Preface: recently the sorting algorithm review, write may not be good, but in order to deepen the impression, they wrote this article

Hill sorting

int shell_sort(int *data, int length) { int gap = 0; Int I = 0, j = 0; for (gap = length / 2; gap >= 1; Gap /= 2) {for (I = gap; i <= length; I ++) {// for (j = I; j >= gap ; J - = gap) {/ / group sorting the if (data [j] < data [j] - gap) {swap (data [j], data [j] - gap); } } } } }Copy the code

Step 1: Determine The Times of grouping. There are 12 elements in the figure above, which are divided into 3 groups

The next for loop goes through three times

for (gap = length / 2; gap >= 1; gap /= 2)
Copy the code

Step 2: Walk through each group

The traversal situation when gap=3 was intercepted, and the loop was 9 times

for (i = gap; i <= length; I++) {// iterate over each groupCopy the code

Step 3: Sort within groups

for (j = i ; j >= gap && data[j - gap] > data[j]; J -= gap) {// Swap (data[j], data[j]); }Copy the code

This in-group sort is the key, sort of insertion sort,

Take the elements of the same color, (let the same elements a, B,c,d,)

Compare the element in the current position (let’s say C) with the previous element (b),

If you want to swap, you swap the positions of the two elements, (becomes a, C,b, D).

And then you continue to compare (a and C) and swap until you don’t need to swap

This time, gap=3 and I =5 are intercepted for analysis

This time we only need to analyze a few elements in deep purple

Quick sort

Int quick_sort(int *data, int left, int right) {if (left >= right) return -1; int key = data[left]; int lo = left, hi = right; while (lo < hi) { while (lo < hi && key < data[hi]) { hi--; } while (lo < hi && key > data[lo]) { lo++; } swap(data[lo], data[hi]); } //lo == hi data[lo] = key; quick_sort(data, left, lo - 1); quick_sort(data, lo + 1, right); }Copy the code

The total code

#include #define DATA_ARRAY_LENGTH 12 void swap(int &a, int &b) { int tmp = a; a = b; b = tmp; return ; } void print(int *data) { for (int i = 0; i < DATA_ARRAY_LENGTH; i ++) { printf("%4d", data[i]); } printf("\n"); } int shell_sort(int *data, int length) { int gap = 0; Int I = 0, j = 0; for (gap = length / 2; gap >= 1; Gap /= 2) {for (I = gap; i <= length; I ++) {// for (j = I; j >= gap && data[j - gap] > data[j]; J -= gap) {// Swap (data[j], data[j]); }}}} int quick_sort(int *data, int left, int right) {// If (left >= right) return -1; int key = data[left]; int lo = left, hi = right; while (lo < hi) { while (lo < hi && key < data[hi]) { hi--; } while (lo < hi && key > data[lo]) { lo++; } swap(data[lo], data[hi]); } //lo == hi data[lo] = key; quick_sort(data, left, lo - 1); quick_sort(data, lo + 1, right); } int quick_sort(int *data, int length) { quick_sort(data, 0, length - 1); } int main() { int i = 0; int data[DATA_ARRAY_LENGTH] = {23, 64, 24, 12, 9, 16, 53, 57, 71, 79, 87, 97}; #if 0 shell_sort(data, DATA_ARRAY_LENGTH); #else quick_sort(data, DATA_ARRAY_LENGTH); #endif for (i = 0; i < DATA_ARRAY_LENGTH; i ++) { printf("%4d", data[i]); } printf("\n"); }Copy the code