1 Classification of sorting algorithms
1.1 stable sorting vs unstable sorting
 Stable sorting: for elements with the same value, the relative positions before and after sequence sorting remain the same, that is, if Ai = Aj, Ai is before Aj, and Ai is still before Aj after sorting. Such as insert sort, bubble sort and merge sort.
 Unstable sorting: the relative positions of elements with the same value before and after sequence sorting may not be consistent, such as selective sorting, fast sorting and heap sorting.
 Note: for elements with different values, the effect of stable sorting and unstable sorting is the same.
1.2 internal sorting VS external sorting
 Internal sorting: read the data to be sorted into memory at one time for sorting;
 External sorting: when the data to be sorted is very large, that is, the data cannot be read into memory at one time. It is necessary to sort the data with the help of external memory and memory.
2 select sort
2.1 ideas
 Each time (for example, the ith time, i=0, 1, 2,..., n2), select the element with the smallest keyword from the following ni data elements to be sorted as the ith element of the ordered element sequence.
 Example of the ith sorting:
2.2 code implementation
void select_sort(int *num, int n) { for (int i = 0; i < n  1; i++) { int ind = i; // Index of minimum value for (int j = i + 1; j < n; j++) { if (num[j] < num[ind]) ind = j; } // ind != i indicates that a new minimum element index was found if (ind != i) swap(num[i], num[ind]); } return ; }
3 insert sort
3.1 ideas
 When the i (i ≥ 1) th data element is inserted, the previous V[0], V[1], V[i1] has been arranged; At this time, use the keyword of V[i] and V[i1], V[i2], Compare the keywords of V[0], insert V[i] after finding the position, and move the object in the original position backward.
 Example of inserting the ith element:
3.2 code implementation
void insert_sort(int *arr, int len) { for (int i = 1; i < len; i++) { int k = i; int v = arr[i]; for (int j = i  1; (j >= 0) && (v < arr[j]); j) { arr[j + 1] = arr[j]; k = j; } if (k != i) arr[k] = v; } return ; }
4 bubble sorting
4.1 ideas
 Each time from back to front (assuming the ith time), j=n1, n2, i. Compare the keywords of V[j1] and V[j] in pairs; If reverse order occurs, exchange V[j1] and V[j];
 Note: in the bubble sorting algorithm, if there is no element exchange operation in a bubble process, it indicates that the sequence at this time is an ordered sequence and should be ended in advance; (optimization means)
 Example of the ith bubbling:
4.2 code implementation
void bubble_sort(int* arr, int len) { int exchange = 1; for (int i = 0; (i < len) && exchange; i++) { exchange = 0; for (int j = len  1; j > i; j) { if (arr[j] < arr[j  1]) { swap(arr[j], arr[j  1]); exchange = 1; } } } return ; }
5 Hill sort
5.1 ideas
 Divide the sequence to be sorted into several groups, insert sort in each group to make the whole sequence basically orderly, and then insert sort the whole sequence;
5.2 code implementation
void Shell(int* arr, int len) { int d = len; do { d = d / 3 + 1; for (int i = d; i < len; i += d) { int k = i; int v = arr[i]; for (int j = i  d; (j >= 0) && (v < arr[j]); j = d) { arr[j + d] = arr[j]; k = j; } if (k != i) arr[k] = v; } } while (d > 1); return ; }
6 merge sort
6.1 ideas
 Merge two ordered sequences into a new ordered sequence. This merging method is called 2way merging, and its time complexity is \ (O(n*log_2n) \);
 Merging routine:
 Merging three ordered sequences into a new ordered sequence is called 3way merging;
 Merging N ordered sequences into a new ordered sequence is called Nway merging;
 Merging multiple ordered sequences into a new ordered sequence is called multichannel merging;
 Example display of 2way merging:

Question: how to sort 20G data on a computer with 4G memory?
A: divide 20G data into 10*2G, sort each 2G data separately, and then merge them;
6.2 code implementation
void merge_sort(int* arr, int l, int r) { if (r == l) return; // Recursive exit // Two way merging int mid = l + (r  l) / 2; merge_sort(arr, l, mid); merge_sort(arr, mid + 1, r); // Merge left and right arrays  > copy int* temp = (int*)malloc(sizeof(int) * (r  l + 1)); int p1 = l, p2 = mid + 1, p = 0; // p1: the subscript of the first element of data on the left, p2: the subscript of the first element of data on the right while (p1 <= mid  p2 <= r) { // P2 > R: the right array element traversal ends if (p2 > r  (p1 <= mid && arr[p1] <= arr[p2])) { temp[p++] = arr[p1++]; } else { temp[p++] = arr[p2++]; } } memcpy(arr + l, temp, sizeof(int) * (r  l + 1)); free(temp); return ; }
7 quick sort
7.1 ideas
 Taking any element in the sequence as the benchmark, the whole sequence is divided into left and right subsequences;
 All elements in the left subsequence are less than or equal to the reference element, and all elements in the right subsequence are greater than the reference element; (sort in ascending order)
 The reference element is arranged in the middle of the two subsequences;
 The two subsequences are divided repeatedly until all the data elements are arranged in the corresponding positions; (recursive implementation)
 Example of fast platoon:
7.2 code implementation
void quick_sort(int *num, int l, int r) { if (l >= r) return ; int x = l, y = r, z = num[x]; // x: Position of head pointer; y: Position of tail pointer; z: Primary element, which defaults to the first element of the array to be sorted while (x < y) { while (x < y && num[y] > z) y; if (x < y) num[x++] = num[y]; while (x < y && num[x] < z) x++; if (x < y) num[y] = num[x]; } num[x] = z; quick_sort(num, l, x  1); quick_sort(num, x + 1, r); return ; }