（5）快速排序-小区间优化
递归时，递归次数以2倍的形式快速增长。需要思考：
（1）如果递归到后面子区间数据较多，可以继续选key进行单趟排序，来分割子区间进行分治递归。
（2）如果递归到后面子区间数据较少，再用分支递归继续处理不太划算。
为了减少递归调用的次数，在递归调用的前面几层使用快速排序，而在递归调用的后面几层根据子区间的数据量选择其他排序，如希尔排序（比快排时间复杂度低）
1. void QuickSortThreeNumberMid(int a, int begin, int end) 2. { 3. if (begin >= end) 4. { 5. return; 6. } 7. 8. //当待排序数据量>20时使用快排 9. if(end - begin + 1 > 20) 10. { 11. int keyi = PartSort(a, begin, end); 12. 13. QuickSortThreeNumberMid(a, begin, keyi - 1); 14. QuickSortThreeNumberMid(a, keyi + 1, end); 15. } 16. else //当待排序数据量<=20时使用希尔排序 17. { 18. ShellSort(a,end-begin+1); 19. } 20. 21. }
快速排序递归方式最大的问题是假如递归深度太深的话，程序本身没有问题，但是栈空间不够时，会导致栈溢出。可以改成非递归方式，需要用栈存储数据模拟递归过程。
基本思路：
（1）将待排序数组第一个元素下标L和最后一个元素下标入栈R
（2）栈不为空时，每次读取调L和R，用单趟排序获取key的下标，判断key的左侧序列和右侧序列是否还需要排序：
①如果需要，入栈对应序列的L和R
②如果不需要（只有一个元素或没有元素需要排序了），不需要入栈
（3）一直执行2，直到栈空
1. //非递归实现 2. void QuickSortNonR(int* a, int begin, int end) 3. { 4. stack st; 5. StackInit(&st); 6. StackPush(&st,begin);//入栈数组最左端元素下标L 7. StackPush(&st, end);//入栈数组最右端元素下标R 8. 9. while (!StackEmpty(&st)) 10. { 11. int left, right; 12. 13. //获取数组最右端元素下标R 14. right = StackTop(&st); 15. StackPop(&st); 16. 17. //获取数组最左端元素下标L 18. left = StackTop(&st); 19. StackPop(&st); 20. 21. int keyi = PartSort1(a, left, right); 22. 23. if (keyi - left > 1) 24. { 25. StackPush(&st, left);//入栈左侧序列的左下表L 26. StackPush(&st, keyi - 1);//入栈右侧序列的右下表R 27. } 28. 29. if (right - keyi > 1) 30. { 31. StackPush(&st, keyi + 1);//入栈左侧序列的左下表L 32. StackPush(&st, right);//入栈右侧序列的右下表R 33. } 34. } 35. 36. StackDestroy(&st); 37. 38. }
快速排序特性总结：
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)（每层有n个元素，一共logN层）
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
四、归并排序
基本思想：
也是一种分治法，将待排序数组看成为n个长度为1的有序子数组，把这些子数组两两归并，使得到「n/2」个长度为2的有序子数组；然后再把这「n/2」个有序数组的子数组两两归并，如此反复，直到最后得到一个长度为n的有序数组为止，这种排序方法也叫做二路归并排序。
归并需要借助第三方数组，否则会造成覆盖，在"治"的时候需要取两个区间的小的元素插入到第三方数组，直到一个区间结束了，再把另一个区间剩下的元素尾插到最后
055-MergeSort.h
1. #pragma once 2. #include<stdio.h> 3. #include <stdlib.h> 4. 5. //打印 6. void Print(int* a, int n); 7. 8. //归并排序 9. void MergeSort(int a, int n);
055-MergeSort.c
1. #include "055-MergeSort.h" 2. 3. //打印 4. void Print(int* a, int n) 5. { 6. for (int i = 0; i < n; i++) 7. { 8. printf("%d ", a[i]); 9. } 10. 11. printf("\n"); 12. } 13. 14. void _MergeSort(int* a, int left, int right, int* temp) 15. { 16. if (left >= right) 17. { 18. return; 19. } 20. 21. int mid = (left + right) / 2; 22. _MergeSort(a, left, mid, temp); 23. _MergeSort(a, mid + 1, right, temp); 24. 25. //将两段有序子区间归并到temp，并拷贝回去 26. int begin1 = left, end1 = mid; 27. int begin2 = mid + 1, end2 = right; 28. 29. int i = left; 30. while (begin1 <= end1 && begin2 <= end2) 31. { 32. //将两段有序子区间的较小值拷贝到temp 33. if (a[begin1] < a[begin2]) 34. { 35. temp[i++] = a[begin1++]; 36. } 37. else 38. { 39. temp[i++] = a[begin2++]; 40. } 41. } 42. 43. //如果其中一个有序子区间没有拷贝完，将剩下的元素直接拷贝到temp中 44. while (begin1 <= end1) 45. { 46. temp[i++] = a[begin1++]; 47. } 48. 49. while (begin2 <= end2) 50. { 51. temp[i++] = a[begin2++]; 52. } 53. 54. int j = 0; 55. 56. //将temp数组拷回到a中 57. for (j = left; j <= right; j++) 58. { 59. a[j] = temp[j]; 60. } 61. } 62. 63. void MergeSort(int* a, int n) 64. { 65. //申请额外空间 66. int* temp = (int*)malloc(sizeof(int) * n); 67. 68. if (temp == NULL) 69. { 70. printf("malloc fail\n"); 71. exit(-1); 72. } 73. 74. //归并排序 75. _MergeSort(a, 0, n - 1,temp); 76. 77. //释放空间 78. free(temp); 79. }
055-TestMergeSort.c
1. #include "055-MergeSort.h" 2. 3. void TestMergeSort() 4. { 5. int arr[] = { 10,9,8,7,6,5,4,3,2,1 }; 6. MergeSort(arr, sizeof(arr) / sizeof(arr[0])); 7. Print(arr, sizeof(arr) / sizeof(arr[0])); 8. } 9. 10. int main() 11. { 12. TestMergeSort(); 13. 14. return 0; 15. }
归并排序的特性总结：
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
归并的非递归的实现需要控制每次归并的元素个数，先是1 1归并，再2 2归并，4 4归并……，因
非递归可以控制每次的gap成倍增长来达到归并的目的，但gap成倍增长也可能会带来这样的问题
（1）第一个区间的元素个数=gap，第二个区间的元素个数<gap
（2）第一个区间的元素个数<=gap，第二个区间的元素不存在
055- MergeSortNonR.h
1. #pragma once 2. #include<stdio.h> 3. #include <stdlib.h> 4. 5. //打印 6. void Print(int* a, int n); 7. 8. //归并非递归 9. void MergeSortNonR(int* a, int n);
055- MergeSortNonR.c
1. #include "055- MergeSortNonR.h" 2. 3. //打印 4. void Print(int* a, int n) 5. { 6. for (int i = 0; i < n; i++) 7. { 8. printf("%d ", a[i]); 9. } 10. 11. printf("\n"); 12. } 13. 14. void _MergeSortNonR(int* a, int* tmp, int begin1, int end1, int begin2, int end2) 15. { 16. int i = begin1; 17. int j = begin1; 18. //将两段子区间进行归并，归并结果放在tmp中 19. 20. while (begin1 <= end1 && begin2 <= end2) 21. { 22. //将较小元素拷贝到tmp中 23. if (a[begin1] < a[begin2]) 24. { 25. tmp[i++] = a[begin1++]; 26. } 27. else 28. { 29. tmp[i++] = a[begin2++]; 30. } 31. 32. } 33. //如果其中一个区间结束，那么另一个区间剩余的元素直接拷贝到tmp中 34. while (begin1 <= end1) 35. { 36. tmp[i++] = a[begin1++]; 37. } 38. 39. while (begin2 <= end2) 40. { 41. tmp[i++] = a[begin2++]; 42. } 43. 44. //归并结束，把tmp拷贝到原数组 45. for (; j <= end2; j++) 46. { 47. a[j] = tmp[j]; 48. } 49. 50. } 51. 52. 53. //归并排序非递归 54. void MergeSortNonR(int* a, int n) 55. { 56. int* tmp = (int*)malloc(sizeof(int) * n);//申请一个临时数组空间 57. if (tmp == NULL) 58. { 59. printf("malloc fail\n"); 60. exit(-1); 61. } 62. 63. int gap = 1;//需合并的子区间中元素的个数 64. while (gap < n) 65. { 66. int i = 0; 67. for (i = 0; i < n; i += 2 * gap) 68. { 69. int begin1 = i, end1 = i + gap - 1; 70. int begin2 = i + gap, end2 = i + 2 * gap - 1; 71. 72. //第一个区间的元素个数<=gap，第二个区间的元素不存在，不需要合并 73. if (begin2 >= n) 74. { 75. break; 76. } 77. 78. //第一个区间的元素个数=gap，第二个区间的元素个数<gap，则第二个小区间的右边界即为数组的右边界 79. if (end2 >= n) 80. { 81. end2 = n - 1; 82. } 83. _MergeSortNonR(a, tmp, begin1, end1, begin2, end2);//合并两个有序序列 84. 85. } 86. gap *= 2;//下一趟需合并的子序列中元素的个数成倍增长 87. } 88. free(tmp);//释放temp空间 89. }
055- TestMergeSortNonR.c
1. #include "055- MergeSortNonR.h" 2. 3. void TestMergeSortNonR() 4. { 5. int arr[] = { 10,9,8,7,6,5,4,3,2,1 }; 6. MergeSortNonR(arr, sizeof(arr) / sizeof(arr[0])); 7. Print(arr, sizeof(arr) / sizeof(arr[0])); 8. } 9. 10. int main() 11. { 12. TestMergeSortNonR(); 13. 14. return 0; 15. }
内排序：数据量相对少，可以放到内存中排序
外排序：数据量较大，内存中放不下，数据需要放到磁盘中，需要排序
有10亿个整数，放到文件中，需要排序假设可以给512MB的内存，如何进行排序？
（1）4GB的数据，分8次读取完，每次读1/8即512MB到内存中进行排序，排序完毕后写到一个小文件，再继续读下一个1/8，重复这个过程，直到这8个文件都有序。
注意：1/8大小的数据在内存中排序时，是内排序，不能用归并排序，因为归并排序要额外申请O(N)的空间，可以选择快排等排序。
（2）8个文件已有序，还需要对这8个文件进行排序，从前两个文件中分别读取一个数据进行排序后写到一个文件中，再分别读取两个数据进行排序写到文件中，直到这两个文件的数据都已经比较完毕，对其他文件也同样进行排序，输出4个文件。再重复前述操作，直到所有文件都排序完毕，输出一个4GB的有序文件。
五、计数排序
原理：用另一个数组统计原数组中相同元素出现的次数，再根据统计次数反向填充到原数组中
需要考虑到，如果a中最小的元素值不是从0开始呢？而是从10000，100000开始呢？Count数组长度岂不是很大？而且前面的元素值统计没有意义，这会造成空间的浪费，因此Count数组的长度取决于数组a中最大最小元素值的绝对差。
055-CountSort.h
1. #pragma once 2. #include<stdio.h> 3. #include <stdlib.h> 4. 5. //打印 6. void Print(int* a, int n); 7. 8. //计数排序 9. void CountSort(int* a, int n)
055-CountSort.c
1. #include "055-CountSort.h" 2. 3. //打印 4. void Print(int* a, int n) 5. { 6. for (int i = 0; i < n; i++) 7. { 8. printf("%d ", a[i]); 9. } 10. 11. printf("\n"); 12. } 13. 14. //计数排序 15. void CountSort(int* a, int n) 16. { 17. //Count数组的长度取决于数组a的元素大小的绝对差 18. //为了计算绝对差，需要先找出数组a的最大最小值 19. int max = a[0], min = a[0]; 20. for (int i = 0; i < n; i++) 21. { 22. if (a[i] > max) 23. { 24. max = a[i]; 25. } 26. if (a[i] < min) 27. { 28. min = a[i]; 29. } 30. } 31. 32. //绝对差作为申请分配新数组空间的个数 33. int range = max - min + 1; 34. int* Count = (int*)malloc(sizeof(int) * range); 35. 36. if (Count == NULL) 37. { 38. printf("malloc fail\n"); 39. exit(-1); 40. } 41. 42. //初始化Count数组 43. memset(Count, 0, sizeof(int)*range); 44. 45. //Count数组赋值为数组a的元素出现的次数 46. for (int i = 0; i < n; i++) 47. { 48. Count[a[i]-min]++; 49. } 50. 51. //根据统计次数反向填充到原数组a中 52. int i = 0; 53. for (int j = 0; j < range; j++) 54. { 55. while (Count[j]--) 56. { 57. a[i++] = j + min; 58. } 59. } 60. }
055-TestCountSort.c
1. #include "055-CountSort.h" 2. 3. void TestCountSort() 4. { 5. int arr[] = { 2,5,3,0,2,3,0,3 }; 6. CountSort(arr, sizeof(arr) / sizeof(arr[0])); 7. Print(arr, sizeof(arr) / sizeof(arr[0])); 8. } 9. 10. int main() 11. { 12. TestCountSort(); 13. 14. return 0; 15. }
适用场景：待排序数组的范围比较集中，效率就高，否则Count数组长度很长，浪费空间；且只适合整数，浮点数和字符串不适用。
时间复杂度：O(n+range)
空间复杂度：O(n)
六、排序总结
稳定的定义：数组中相同的值，排完序后，相对顺序不变，就是稳定的，否则就是不稳定的。
