Sorting: the focus of written examination and interview. 1. Algorithm description; 2. Realization; 3. Efficiency analysis (time complexity, space complexity, stability)

Difficulty: too many sorting algorithms

Stability: for data with the same keyword (the same number), if A is in front of A 'before sorting, the algorithm is stable if A is in front of A' after sorting, otherwise it is unstable; If there is no jumping exchange data, it is unstable if there is one, and it is stable if there is no one

The first sort: (simple) direct insertion sort. The more ordered the characteristic data, the faster. If it is completely ordered, it is O(n)

The second sorting: shell sorting. For interval grouping, insert sorting is used to make the group orderly, then reduce the grouping and sort until the number of groups is 1

The third sort: bubble sort. Compare the two, and the big one will come back

The fourth sort: quick sort. Find a benchmark (the first data),

1. Find data smaller than the benchmark from back to front and move forward. 2. Find data larger than the benchmark from front to back and move back. 3. Repeat 1 and 2 until the benchmark position is found

Disadvantages of quick sorting: 1. The more ordered, the slower. If it is completely ordered, it is O(n^2);2. The spatial complexity is O(logn), not O(1);3. Instability;

Fifth sorting: Select Sorting. Find the minimum value and the first exchange to be sorted from the to be sorted each time

Sixth sort: heap sort

The seventh sort: 2-way merge sort. Merge two pieces of ordered data into one piece of ordered data until all the data are in order

The eighth sorting: Radix (bucket) sorting, low order first, all numbers from low order (bits) to high order, enter the corresponding queue in turn, and then exit until all numbers are in order

# 1. (simple) direct insert sort

//(simple) direct insert sort //(simple) direct insertion sorting. The more ordered the characteristic data, the faster. If it is completely ordered, it is O(n) void InsertSort(int* arr, int len)//O(n^2),O(1), stable {//No data exchange, stable int tmp; int j; for (int i = 1; i < len; i++)//i subscript of the number currently to be processed { tmp = arr[i]; for (j = i - 1; j >= 0; j--)//Find the position from back to front and move the data at the same time { if (arr[j] > tmp)//The data needs to be moved back { arr[j + 1] = arr[j]; } else { break; } } arr[j + 1] = tmp; } }

# 2. shell sorting

//Shell sorting. For interval grouping, insert sorting is used to make the group orderly, then reduce the grouping and then sort until the number of groups is 1 //One shell process, gap is the number of groups (interval) static void Shell(int* arr, int len, int gap) { int tmp; int j; for (int i = gap; i < len; i++)//Start with the "second" data { tmp = arr[i]; for (j = i - gap; j >= 0; j -= gap)//Compared with the same group of data { if (arr[j] > tmp) { arr[j + gap] = arr[j]; } else { break; } } arr[j + gap] = tmp; } } void ShellSort(int* arr, int len)//O(n^1.3 ~n^1.5),O(1), unstable { int d[] = { 5,3,1 };//Number of groups. The last one must be 1 for (int i = 0; i < sizeof(d) / sizeof(d[0]); i++) { Shell(arr, len, d[i]); } }

# 3. Bubble sorting

//Bubble sort, pairwise comparison, big one back void BubbleSort(int* arr, int len)//O(n^2),O(1), stable { int tmp; for (int i = 0; i < len - 1; i++)//Number of trips { for (int j = 0; j + 1 < len - i; j++)//Note that j+1 is out of bounds { if (arr[j] > arr[j + 1])//exchange { tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } }

# 4. Quick sort

//Quick sort. Find a benchmark (first data), // 1. Find data smaller than the benchmark from back to front and move forward. 2. Find data larger than the benchmark from front to back and move back. 3. Repeat 1 and 2 until the benchmark position is found // Disadvantages of quick sorting: 1. The more ordered, the slower. If it is completely ordered, it is O(n^2);2. The spatial complexity is O(logn), not O(1);3. Instability; //A division of quick sort int Partition(int* arr, int low, int high)//O(n),O(1) { int tmp = arr[low];//benchmark while (low < high) { //Find data smaller than the benchmark from back to front and move forward while (low<high && arr[high]>tmp) high--; if (low < high) arr[low] = arr[high]; //Find data larger than the benchmark from front to back and move back while (low < high && arr[low] <= tmp) low++; if (low < high) arr[high] = arr[low]; } arr[low] = tmp; return low; } void Quick(int* arr, int low, int high) { int par = Partition(arr, low, high); if (low < par - 1)//There is more than one data on the left { Quick(arr, low, par - 1); } if (par + 1 < high) { Quick(arr, par + 1, high); } } void QuickSort(int* arr, int len)//O(nlogn),O(logn), unstable { Quick(arr, 0, len - 1); } void Show(int* arr, int len) { for (int i = 0; i < len; i++) { printf("%d ", arr[i]); } printf("\n"); }

# 5. Select Sorting

//Select sorting. Find the minimum value and the first exchange to be sorted each time //Select sort void SelectSort(int* arr, int len)//O(n^2),O(1), unstable { int minIndex;//Subscript of minimum value int tmp; for (int i = 0; i < len - 1; i++) { minIndex = i; for (int j = i + 1; j < len; j++)//Find minimum value { if (arr[minIndex] > arr[j])//Note that it is different from books. This code is not exchanged. Exchange it after all are found { minIndex = j; } } if (minIndex != i)//The minimum value is exchanged with the first value to be sorted { tmp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = tmp; } } }

# 6. Heap sorting

//Heap adjustment //Adjust from top to bottom, start the subscript and end the subscript void HeapAdjust(int* arr, int start, int end)//O(logn) { int tmp = arr[start]; for (int i = 2 * start + 1; i <= end; i = 2 * i + 1) { if (i < end && arr[i] < arr[i + 1])//There is a right child, and the value of the left child is less than that of the right child i++;//i must be the subscript of the larger value of the left and right children if (arr[i] > tmp) { arr[start] = arr[i]; start = i; } else //Got a location break; } arr[start] = tmp; } //Parent - > child: I - > 2I + 1,2i-1 //Child - > parent: I - > (i-1) / 2 //Heap sort void HeapSort(int* arr, int len)//O(nlogn),O(1), unstable { //Build a large root pile for the first time, and adjust it from back to front for many times int i; for (i = (len - 1 - 1) / 2; i >= 0; i--)//Start from the last subtree O(nlogn) { HeapAdjust(arr, i, len - 1); } //Swap the root with the last one to be sorted each time, and then adjust it int tmp; for (i = 0; i < len - 1; i++) //O(nlogn) { //exchange tmp = arr[0]; arr[0] = arr[len - 1 - i]; arr[len - 1 - i] = tmp; //Readjustment HeapAdjust(arr, 0, len - 1 - i - 1); } }

# 7. Merge and sort

//2-way merge sort. Merge two pieces of ordered data into one piece of ordered data until all the data are in order //One time merge //gap: length of merge segment static void Merge(int* arr, int len, int gap)//O(n),O(n) { int low1 = 0;//Starting subscript of the first merge segment int high1 = low1 + gap - 1;//End subscript of the first merge segment int low2 = high1 + 1;//Starting subscript of the second merge segment int high2 = low2 + gap < len ? low2 + gap - 1 : len - 1;//End subscript of the second merge segment int* brr = (int*)malloc(len * sizeof(int));//Store consolidated data int i = 0;//brr subscript assert(brr != NULL); //There are two merging segments while (low2 < len) { //Both merging segments still have data, which needs to be compared while (low1 <= high1 && low2 <= high2) { if (arr[low1] <= arr[low2]) { brr[i++] = arr[low1++]; } else { brr[i++] = arr[low2++]; } } //The data of one merging segment has been completed, and the other still has data while (low1 <= high1) { brr[i++] = arr[low1++]; } while (low2 <= high2) { brr[i++] = arr[low2++]; } //Next two merge segments low1 = high2 + 1; high1 = low1 + gap - 1; low2 = high1 + 1; high2 = low2 + gap < len ? low2 + gap - 1 : len - 1; } //There is only one merge segment while (low1 < len) { brr[i++] = arr[low1++]; } //Copy the merged data to arr for (i = 0; i < len; i++) { arr[i] = brr[i]; } free(brr); } //Merge sort void MergeSort(int* arr, int len)//O(nlogn),O(n), stable { for (int i = 1; i < len; i *= 2) { Merge(arr, len, i); } }

# 8. Cardinality sorting

//Base (bucket) sorting, low order first, all numbers, starting from low order (bits) to high order, are successively entered into the corresponding queue and then out until they are all in order //Gets the number of digits of the maximum number static int GetFigur(int* arr, int len) { int max = arr[0];//Maximum for (int i = 1; i < len; i++) { if (max < arr[i]) max = arr[i]; } //987 - > 3 lost bits n /= 10 int count = 0; while (max != 0) { count++; max /= 10; } return count; } //Gets the number of the right digit of the decimal integer. Figure starts from 0, //For example, (123,0) - > 3; (123,1)->2; (123,2)->1; (123,3)->0 static int GetNum(int n, int figur) { for (int i = 0; i < figur; i++) n /= 10; return n % 10; } //Cardinality sort void RadixSort(int* arr, int len)//O(d*n) d represents the number of bits of data, O(n), stable { //You need to use 10 queues to store the numbers in the queue SqQueue queArr[10]; for (int i = 0; i < 10; i++) { InitQueue(&queArr[i]); } //Get the number of digits of the maximum number and determine the number of trips in and out of the team int count = GetFigur(arr, len); int index;//Subscript of queue for (int i = 0; i < count; i++)//Process the ith number of each number from right to left { for (int j = 0; j < len; j++)//Traverse the array and join the queue { index = GetNum(arr[j], i);//index saves arr[j] the subscript of the queue that should be entered Push(&queArr[index], arr[j]);//Store the number in the corresponding queue } //All data dequeue. Dequeue the data of all queues in turn int j = 0;//arr subscript for (int k = 0; k < 10; k++)//All queues { //A queue may have more than one data while (!IsEmpty(&queArr[k])) { Pop(&queArr[k], &arr[j++]); } } } for (int i = 0; i < 10; i++) { Destroy(&queArr[i]); } }