堆排序
之前在对应文章也讲到了堆排序的写法，这里就不再做过多的阐述，放上对应的链接:
点我进入对应文章
关于堆排序的时间复杂度，空间复杂度:
冒泡排序
时间复杂度:O(N^2)
空间复杂度:O(1)
稳定性：稳定
点我进入对应文章
快速排序(重要，常考)
概念
快速排序使用分治的思想，通过一趟排序将待排序列分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序，递归地以达到整个序列有序的目的。
快速排序的三个步骤
(1)选择基准：在待排序列中，按照某种方式挑出一个元素，作为 “基准”（pivot）
(2)分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大
(3)递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。
选择基准的方式
方式1 固定位置(书本上介绍的内容)
快速排序采用的是分治思想：下面我先拿一个来举例子:
1:先定义两个下标，low下标和high下标，low下标指向0下标处，high下标指向9下标处，此时这个low对应的值6就是我们的基准值.我们把这个基准值待会先放到tmp变量当中.
2.然后开始从后向前寻找比6小的数字, 此时5比6小，就把5给我们的low
3:然后从前向后开始寻找比6大的数字，此时low指向了我们的7,就把7放到high所在的位置.
4.然后让high继续往前走，走到了6下标的位置，发现6下标的4要比基准值6小，就把4放到low的位置处，然后low继续往后走，走到了4下标处.
5:然后此时9大于6，就将9放到high所指向的位置处.
6:然后high继续往前走到了5下标处，此时的3小于6，所以将3这个数字放到我们的low所指向的位置:
7.然后low此时指向了high所指向的位置，那么我们将这个6这个基准放到这个下标处：此时pivot指向我们的基准.
此时我们会发现6左边的元素都是比自己小的元素，6右边的元素都是比自己大的元素.从而这个时候就可以采用分治的思想了
8：先对6的左边采用分治思想
此时high指向pivot-1,low指向第一个元素然后先对6左边的区域进行分治
9：对于左边的区域的思想跟刚才的思想其实是一样的，拿出一个基准值5，然后从左到右找比5大的数字，从右到左找比5小的数字，交换方式还是跟刚才的方式相同，这里就不再做过多的赘述.，最后的结果如下：
10.然后low指向0下标处，high指向privot-1,也就是新的位置(下标3处)
11.然后继续进行调整，调整完毕后如下所示:
12.此时继续往下走，将low调整到0下标处，将high调整到1下标处，然后再进行调整,此时我们6的左区间排序完毕.
13.此时我们对6的左边的区间全部排序完毕，按照相同的做法对6右边的区间全部进行一遍排序，方法还是跟之前一样，low指向9，high指向8，然后重复之前的操作便可以完成排序.
在这里分治的思想其实就是对左右区间做之前相同的排序操作.只不过每次需要找到我们的基准值.
其实快速排序的核心思想就是寻找我们的基准，然后再对这个基准的左右区间采用分治的思想，所以整体来说，思想跟二叉树的前序遍历是一个思想，所以其实可以将这个过程转换为二叉树遍历的写法来编写我们快速排序的代码.
代码示例
public class MapDemo1 { //pivot方法的作用就是对每趟的数组进行对应的排序和寻找我们最终的基准值 //pivot方法是我们的核心方法 public static int pivot(int[] array, int start, int end) { int tmp = array[start]; while (start < end) { //注意这里有两个判断条件，条件1 start<end是针对当我们使用我们的end是不能超过start的，否则就数组越界了 //第二点就是我们从右往左找是要寻找比当前tmp中的值小的元素的，所以判断条件要注意. //并且要注意的是，假设此时我们的tmp中的值与array[end]中的值相等的话，此时end也是要往前--的，所以最终我们的array[end]要>=tmp,不要忘记等号 while (start < end && array[end] >= tmp) { end--; } //假设此时end不再往左--且start<end的时候，说明找到了比tmp小的数字，则进行交换 array[start] = array[end]; //这里的两个判断条件以及原因跟上述相同 while (start < end && array[start] <= tmp) { start++; } //假设此时start不再往右++且start<end的时候，说明找到了比tmp大的数字，则进行交换 array[end] = array[start]; } //最后start下标会与我们的end下标重合，代表这一趟的快排结束了，此时需要将tmp中的值赋给我们的array[start] array[start] = tmp; //此时我们start和end重合的位置就是我们每一趟排序的基准,返回start return start; } //时间复杂度空间复杂度在quick方法这里看 public static void quick(int[] array, int low, int high) { if (low < high) { //先对原数组进行一遍排序后找到第一个基准值 int piv = pivot(array, low, high); //以这个基准值为准开始先对这个基准值的左空间进行排序 //使用递归 quick(array, low, piv - 1); //以这个基准值为准开始再对这个基准值的右空间进行排序 quick(array, piv + 1, high); } } //快速排序quickSort方法 public static void quickSort(int[] array) { quick(array, 0, array.length - 1); } public static void main(String[] args) { int[] array = {12, 5, 9, 16, 6, 23, 1, 45, 24, 13}; quickSort(array); System.out.println(Arrays.toString(array)); } }
性能分析
注意：时间复杂度，空间复杂度在quick方法这里看
最好的时间复杂度为O(nlogn)的原因就是因为快速排序算法的时间复杂度一般为递归的次数乘以我们当前遍历的次数,递归的次数就相当于我们递归左右区间的次数，相当于一个二叉树的遍历，而这个递归的次数又跟我们二叉树的高度有关，所以说递归的次数相当于二叉树的高度为logn,而我们遍历的次数就是n次，因为每递归一次遍历的次数都是n次，所以最好情况下的快排的时间复杂度为O(nlogn).
而最坏情况下的时间复杂度为O(N^2),前提是这个需要采用快速排序的数组是一个有序的数组：例如1，2，3，4，5，6，7，8.
ok,到了这里我们就可以对这种有序的情况去进行优化:此时就有以下种方式去进行优化
方式2 随机选取基准(不重要)
引入的原因：在待排序列是部分有序时，固定选取枢轴使快排效率底下，要缓解这种情况，就引入了随机选取枢轴
做法：就是随机找到后边的一个下标，然后和low下标的数据进行交换，最后以low下标交换后的值作为基准
方式3 三数取中（median-of-three）(优化有序的数据)
三数取中法就是找到这组数据的第一个，最后一个以及中间数据，这三个数据对应的下标分别为low,high,mid,最终我们是要保证array[mid] <= array[low] <= array[end]，也就是说假设一个有序的数组1，2，3，4，5，6，7，8.此时拿我们的三数取中法的话，一开始的基准值为array[3] = 4,不再是1，所以一开始假如我们的array[low] array[high]也需要进行交换，假如array[mid] > array[high]的话，也同样需要进行交换.下面来看代码:
代码示例
假设此时我们不使用三数取中法的话，来看我们针对1万个数字的排序时间：
public class MapDemo1 { public static int pivot(int[] array, int start, int end) { //一开始的基准值等于数组的第一个元素 int tmp = array[start]; while (start < end) { //注意这里有两个判断条件，条件1 start<end是针对当我们使用我们的end是不能超过start的，否则就数组越界了 //第二点就是我们从右往左找是要寻找比当前tmp中的值小的元素的，所以判断条件要注意. //并且要注意的是，假设此时我们的tmp中的值与array[end]中的值相等的话，此时end也是要往前--的，所以最终我们的array[end]要>=tmp,不要忘记等号 while (start < end && array[end] >= tmp) { end--; } //假设此时end不再往左--且start<end的时候，说明找到了比tmp小的数字，则进行交换 array[start] = array[end]; //这里的两个判断条件以及原因跟上述相同 while (start < end && array[start] <= tmp) { start++; } //假设此时start不再往右++且start<end的时候，说明找到了比tmp大的数字，则进行交换 array[end] = array[start]; } //最后start下标会与我们的end下标重合，代表这一趟的快排结束了，此时需要将tmp中的值赋给我们的array[start] array[start] = tmp; //此时我们start和end重合的位置就是我们每一趟排序的基准 return start; } public static void quick(int[] array, int low, int high) { if (low < high) { //然后再开始排序和找基准值 int piv = pivot(array, low, high); //对左序列进行快速排序 quick(array, low, piv - 1); //对右序列进行快速排序 quick(array, piv + 1, high); } } public static void quickSort(int[] array) { quick(array, 0, array.length - 1); } public static void main(String[] args) { int[] array = new int[1_0000]; for (int i = 0; i < array.length; i++) { array[i] = i; } long startTime = System.currentTimeMillis(); quickSort(array); long endTime = System.currentTimeMillis(); System.out.println(endTime - startTime); } }
运行时间为13s
再来看我们使用三数取中法后：
public class MapDemo1 { public static void swap(int[] array, int k, int i) { int tmp = array[k]; array[k] = array[i]; array[i] = tmp; } /** * 三数取中法medianOfThree * @param array * @param low * @param high */ public static void medianOfThree(int[] array, int low, int high) { int mid = (low + high) / 2; //我们的目标是要保证后面的关系：array[mid] <= array[low] <= array[end] //array[mid] <= array[low] if (array[low] < array[mid]) { swap(array, low, mid); } //array[low] <= array[high] if (array[low] > array[high]) { swap(array, low, high); } //array[mid] <= array[high] if (array[mid] > array[high]) { swap(array, mid, high); } } public static int pivot(int[] array, int start, int end) { //一开始的基准值等于数组的第一个元素 int tmp = array[start]; while (start < end) { //注意这里有两个判断条件，条件1 start<end是针对当我们使用我们的end是不能超过start的，否则就数组越界了 //第二点就是我们从右往左找是要寻找比当前tmp中的值小的元素的，所以判断条件要注意. //并且要注意的是，假设此时我们的tmp中的值与array[end]中的值相等的话，此时end也是要往前--的，所以最终我们的array[end]要>=tmp,不要忘记等号 while (start < end && array[end] >= tmp) { end--; } //假设此时end不再往左--且start<end的时候，说明找到了比tmp小的数字，则进行交换 array[start] = array[end]; //这里的两个判断条件以及原因跟上述相同 while (start < end && array[start] <= tmp) { start++; } //假设此时start不再往右++且start<end的时候，说明找到了比tmp大的数字，则进行交换 array[end] = array[start]; } //最后start下标会与我们的end下标重合，代表这一趟的快排结束了，此时需要将tmp中的值赋给我们的array[start] array[start] = tmp; //此时我们start和end重合的位置就是我们每一趟排序的基准 return start; } public static void quick(int[] array, int low, int high) { if (low < high) { //先使用三数取中法 medianOfThree(array, low, high); //然后再开始排序和找基准值 int piv = pivot(array, low, high); //对左序列进行快速排序 quick(array, low, piv - 1); //对右序列进行快速排序 quick(array, piv + 1, high); } } public static void quickSort(int[] array) { quick(array,0,array.length-1); } public static void main(String[] args) { int[] array = new int[1_0000]; for (int i = 0; i < array.length; i++) { array[i] = i; } long startTime = System.currentTimeMillis(); quickSort(array); long endTime = System.currentTimeMillis(); System.out.println(endTime-startTime); } }
我们会发现此时运行的时间为1s.
方式4
快速排序在一直执行的过程中是逐渐趋于有序的，那么对于逐渐趋于有序的数字来说使用直接插入排序会更加的提升效率.
我们在方式3的基础上再进行一次优化，当high与low的距离小于50的时候，这时候我们的数组一定是趋于有序的数组了，所以可以直接使用直接插入排序对我们的代码进行优化
优化前:假设此时我们不使用直接插入排序的话：我们拿方式3中的代码对100万条数据排序的耗时是17s
优化后:使用直接插入排序后的算法的耗时是10s
public class MapDemo1 { public static void swap(int[] array, int k, int i) { int tmp = array[k]; array[k] = array[i]; array[i] = tmp; } /** * 三数取中法medianOfThree * * @param array * @param low * @param high */ public static void medianOfThree(int[] array, int low, int high) { int mid = (low + high) / 2; //我们的目标是要保证后面的关系：array[mid] <= array[low] <= array[end] //array[mid] <= array[low] if (array[low] < array[mid]) { swap(array, low, mid); } //array[low] <= array[high] if (array[low] > array[high]) { swap(array, low, high); } //array[mid] <= array[high] if (array[mid] > array[high]) { swap(array, mid, high); } } public static int pivot(int[] array, int start, int end) { //一开始的基准值等于数组的第一个元素 int tmp = array[start]; while (start < end) { //注意这里有两个判断条件，条件1 start<end是针对当我们使用我们的end是不能超过start的，否则就数组越界了 //第二点就是我们从右往左找是要寻找比当前tmp中的值小的元素的，所以判断条件要注意. //并且要注意的是，假设此时我们的tmp中的值与array[end]中的值相等的话，此时end也是要往前--的，所以最终我们的array[end]要>=tmp,不要忘记等号 while (start < end && array[end] >= tmp) { end--; } //假设此时end不再往左--且start<end的时候，说明找到了比tmp小的数字，则进行交换 array[start] = array[end]; //这里的两个判断条件以及原因跟上述相同 while (start < end && array[start] <= tmp) { start++; } //假设此时start不再往右++且start<end的时候，说明找到了比tmp大的数字，则进行交换 array[end] = array[start]; } //最后start下标会与我们的end下标重合，代表这一趟的快排结束了，此时需要将tmp中的值赋给我们的array[start] array[start] = tmp; //此时我们start和end重合的位置就是我们每一趟排序的基准 return start; } //插入排序 public static void insertSortBount(int[] array, int low, int high) { for (int i = low + 1; i <= high; i++) { int tmp = array[i]; int j = i - 1; for (; j >= low; j--) { if (array[j] > tmp) { array[j + 1] = array[j]; } else { break; } } array[j + 1] = tmp; } } public static void quick(int[] array, int low, int high) { if (low >= high) { return; } //对距离为50以内的实行插入排序 if (high - low + 1 <= 50) { //使用插入排序 insertSortBount(array, low, high); //记着这里一定要return 这里说明 这个区别范围有序了 直接结束 return; } //先使用三数取中法 medianOfThree(array, low, high); //然后再开始排序和找基准值 int piv = pivot(array, low, high); //对左序列进行快速排序 quick(array, low, piv - 1); //对右序列进行快速排序 quick(array, piv + 1, high); } public static void quickSort(int[] array) { quick(array, 0, array.length - 1); } public static void main(String[] args) { int[] array = new int[100_0000]; for (int i = 0; i < array.length; i++) { array[i] = i; } long startTime = System.currentTimeMillis(); quickSort(array); long endTime = System.currentTimeMillis(); System.out.println(endTime - startTime); } }
归并排序
概念
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
原理讲解
其实关于分割其实非常好理解，因为分割其实就是拆分，而我们归并的原理是这样的，当我们已经拆分完毕后就必须开始使用归并了，归并的时候是这样进行归并的
1：假如此时我们要归并下面的数组，就需要分别再两个数组内部定义一个s1,e1,s2,e2,s1和s2分别指向我们两个需要归并的数组的头，e1和e2分别指向我们两个需要归并的数组的尾
2:然后开始向后遍历，此时如果s1>s2，就把s2先放入到我们的tmp数组当中去，然后说s2往后走一步
3：然后再比较s1和s2，发现s1
4:然后继续比较s1和s2的大小，发现s1>s2,于是7入数组，s2向后移动
此时s2>e2了，说明第二段已经没有数据了，没有数据的话就将第一段剩下的值全部放入我们的tmp数组当中去.
此时1，6，7，10完成了排序.
代码示例
注意代码中的注释：里面写出了为什么要那么做
import java.util.Arrays; public class MapDemo1 { public static void merge(int[] array, int start, int mid, int end) { //s1的值就是递归进入的时候的start下标，而s2的值就是递归进入的时候的mid+1，e1就是mid,e2是end int s1 = start; int s2 = mid + 1; //注意我们数组最终大小为end-start+1 int[] tmp = new int[end - start + 1]; //k代表tmp数组的下标 int k = 0; while (s1 <= mid && s2 <= end) { if (array[s1] <= array[s2]) { //注意这里是小于等于，因为归并两个有序组的时候，s1和s2指向的数字可能是相同的，而为了保证s1所指向的数字在最终插入到tmp数组的时候是在s2所指向的数字的前面的，要小于等于 //而这个小于等于也保证了最终的我们的归并排序是一个稳定的排序 tmp[k++] = array[s1++]; } else { tmp[k++] = array[s2++]; } } //此处代表第一段还有数据，但是第二段没有数据了 while (s1 <= mid) { //那就将第二段中的剩余数据插入tmp当中 tmp[k++] = array[s1++]; } //此处代表第二段还有数据，但是第一段没有数据了 while (s2 <= end) { //那就将第一段中的剩余数据插入到tmp当中去 tmp[k++] = array[s2++]; } for (int i = 0; i < tmp.length; i++) { //注意这里我们将排序好的数组现在要归并到原数组当中去了，但是有个问题就是该怎样按照顺序将排序好的元素替换到原数组当中去，有些同学想了，那这个简单了直接使用array[i]=tmp[i] //但是注意这样的写法是错误的，原因是当我们左区间递归合并完毕后是没有问题的，但是假如到了右边呢？此时如果还是array[i]=tmp[i]相当于原数组对应的左区间的元素都被替换了，原数组右边的元素还是没有被替换 // array[i + start] = tmp[i]; } } //时间复杂度和空间复杂度需要看我们的mergeSortInternal方法 public static void mergeSortInternal(int[] array, int low, int high) { if (low >= high) { return; } int mid = (low + high) / 2; mergeSortInternal(array, low, mid); mergeSortInternal(array, mid + 1, high); //合并的操作 merge(array, low, mid, high); } public static void mergeSort(int[] array) { mergeSortInternal(array, 0, array.length - 1); } public static void main(String[] args) { int[] array = new int[1_0000]; for (int i = 0; i < array.length; i++) { array[i] = i; } mergeSort(array); System.out.println(Arrays.toString(array)); } }
下面是对代码的部分图示讲解：
性能分析
至于为什么是稳定排序代码里面已经有了注释，这里就不再做过多的赘述，但是要注意的一点是,空间复杂度为O(N）是因为我们在merge方法中定义了一个大小为N的tmp的数组去存储排序后的元素.,而时间复杂度为O(N*log(N))的原因是mergeSortInternal方法中我们既有递归方法也有merge中对于元素的遍历,归并排序算法的时间复杂度一般为递归的次数乘以我们当前遍历的次数.
海量数据的排序问题
外部排序：排序过程需要在磁盘等外部存储进行的排序前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
1.先把文件切分成 200 份，每个 512 M
2.分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3.进行 200 路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
这块只需要知道思想，可以给面试官说出来，代码不需要掌握.
排序的总结
此时假设规定只能使用空间复杂度为O(1) 的算法的话，那就只能堆排序
如果要保证排序最快的话就使用快排
然后最主要掌握的是堆排序，快速排序以及归并排序，希尔排序不用掌握，然后前三个排序是基础.
