挖坑法递归代码实现：
1. public void quickSort(int[]arr){ 2. quick(arr,0,arr.length-1); 3. } 4. 5. private void quick(int[]arr,int start,int end){ 6. 7. if(start>=end){ 8. return; 9. } 10. 11. int pivot=pivotPartationHoare(arr,start,end); 12. quick(arr,start,pivot-1); 13. quick(arr,pivot+1,end); 14. } 15. 16. private int pivotPartation(int[]arr,int left,int right){ 17. int i=left; 18. int pivot=arr[left]; 19. 20. while(left<right){ 21. 22. //left<right不能少，否则会出现越界 23. while (left<right&&arr[right]>=pivot){ 24. right--; 25. } 26. arr[left]=arr[right]; 27. while (left<right&&arr[left]<=pivot){ 28. left++; 29. } 30. 31. arr[right]=arr[left]; 32. 33. //都找到后交换 34. swap(arr,left,right); 35. 36. } 37. 38. //一边找完之后和原来的left交换 39. arr[left]=pivot; 40. //swap(arr,left,i); 41. 42. return left;//为新的基准 43. 44. } 45. 46. public void swap(int[]arr,int i,int j){ 47. int temp=arr[i]; 48. arr[i]=arr[j]; 49. arr[j]=temp; 50. }
快排优化方法：
1. 三数取中法选key
2. 递归到小的子区间时，可以考虑使用插入排序
1. private static int partition(int[] array, int left, int right) { 2. int prev = left ; 3. int cur = left+1; 4. while (cur <= right) { 5. if(array[cur] < array[left] && array[++prev] != array[cur]) { 6. swap(array,cur,prev); 7. } 8. cur++; 9. } 10. swap(array,prev,left); 11. return prev; 12. } 13. 14. /** 15. * 对指定区间的数据进行插入排序 16. * @param array 17. * @param left 18. * @param right 19. */ 20. private void insertSort(int[] array,int left,int right) { 21. for (int i = left+1; i <= right; i++) { 22. int tmp = array[i]; 23. int j = i-1; 24. for (; j >= left;j--) { 25. if(array[j] > tmp) { 26. array[j+1] = array[j]; 27. }else { 28. //array[j+1] = tmp; 29. break; 30. } 31. } 32. array[j+1] = tmp; 33. } 34. } 35. private void quick(int[] array,int start,int end) { 36. 37. if(start >= end) { 38. return; 39. } 40. 41. if(end-start+1 <= 15) { 42. //对 start 和 end区间 范围内 使用插入排序 43. insertSort(array,start,end); 44. return; 45. } 46. //System.out.println("start: " +start +" end: "+end); 47. 48. // 在执行 partition 找基准之前，解决划分不均匀的问题 49. int index = findMidValOfIndex(array,start,end); 50. swap(array,start,index); 51. 52. int pivot = partition(array,start,end); 53. quick(array,start,pivot-1); 54. quick(array,pivot+1,end); 55. } 56. 57. private int findMidValOfIndex(int[] array,int start,int end) { 58. int midIndex = (start+end) / 2; 59. // 3 9 60. if(array[start] < array[end]) { 61. if(array[midIndex] < array[start]) { 62. return start; 63. }else if(array[midIndex] > array[end]) { 64. return end; 65. }else { 66. return midIndex; 67. } 68. }else { 69. if(array[midIndex] > array[start]) { 70. return start; 71. }else if(array[midIndex] < array[end]) { 72. return end; 73. }else { 74. return midIndex; 75. } 76. } 77. } 78. 79. 80. /** 81. * 时间复杂度：O(N*logN) 82. * 空间复杂度：O(logN) 83. * 稳定性：不稳定的排序 84. * @param array 85. * 86. * 问题： 87. * 当我们给定的数据 是有序的时候，这个快排的时间复杂度是O(n^2) 88. * 空间复杂度：O(n) 89. */ 90. public void quickSort1(int[] array) { 91. quick(array,0,array.length-1); 92. }
非递归实现：
1. public static void quickSort(int[] array) { 2. Stack<Integer> stack = new Stack<>(); 3. int start = 0; 4. int end = array.length-1; 5. int pivot = partition(array,start,end); 6. //1.判断左边是不是有2个元素 7. if(pivot > start+1) { 8. stack.push(start); 9. stack.push(pivot-1); 10. } 11. //2.判断右边是不是有2个元素 12. if(pivot < end-1) { 13. stack.push(pivot+1); 14. stack.push(end); 15. } 16. while (!stack.isEmpty()) { 17. end = stack.pop(); 18. start = stack.pop(); 19. pivot = partition(array,start,end); 20. //3.判断左边是不是有2个元素 21. if(pivot > start+1) { 22. stack.push(start); 23. stack.push(pivot-1); 24. } 25. //4.判断右边是不是有2个元素 26. if(pivot < end-1) { 27. stack.push(pivot+1); 28. stack.push(end); 29. } 30. } 31. 32. }
快速排序总结
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
归并排序
归并排序过程
基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并
归并排序
递归实现代码：
1. public void mergeSort1(int[] array) { 2. mergeSortChild(array,0,array.length-1); 3. } 4. 5. private void mergeSortChild(int[] array,int left,int right) { 6. if(left == right) { 7. return; 8. } 9. int mid = (left+right) / 2; 10. mergeSortChild(array,left,mid); 11. mergeSortChild(array,mid+1,right); 12. //合并 13. merge(array,left,mid,right); 14. } 15. 16. private void merge(int[] array,int left,int mid,int right) { 17. int s1 = left; 18. int e1 = mid; 19. int s2 = mid+1; 20. int e2 = right; 21. int[] tmpArr = new int[right-left+1]; 22. int k = 0;//表示tmpArr 的下标 23. while (s1 <= e1 && s2 <= e2) { 24. if(array[s1] <= array[s2]) { 25. tmpArr[k++] = array[s1++]; 26. }else{ 27. tmpArr[k++] = array[s2++]; 28. } 29. } 30. while (s1 <= e1) { 31. tmpArr[k++] = array[s1++]; 32. } 33. while (s2 <= e2) { 34. tmpArr[k++] = array[s2++]; 35. } 36. //tmpArr当中 的数据 是right left 之间有序的数据 37. for (int i = 0; i < k; i++) { 38. array[i+left] = tmpArr[i]; 39. } 40. }
非递归实现代码：
1. public static void mergeSort(int[] array) { 2. int gap = 1; 3. while (gap < array.length) { 4. for (int i = 0; i < array.length; i += gap*2) { 5. int left = i; 6. int mid = left + gap -1; 7. int right = mid+gap; 8. if(mid >= array.length) { 9. mid = array.length-1; 10. } 11. if(right >= array.length) { 12. right = array.length-1; 13. } 14. merge(array,left,mid,right); 15. } 16. gap *= 2; 17. } 18. }
归并排序总结
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
海量数据的排序问题
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
1. 先把文件切分成 200 份，每个 512 M
2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3. 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
排序算法复杂度及稳定性分析
| 排序方法 | 最好 | 平均 | 最坏 | 空间复杂度 | 稳定性 |
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 希尔排序 | O(n) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(1) | 不稳定 |
| 快速排序 | O(n * log(n)) | O(n * log(n)) | O(n^2) | O(log(n)) ~ O(n) | 不稳定 |
| 归并排序 | O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(n) | 稳定 |
