面试必须要知道的常见排序算法

以下排序均为升序

---

1.直接插入排序 

具体思想

把待排序的数据按大小比较插入到一个已经排序好的有序序列中,直到所有的待排序数据全部插入到有序序列中为止.实际生活中,我们平常斗地主摸牌时,就用到了插入排序的思想.

1. 当插入第n个数据时,前面n-1个数据已经有序;
2. 第n个数据依次与前n-1个数据比较大小,如果遇到比自己大的数x,则数x的位置向后移动一步,直到第一次遇到比自己小的数y停止,然后将这个第n个数据放在数y后面;
3. 如果前n-1个数据都比当前这第n个数据要小,那么这第n个数据就插入到最前面.

代码实现

public void insertSort(int[] array){//第一个数字因为只有自身一个,所以本就是有序的,故待排序的数字下标为[0]~[array-1].依次遍历即可.for(int i=1;i<array.length;i++){int index=i-1;int cur=array[i];while(index>=0){if(cur<array[index]){//如果待插入的数字比当前数字要小,则当前数字向后移动一个位置array[index+1]=array[index];}else{//如果待插入的数字比当前数字要大,则直接插在当前数字的后面,结束循环array[index+1]=cur;break;}index--;}if(index<0){array[0]=cur;}}}

算法特性分析

对于要排序的数组,越接近有序,效率越高.该排序为稳定的排序.

时间复杂度:O(N^2)

空间复杂度:O(1),只借助了常数个变量

---

2. 希尔排序

具体思想

希尔排序又称缩小增量法,是直接插入排序的优化.因为通过直接插入排序我们了解到,数组越接近有序,排序的效率越高.所以希尔排序的大致思想就是先使数组大致有序后,然后再直接插入排序.所以可以将希尔排序理解为直接插入排序的优化.

那怎样做到先将一个数组做到基本有序呢.基本思路如下:

1. 先选定一个gap值(gap<元素个数),然后所有距离为gap的数自动分为一组,然后对每组进行插入排序;
2. 再更新gap的值(比原值要小),然后重复一的操作;
3. 直到gap减小为1,然后数据基本有序了,然后对整组使用直接插入排序.

第三轮排序时,数组已经基本有序了,这时再用直接插入排序效率就很高了.至于这个gap的取值应该怎么取,很多资料也没有一个明确的说法.

以下代码的实现,增量值我就用gap=(n+1)/2,gap=(gap+1)/2,直到gap=1为止 

代码实现

public static void shellSort(int[] array){int gap=(array.length+1)/2;while(gap>1){shell(array,gap);gap=(gap+1)/2;}if(gap==1){shell(array,gap);}}
public static void shell(int[] array,int gap){for (int i = gap; i <array.length ; i++) {int j=i-gap;int cur=array[i];while(j>=0){if(cur<array[j]){array[j+gap]=array[j];}else{array[j+gap]=cur;break;}j=j-gap;}if(j<0){array[j+gap]=cur;}}}

算法特性分析

1. 该排序不稳定.
2. 希尔排序的时间复杂度小于O(N^2),但是具体是多少还不好下定论,与其增量值有关.大概在O(N*1.3)~O(N*1.5)左右
3. 空间复杂度:O(1)

---

3. 选择排序

具体思想

1. 在待排序列表中找最小的数,将这个最小数与第一个位置上的数交换位置,这样这个数就有序了;
2. 在剩余未被排序的元素中找最小值,将其与第二个位置上的数交换位置,这样这个数也有序了;
3. 以此类推,每个数都到了它应该在的位置,自然整个列表就有序了.

代码实现

public static void selectSort(int[] array){for (int i = 0; i <array.length ; i++) {int min=array[i];int index=i;for(int j=i+1;j<array.length;j++){if(min>array[j]){min=array[j];index=j;}}array[index]=array[i];array[i]=min;}
}

算法特性分析

1. 直接选择排序很好理解，但实际效率不高，很少使用,是不稳定的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)

---

4. 堆排序      

调整一颗子树成为大根堆:

比较根节点和左右孩子的最大值,通过交换二者的位置保证根节点的值比左右子树都大;

如果根节点与孩子节点未发生交换,说明该子树本身就是大根堆;

如果根节点与孩子节点发生过交换,则需要判断交换后的以孩子节点为根节点的子树是否仍为大根堆,重复1的操作,结束条件为该节点没有孩子节点或不需要发生交换.

 

/**    * 向下调整子树* @param array  * @param parent 需要调整子树的根节点位置* @param end  该子树的最后一个叶子节点的位置*/ 
private static void shiftDown(int[] array, int parent, int end) {int child=parent*2+1;while(child<=end){//说明有孩子,找到左右孩子的最大值if(child+1<=end&&array[child]<array[child+1]){child++;}//此时child下标保存的是左右孩子最大值的下标//将根节点与孩子的最大值做比较if(array[parent]<array[child]){int tmp=array[parent];array[parent]=array[child];array[child]=tmp;parent=child;//开始更新下标,继续看下面的子树是不是大根堆child=parent*2+1;}else{break;}}}

建堆思想:

1).从最后一颗子树开始调整,使这颗子树成为大根堆

• 确定最后一颗子树的根节点p的下标:  p=(len-1-1)/2     

2).调整完这颗子树后,找到下一棵树的根节点(p--),然后重复1的操作.

3).直到调整完0下标这棵树就结束了.

 具体思想

 1.建大根堆    

//1.建大根堆(对每颗子树进行向下调整)
for(int i=(array.length-1-1)/2;i>=0;i--){shiftDown(array,i,array.length-1);
}

 2.交换大根堆的第一个元素与最后一个元素的位置,然后将数组下标为[0]~[length-1]的所有元素进  行向下调整,使其成为大根堆.

 3.再次交换大根堆的第一个元素与大根堆的最后一个元素(即列表倒数第二个元素的位置),然后再将数组下标为[0]~[length-2]的所有元素进行向下调整,使其成为大根堆.

 4.以此类推,每次构成大根堆的元素都会减少一个,直到大根堆的元素减少到只有一个时,数组排序完成.

代码实现

    public static void heapSort(int[] array){//1.建大根堆(对每颗子树进行向下调整)for(int i=(array.length-1-1)/2;i>=0;i--){shiftDown(array,i,array.length-1);}//2.将大根堆的第一个元素与最后一个元素交换位置,然后继续向下调整,直到大根堆只剩一个元素for (int i = array.length-1; i >0 ; i--) {int tmp=array[i];array[i]=array[0];array[0]=tmp;shiftDown(array,0,i-1);}}/*** 向下调整子树* @param array* @param parent 需要调整子树的根节点位置* @param end  该子树的最后一个叶子节点的位置*/private static void shiftDown(int[] array, int parent, int end) {int child=parent*2+1;while(child<=end){//说明有孩子,找到左右孩子的最大值if(child+1<=end&&array[child]<array[child+1]){child++;}//此时child下标保存的是左右孩子最大值的下标//将根节点与孩子的最大值做比较if(array[parent]<array[child]){int tmp=array[parent];array[parent]=array[child];array[child]=tmp;parent=child;//开始更新下标,继续看下面的子树是不是大根堆child=parent*2+1;}else{break;}}}

特性分析

1. 堆排序使用堆来选择元素,使效率高了不少.是不稳定排序
2. 时间复杂度:O(N*logN)
3. 空间复杂度:O(1)

---

5. 冒泡排序

具体思想

1. 将下标为0的元素与下标为1的元素进行比较
2. 若下标为0的元素大于下标为1的元素,则交换二者位置;反之则不用交换.
3. 将下标为1的元素与下标为2的元素进行比较
4. 重复2的操作
5. 以此类推,直到将数组的最后一个元素与其前一个元素进行大小比较,交换位置之后,结束本轮循环.此时,最后一个元素就是待排序数组中的最大值,已经有序.
6. 除去已经有序的元素,将剩余的元素进行1-5的操作,直到数组元素全部有序

代码实现

  public static void bubbleSort(int[] array){int len=array.length;//每一趟排序都会使最后一个元素有序for(int i=0;i<len;i++){//使最后一个元素有序for(int j=0;j<len-1-i;j++){if(array[j]>array[j+1]){//当前者比后者大时,交换二者位置int tmp=array[j];array[j]=array[j+1];array[j+1]=tmp;}}}}

但是以上代码效率低下,因为当数组不管是否有序,按照该代码始终都会进行len趟的循环,每一趟使一个元素有序.如果数组在len趟之前就已经有序,那代码依然会走完这len趟,而正常情况下,我们希望数组有序后就结束.对于这个缺陷,可以将代码做一下优化:

   public static void bubbleSort(int[] array){int len=array.length;boolean flag=true;//每一趟排序都会使最后一个元素有序for(int i=0;i<len;i++){flag=false;//使最后一个元素有序for (int j = 0; j < len - 1 - i; j++) {if (array[j] > array[j + 1]) {flag = true;//当前者比后者大时,交换二者位置int tmp = array[j];array[j] = array[j + 1];array[j + 1] = tmp;}}//一趟结束之后,发现flag没有被修改,说明此时数组已经有序,可以退出了if(!flag){break;}}}

特性分析

1. 非常容易理解的排序,是稳定排序
2. 时间复杂度:O(N^2)
3. 空间复杂度:O(1)

---

6.快速排序

具体思想

1. 先从待排序数组中选取最左端作为一个基准值(也可以选取最右端),然后通过"某一方法"找到它应该在的位置(即代码最终有序时它所在的位置),这样该位置的左边均小于等于这个基准值,右边均大于等于这个基准值.此时,我们可以理解为这个位置将这个待排序数组分成了左右两个子序列.而我们的接下来就是让这左右两个子序列分别有序.
2. 再将左子序列作为待排序数组,重复1的操作,直到所有值都在其对应位置上为止.
3. 右子序列的处理方法与左子序列相同.

伪代码如下(partition方法即为上述中的"某一方法")：

   private static void quick(int[] array, int left, int right) {if(left>=right)return;//找基准值int pivot=partition(array,left,right);//递归的找左右子序列的基准值quick(array,left,pivot-1);quick(array,pivot+1,right);}

以上提到的"某一方法"是什么呢，也就是如何将最左端的值在它应该放的位置.在这里我将介绍两种方法:Hoare法和挖坑法.

Hoare法思路:

1. 先用left指向最左端元素,right指向最右端数据.选取最左边作为key值(基准值).
2. 将right所指的数与key值做比较,大于key则right向左走一步(right--),再次进行比较,直到找到比key值小的数停下来;
3. 将left所指的数与key值做比较,小于key则left向右走一步(left++),再次进行比较,直到找到比key值大的数停下来;
4. 重复2和3的操作，直到right和left相遇，交换最左边位置上的key值与相遇位置上的数，此时key值(基准值)的位置就确定了。

注意看,最后key值8最后放在了它应该在的位置.也就是它的左边元素均小于它,右边元素均大于它 

代码实现

    /*** 确定基准值的位置* @param array* @param left* @param right* @return*/private static int partition(int[] array, int left, int right) {int tmp=array[left];int start=left;while(left<right){while(left<right&&array[right]>=tmp){right--;}while(left<right&&array[left]<=tmp){left++;}int cur=array[right];array[right]=array[left];array[left]=cur;}array[start]=array[left];array[left]=tmp;return  left;}

挖坑法思路：

挖坑法和Hoare法有点相似。选取最左边位置为坑，将其坑中的值保存到key中，然后依次左边找小，右边找大，找到后放入坑中。直到左右相遇，将key值放入坑中，此时key值有序，即基准值位置确定。具体思路如下图：

    private static int partition(int[] array, int left, int right) {int key=array[left];while(left<right){while(left<right&&array[right]>=key){right--;}array[left]=array[right];while (left<right&&array[left]<=key){left++;}array[right]=array[left];}array[left]=key;return left;}

整体代码实现

    public static void quickSort(int[] array){quick(array,0,array.length-1);}private static void quick(int[] array, int left, int right) {if(left>=right)return;int pivot=partition2(array,left,right);quick(array,left,pivot-1);quick(array,pivot+1,right);}//用挖坑法来找基准值private static int partition2(int[] array, int left, int right) {int key=array[left];while(left<right){while(left<right&&array[right]>=key){right--;}array[left]=array[right];while (left<right&&array[left]<=key){left++;}array[right]=array[left];}array[left]=key;return left;}

---

快速排序的优化

为什么要对快速排序进行优化,其实我们分析一下它的时间复杂度就知道,在找基准值的位置时,我们都会将该序列分为左右两个子序列,左边比基准值小,右边比基准值大.然后去找左子序列基准值的位置,又将这个左子序列分为左右两个子序列,一直递归下去,直到只有一个值,无法分为左右子序列为止.就很像二叉树遍历一样,一直到没有左右子树.接着对有子序列做同样的操作.所以它的时间复杂度是O(N*logN).但是,有没有想过,如果当待排序数组本身就有序的话,再用这个方法排序的话,效率将会非常低下了.因为如果还是将最左端的值当做基准值去找它的位置的话,就不会同时有左右子序列了,那这个结构就像下图这样:

高度为n,那么时间复杂度就变成了O(N*N),就跟冒泡排序差不多了.这很显然不是我们想要看到的结果.我们理想中的结果是,最左边的那个基准值的位置在待排序数组中的中间位置,这样才能保证同时有左右子序列,这样时间复杂度才是O(N*logN).

那我们怎样进行优化呢?搞清楚问题我们才能对症下药,导致快排时间复杂度变为O(N^2)的情况,是因为在数组有序情况下,我们在将最左边作为基准值,去找它对应的位置时,这个基准值的位置就在边上,导致左右子序列元素个数相差很大甚至最后全部呈以上图所示的情况.而理想情况下,应该是基准值的位置刚好将待排序数组分为元素个数相差无几的左右两个序列.所以解决办法是,选取最左边的数为基准值,而这个基准值最终会放在靠中间的位置,将数组分为左右两个元素个数相差无几子序列.因此我们可以用三数取中法.

三数取中法思路： 

将子序列中最左端、最右端、和中间位置上的三个数相互比较大小，使第二大的数放在最左端，这时，选取最左端作为基准值，然后去找它所在的位置，这样就能确保它所在的位置能将该序列分为左右两个子序列了。

此时优化后的完整快排如下：

 public static void quickSort(int[] array){quick(array,0,array.length-1);}private static void quick(int[] array, int left, int right) {if(left>=right)return;int pivot=partition3(array,left,right);quick(array,left,pivot-1);quick(array,pivot+1,right);}private static int partition3(int[] array, int left, int right) {//选取从最左、最右、中间选取中间大小的值int midIndex=getMidIndex(array,left,right);//将中间大小的值与最左边的值换位置。int tmp=array[left];array[left]=array[midIndex];array[midIndex]=tmp;//用挖坑法找基准值的位置int key=array[left];while(left<right){while(left<right&&array[right]>=key){right--;}array[left]=array[right];while (left<right&&array[left]<=key){left++;}array[right]=array[left];}array[left]=key;return left;}//三数取中private static int getMidIndex(int[] array, int left, int right) {int mid=(left+right)>>>2;if(array[left]<array[right]){if(array[mid]<array[left]){return left;}else if(array[mid]>array[right]){return right;}else{return mid;}}else{if(array[mid]>array[left]){return left;}else if(array[mid]<array[right]){return right;}else{return mid;}}}

此时该排序的时间复杂度为O(N*logN)，空间复杂度为O(N）.不稳定排序.

---

7.归并排序

具体思想

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。将两个有序表合并成一个有序表，称为二路归并。

但是以上情况是比较理想的情况，我们在合并的时候恰好是两两一组，这与元素个数紧密关系，但是在普遍情况下，拆分后合并时会有以下各种各样的情况，比如：

代码实现

 public static void mergeSort(int[] array){int gap=1;int len=array.length;int[] tmp=new int[len];while(gap<len) {int index=0;for (int i = 0; i < array.length; i += 2 * gap) {int s1 = i;int e1 = i + gap - 1;int s2 = e1 + 1;int e2 = s2 + gap - 1;//e1,s1,e2都有可能越界,所以要针对不同情况对e1,s1,s2做出调整//e1或s1越界，则不需要合并if (e1 >=len||s1>=len){break;}//e2越界if(e2>=len){e2=len-1;}//开始合并while(s1<=e1&&s2<=e2){if(array[s1]<=array[s2]){tmp[index++]=array[s1];s1++;}else{tmp[index++]=array[s2];s2++;}}while(s1<=e1){tmp[index++]=array[s1++];}while(s2<=e2){tmp[index++]=array[s2++];}//把归并好的部分赋值给原数组for(int j=0;j<=e2;j++){array[j]=tmp[j];}}gap*=2;}}

算法特性分析

1. 该排序为稳定排序。
2. 时间复杂度：O(N*longN)   空间复杂度：O(N).
3. 归并的缺点在于需要O(N)的空间复杂度，归并排序用的更多的是解决在磁盘中的外部排序问题

外部排序：排序过程需要借助磁盘的外部存储进行的排序。

比如进行海量数据排序时，需要对100G的数据进行排序，但是内存只有1G。我们就可以用归并排序了.

因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序,大致思路如下

1. 先把文件切分成 200 份，每个 512 M
2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3.  进行二路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
    

总结：