一文带你秒懂十大排序（上）：https://developer.aliyun.com/article/1521563
2、快速排序
算法思想：在待排序的序列中选择一个基准，按照基准将元素分成左右两个子序列，使得左边的子序列的元素都小于基准元素，使得右边的子序列都大于基准元素，对左右子序列继续重复上述步骤，使得每个子序列的长度为1为止。
动图演示：
代码实现：
public static void quickSort(int[] array){ quick(array,0,array.length - 1); } public static void quick(int[] array,int left,int right){ if(left >= right){ return; } int part = partition(array,left,right); quick(array,left,part -1); quick(array,part + 1,right); } public static int partition(int[] array,int start,int end){ int temp=array[start]; while(start < end){ while(start < end && array[end] >= temp){ end--; } array[start] = array[end]; while (start < end && array[start] <= temp){ start++; } array[end] = array[start]; } array[start] = temp; return start; }
性能分析：
- 时间复杂度：O(nlog2 n)。
- 空间复杂度：O(log2 n)。
- 稳定性：稳定。
上述快速排序的时间复杂度是在最好情况下的，最坏情况下整个待排序元素是顺序或是逆序的，时间复杂度高达O(n^2),并且当数据量很大的时候，空间复杂度也是很大的，可能会出现栈溢出，所以需要进行优化：
每次选择基准元素时采用三数取中法，就是将right坐标、left坐标的值和mid中间值约束，以确保每次的基准元素不是最大值或最小值，还有当子序列长度不太大时，可以使用直接插入排序来提高效率。
public static void quickSort(int[] array){ quick(array,0,array.length - 1); } public static void quick(int[] array,int left,int right){ if(left >= right){ return; } if(right-left <=15){ insertSort(array,left,right); return; } int index = midThree(array,left,right); int temp = array[index]; array[index] = array[left]; array[left] = temp; int part = partition(array,left,right); quick(array,left,part -1); quick(array,part + 1,right); } public static int partition(int[] array,int start,int end){ int temp=array[start]; while(start < end){ while(start < end && array[end] >= temp){ end--; } array[start] = array[end]; while (start < end && array[start] <= temp){ start++; } array[end] = array[start]; } array[start] = temp; return start; } public static void insertSort(int[] array,int left,int right){ for(int i = left+1;i <= right;i++){ int temp = array[i]; int j = i-1; for(;j >=left;j--){ if(array[j] > temp){ array[j+1] = array[j]; }else{ break; } } array[j+1] = temp; } } public static int midThree(int[] array,int left,int right){ int mid=(left+right) / 2; if(array[left] < array[right]){ if(array[mid] > array[left]){ return mid; }else{ return left; } }else{ if(array[mid] > array[right]){ return mid; }else{ return right; } } }
快速排序也可以非递归实现： 利用栈将每次划分的左右子序列的下标入栈，只要栈不为空，每次弹出两个元素，作为调整区间的下标。直到子序列只有一个元素的时候就停止入栈。
代码实现：
public static void quickSort2(int[] array){ Deque<Integer> stack = new LinkedList<>(); int left=0; int right=array.length-1; stack.push(left); stack.push(right); while (!stack.isEmpty()){ right=stack.pop(); left=stack.pop(); int part=partition(array,left,right); if(part > left+1){ stack.push(left); stack.push(part-1); } if(part < right-1){ stack.push(part+1); stack.push(right); } } }
四、归并排序
算法思想：采用的是分治法的思想，先把待排序的序列分解成若干个子序列，先让子序列有序，然后将有序的子序列合并是整个待排序的序列。
动图演示：
代码实现：
public static void mergeSort(int[] array){ divideMerge(array,0,array.length-1); } public static void divideMerge(int[] array,int left,int right){ if(left >= right){ return; } int mid=(left+right) / 2; divideMerge(array,left,mid); divideMerge(array,mid+1,right); merge(array,left,right,mid); } public static void merge(int[] array,int left,int right,int mid){ int s1=left; int s2=mid+1; int[] nums=new int[right-left+1]; int k=0; while(s1 <= mid && s2 <= right){ if(array[s1]<array[s2]){ nums[k++] = array[s1++]; }else{ nums[k++] = array[s2++]; } } while(s1 <= mid){ nums[k++] = array[s1++]; } while (s2 <= right){ nums[k++] = array[s2++]; } for(int i=0;i< k;i++){ array[i+left]=nums[i]; } }
性能分析：
- 时间复杂度：O(nlog2 n)。
- 空间复杂度：O(n)。
- 稳定性：稳定 。
同样，归并排序也可以进行非递归实现。
public static void mergeSort2(int[] array) { int gap = 1; while (gap < array.length) { for (int i = 0; i < array.length; i = i + gap * 2) { int left = i; int mid = left + gap - 1; if (mid >= array.length) { mid = array.length - 1; } int right = mid + gap; if (right >= array.length) { right = array.length - 1; } merge(array, left, right, mid); } gap *= 2; } }
海量数据的排序问题：
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G ，需要排序的数据有 100G
解决方案：因为待排序的数据有100G而内存只有1G，那么就可以将待排序的数据等分为200份，每份数据大小为512M，然后将每份数据存入内存中排好序，然后对这200份数据在内存外进行再进行归并排序即可。
五、计数排序
算法思想：利用鸽巢原理，开辟一段较大的空间的数组，数组中默认元素为0,将待排序的元素对应到下标所对应的元素值加一，计数排序主要应用于待排序的序列在某个范围内。
动图演示：
代码实现：
public static void countingSort(int[] array){ int min = array[0]; int max = array[0]; for(int i = 1;i < array.length;i++){ if(array[i] < min){ min = array[i]; } if(array[i] > max){ max = array[i]; } } int[] nums = new int[max-min+1]; for(int i = 0;i < array.length;i++){ nums[array[i]-min]++; } int k=0; for(int i = 0;i < nums.length;i++){ while(nums[i] != 0){ array[k++] = min+i; nums[i]--; } } }
性能分析：
- 时间复杂度：O(max(n,数组范围))。
- 空间复杂度：O(数组范围)。
- 稳定性：稳定。
六、基数排序
算法思想：基数排序是对数字的每一位进行排序的，最大数字的位数决定了排列的次数，每次先排列，然后再收集，重复上述步骤，直到最高位排序完成。
动图演示：
代码实现：
//基数排序 public static void baseSort(int[] array){ int max = array[0]; for(int i = 1;i < array.length;i++){ if(array[i] > max){ max = array[i]; } } int count=countByte(max); LinkedList<LinkedList<Integer>> lists = new LinkedList<>(); for(int i = 0;i < 10;i++){ lists.add(new LinkedList<>()); } int k=1; while(k <= count){ for(int i = 0;i < array.length;i++){ int num = getByteNum(array[i],k); lists.get(num).add(array[i]); } int j = 0; for(int i = 0;i < lists.size();i++){ while(!lists.get(i).isEmpty()){ array[j++] =lists.get(i).poll(); } } k++; } } //计算出数字的位数 public static int countByte(int num){ int count = 0; while(num != 0){ num=num/10; count++; } return count; } //获取到指定位的数字 public static int getByteNum(int num,int index){ String s = String.valueOf(num); if(index <= s.length()){ return (int)(s.charAt(s.length() - index) - '0'); } return 0; }
性能分析：
- 时间复杂度：O(n*k)。
- 空间复杂度：O(n+k)。
- 稳定性： 稳定。
七、桶排序
算法思想：将待排序的序列划分为多个范围大小相同的区间，将元素分别放入到对应的区间，对每个子区间进行排序，最后整个序列变得有序。
动图演示：
代码实现：
public static void bucketSort(int[] array){ int min = array[0]; int max = array[0]; for(int i = 1;i < array.length;i++){ if(array[i] < min){ min = array[i]; } if(array[i] > max){ max = array[i]; } } int size = (max-min) / array.length + 1; LinkedList<LinkedList<Integer>> lists = new LinkedList<>(); for(int i = 0;i < size;i++){ lists.add(new LinkedList<>()); } for(int i = 0;i < array.length;i++){ int num = (array[i] - min) / size; lists.get(num).add(array[i]); } int k=0; for(int i = 0;i < size;i++){ lists.get(i).sort(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o1-o2; } }); while(!lists.get(i).isEmpty()){ array[k++]=lists.get(i).poll(); } } }
性能分析：
- 时间复杂度：O(n+k)。
- 空间复杂度：O(n+k)。
- 稳定性：稳定。
八、排序总结
| 算法名称 | 时间复杂度 | 空间复杂度 | 稳定性 |
| 直接插入排序 | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(n^1.3) | O(1) | 不稳定 |
| 直接选择排序 | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(nlog2 n) | O(1) | 不稳定 |
| 冒泡排序 | O(n^2) | O(1) | 稳定 |
| 快速排序 | O(nlog2 n) |
O(log2 n) | 不稳定 |
| 归并排序 | O(nlog2 n) | O(n) | 稳定 |
| 计数排序 | O(max(n,数组范围)) |
O(数组范围) | 稳定 |
| 基数排序 | O(n*k） |
O(n+k) | 不稳定 |
| 桶排序 | O(n+k) | O(n+k) | 稳定 |
注意点：
序列基本有序时，快排退化成冒泡排序，直接插入排序最快。
各排序算法中，最坏情况下时间复杂度最低的是堆排序。
初始数据集的排列顺序对算法的性能无影响的有堆排序、归并排序、选择排序。
