常见排序算法总结

本文最后更新于：2024年5月11日上午

定义

先看一下维基百科关于排序算法的定义

一个排序算法（英语：Sorting algorithm）是一种能将一串数据依照特定排序方式进行排列的一种算法。最常用到的排序方式是数值顺序以及字典顺序。有效的排序算法在一些算法（例如搜索算法与合并算法）中是重要的，如此这些算法才能得到正确解答。排序算法也用在处理文字数据以及产生人类可读的输出结果。基本上，排序算法的输出必须遵守下列两个原则：

输出结果为递增序列（递增是针对所需的排序顺序而言）

输出结果是原输入的一种排列、或是重组

排序可以说是数据结构与算法中最基础最重要的东西了。

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

可以将其分为两大类：

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动图演示

特殊情况

元素正序时最快，反序时最慢

实现代码

package SortAlgorithm;

/**
 * @Author: Salute61
 * @Date: 2020/8/23 19:46
 * @Description: 冒泡排序的基本思想就是重复的遍历要排序的序列，对元素两两一次比较
 *               平均时间复杂度O(n^2)，最好情况O(n)就是序列已经有序了，最坏就是O(n^2)
 **/
public class BubbleSort {
    private static void exch(int[] a,int i,int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    private static void show(int[] a){
        for(int i=0;i<a.length;i++)
            System.out.print(a[i]+" ");
        System.out.println("本次结束！");
    }
    private static void sort(int[] a){
        for(int i=0;i<a.length-1;i++){
            for(int j=0;j<a.length-1;j++){
                if(a[j]>a[j+1])
                    exch(a,j,j+1);
            }
            show(a);
            System.out.println();
        }
    }
    public static void main(String[] args){
        System.out.println("初始数组：");
        int[] a = {12,6,58,92,55,33,10,38};
        sort(a);
    }
}

代码的输出结果：可以看到每次排序都会有一个值有序（即当前无序部分的最大值）

冒泡排序优化

上面的冒泡排序是基本思想的实现代码，看图就会发现第五次排序后就已经有序了，但是只要i没到a.length就会继续，所以可以进行一点优化：

参考别人的思路，通过设置标志位flag，判断第i趟是否有元素交换，没有说明已经有序了
编写一个判断函数isSorted()，遍历数组看是否有序了，相比设置flag的花销会更大

//flag的思路就是出现了交换，flag就翻转表示还未完全有序，思路很简单
    private static void sort(int[] a){
        for(int i=0;i<a.length-1;i++){
            int flag = 1;//每次遍历设置，设置在外面就没用了
            for(int j=0;j<a.length-1;j++){
                if(a[j]>a[j+1]) {
                    exch(a,j,j+1);
                    flag = 0;
                }
            }
            show(a);
            //因为是当前遍历设置的，遍历完判断，所以会多输出一次
            if(flag == 1)
                break;
        }
    }
//这里是遍历一下数组
public static int isSorted(int[] a){
        for(int i=1;i<a.length-1;i++){
            if(a[i]<a[i-1])
                return -1;
        }
        return 1;
    }

运行结果：

选择排序

选择排序是一种简单直观的排序算法，非常稳定，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。

动图演示

实现代码

package SortAlgorithm;

/**
 * @Author: Salute61
 * @Date: 2020/8/23 21:32
 * @Description: 选择排序就是把a[i]和a[i+1...a.length-1]中最小的交换
 *               可以理解为：整个序列分为有序和无序两组；一开始有序组为空，无序组就是全部序列
 *               每次就在无序组中找最小的元素，放到有序组
 *               时间复杂度一直是O(n^2)
 **/
public class SelectionSort {
    private static void exch(int[] a,int i,int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    private static void show(int[] a){
        for(int i=0;i<a.length;i++)
            System.out.print(a[i]+" ");
        System.out.println("本次结束！");
    }
    private static void sort(int[] a){
        for(int i=0;i<a.length;i++){
            int min = i;
            for(int j=i+1;j<a.length;j++){
                if(a[j]<a[min])
                    min = j;
            }
            exch(a,i,min);
            show(a);
        }
    }
    public  static void main(String[] args){
        int[] a = {12,6,58,92,55,33,10,38};
        sort(a);
    }
}

一个优化的思路也是可以用isSorted判断

插入排序

插入排序原理就像打扑克牌，每次将一张牌插入到已经有序的牌组的合适位置。为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。

与选择排序一样，当前索引左边的所有元素都是有序的，但它们的最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动。但是当索引到达数组的右端时，数组排序就完成了。

插入排序针对小规模数据或基本有序数据效率较高

算法步骤

将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

动图演示

实现代码

package SortAlgorithm;

/**
 * @Author: Salute61
 * @Date: 2020/8/23 21:45
 * @Description: 插入排序就是将第i个位置元素插入前面已经有序的序列中
 *               默认第一个元素已经有序了
 *               插入方法是逐个与前面的元素比较,两两比较交换,直到找到合适的位置
 *               平均时间复杂度O(n^2)，最好情况下已经有序一遍,遍历就结束了O(n)
 **/
public class InsertionSort {
    private static void exch(int[] a,int i,int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    private static void show(int[] a){
        for(int i=0;i<a.length;i++)
            System.out.print(a[i]+" ");
        System.out.println("插排——本次结束！");
    }
    private static void sort(int[] a){
        for(int i=1;i<a.length;i++){
            for(int j=i;j>0&&a[j]<a[j-1];j--){
                exch(a,j,j-1);
            }
            show(a);
        }
    }
    public  static void main(String[] args){
        int[] a = {12,6,58,92,55,33,10,38};
        sort(a);
    }
}

我们要考虑的更一般的情况是部分有序的数组。倒置指的是数组中的两个顺序颠倒的元素。比如 E X A M P L E 中有 11 对倒置：E-A、 X-A、 X-M、 X-P、 X-L、 X-E、 M-L、 M-E、 P-L、 P-E以及 L-E。如果数组中倒置的数量小于数组大小的某个倍数，那么我们说这个数组是部分有序的。下面是几种典型的部分有序的数组：

数组中每个元素距离它的最终位置都不远；
一个有序的大数组接一个小数组；
数组中只有几个元素的位置不正确。

插入排序对这样的数组很有效，而选择排序则不然。事实上，当倒置的数量很少时，插入排序很可能比本章中的其他任何算法都要快。

代码优化

还有一种优化算法，叫做拆半插入。当数据量n很大时直接插入排序就不适宜了，这时折半插入相对效率更高。基本思想是利用二分法方式在已有序的系列中找到待插入的位置

private static void sort(int[] a){
    for(int i=1;i<a.length;i++){
        int low = 0,high=a.length-1,mid;
        while(low<=high){//二分思想循环查找
            mid = low+(high-low)/2;
            if(a[i]<=a[mid])
                high = mid-1;
            else
                low = mid+1;
        }//循环结束后low就是a[i]应该插入的位置
        int tmp = a[i];
        for(int j=i-1;j>=low;j--){
            a[j+1]=a[j];
        }
        a[low] = tmp;
        show(a);
    }
}

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。

可以理解为间隔h个元素比较，例如数组[3,5,1,6,2,4,8,9]：

选择初始h=5为数组一半长度，那么就将序列分为：[3,2]、[5,4]、[1,8]、[6,9]一共4组，每组进行直接插入排序。得到数组[2,4,1,6,3,5,8,9]
然后增量因子变为一半h=2，分为两组[2,1,3,8]、[4,6,5,9]。排序得到[1,2,3,8]、[4,5,6,9]合并[1,4,2,5,3,6,8,9]
然后增量因子h=1，再次插入排序得到有序数组[1,2,3,4,5,6,8,9]

算法步骤

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

动图演示

实现代码

package SortAlgorithm;

/**
 * @Author: Salute61
 * @Date: 2020/8/23 22:18
 * @Description: 希尔排序是对直接插入排序的一个改进
 *               通过设置增量,将原序列按增量大小为间隔分组,对分组内元素直接插入排序
 *               基本取法：增量因子 h = N/2 ; 也可以按照初始值1,通过3*h+1计算直到h刚好不大于数组长度,后续的 h = (h-1)/3
 **/
public class ShellSort {
    private static void exch(int[] a,int i,int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    private static void show(int[] a){
        for(int i=0;i<a.length;i++)
            System.out.print(a[i]+" ");
        System.out.println("shell——本次结束！");
    }
    private static void sort(int[] a){
        //设置增量因子
        int factor = 1;
        while (factor<a.length){
            factor = factor*3 + 1;
        }
        while(factor>=1){
            //对增量分组，分组进行插入排序
            //factor此时是不大于序列长度能取到的最大值,factor到a.length-1就是每个分组中的最大值
            for (int i=factor;i<a.length;i++){
                //可能交换时会覆盖a[i]，所以先存储a[i]
                int tmp = a[i];
                int j;
                //以增量factor为间值对当前分组进行插入排序
                for (j = i-factor;j>=0&&a[j]>tmp;j -= factor){
                    a[j+factor] = a[j];
                }
                //最后的位置放入之前a[i]
                a[j+factor] = tmp;
            }
            factor = (int)Math.floor(factor/3);
            show(a);
        }
    }
    public  static void main(String[] args){
        int[] a = {12,6,58,92,55,33,10,38};
        sort(a);
    }
}

归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
自下而上的迭代；

在《数据结构与算法 JavaScript 描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为：

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

然而，在 JavaScript 中这种方式不太可行，因为这个算法的递归深度对它来讲太深了。

说实话，我不太理解这句话。意思是 JavaScript 编译器内存太小，递归太深容易造成内存溢出吗？还望有大神能够指教。

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

算法步骤

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤 3 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。

动图演示

实现代码

原地归并：

实现归并的一种直截了当的办法是将两个不同的有序数组归并到第三个数组中，方法很简单，创建一个适当大小的数组然后将两个输入数组中的元素一个个从小到大放入这个数组中。（即上面算法步骤所描述的）
但是，当用归并将一个大数组排序时，我们需要进行很多次归并，因此在每次归并时都创建一个新数组来存储排序结果会带来问题。我们更希望有一种能够在原地归并的方法，这样就可以先将前半部分排序，再将后半部分排序，然后在数组中移动元素而不需要使用额外的空间。你可以先停下来想想应该如何实现这一点，乍一看很容易做到，但实际上已有的实现都非常复杂，尤其是和使用额外空间的方法相比。

//原地归并的抽象方法
public static void merge(Comparable[] a,int low,int mid,int high){
    //将a[low...mid]和a[mid+1...high]归并
    int i=low,j=mid+1;
    for(int k=low;k<=high;k++){//将a[low...high]复制到aux[low...high]
        aux[k]=a[k]
    }
    for(int k=low;k<=high;k++){//双指针方法
        //左边取完了
        if	   (i>mid)		          a[k]=aux[j++];
        //右边取完了
        else if(j>high)		          a[k]=aux[i++];
        //右边元素小于左边
        else if(less(aux[j],aux[i]))  a[k]=aux[j++];
        //右边元素大于左边
        else                          a[k]=aux[i++];
    }
}

自底向上迭代法：

自底向上的归并排序会多次遍历整个数组，根据子数组大小进行两两归并。子数组的大小 sz 的初始值为1，每次加倍。最后一个子数组的大小只有在数组大小是 sz 的偶数倍的时候才会等于 sz （否则它会比 sz 小）。

以序列{12,6,58,92,55,33,10,38}为例：

初始步长为1，合并相邻区间10,38

[6,12,58,92,55,33,10,38]、[12,6,58,92,55,33,10,38]、[12,6,58,92,33,55,10,38]、[12,6,58,92,55,33,10,38]
第二次步长为2，合并相邻区间

[6,12,58,92,55,33,10,38]、[12,6,58,92,10,33,38,55]
第三次步长为4，合并相邻区间

[6,10,12,33,38,55,58,92]

package SortAlgorithm;

/**
 * @Author: Salute61
 * @Date: 2020/8/28
 * @Description: 归并排序采用归并操作,是一种典型的分治算法应用,
 *               基本思路就是将两个有序数组归并成一个,所以归并排序就是将序列分成两个子序列排好序合并,子序列同样再分直到有序
 *               常用的归并方式是双指针合并数组,
 *               数组过大时归并占用内存过多,可以考虑原地归并
 */
public class MergeSort {

    private static void exch(int[] a,int i,int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    private static void show(int[] a){
        for(int i=0;i<a.length;i++)
            System.out.print(a[i]+" ");
        System.out.println("merge__本次结束！");
    }
    //将两个有序子序列合并为一个
    public static void merge(int[] a,int low,int mid,int high){
        int[] tmp = new int[a.length];
        //将a[low...mid]和a[mid+1...high]归并
        int i=low,j=mid+1;
        //先将a[low...high]复制到aux[low...high]
        for(int k=low;k<=high;k++){
            tmp[k]=a[k];
        }
        //双指针方法
        for(int k=low;k<=high;k++){
            //左侧取完了
            if	   (i>mid)		          a[k]=tmp[j++];
            //右侧取完了
            else if(j>high)		          a[k]=tmp[i++];
            //两边都有剩余,右边小
            else if(tmp[j]<tmp[i])        a[k]=tmp[j++];
            //左边小
            else                          a[k]=tmp[i++];
        }
    }
    private static void sort(int[] a){
        int N = a.length;
        int[] tmp = new int[N];
        for(int sz=1;sz<N;sz=sz+sz){
            for(int lo=0;lo<N-sz;lo+=sz+sz){
                merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1,N-1));
            }
            show(a);
        }
    }

    public static void main(String[] args){
        int[] a = {12,6,58,92,55,33,10,38};
        sort(a);
    }
}

自顶向下递归法：

要对子数组 a[1o..hi] 进行排序，先将它分为 a[1o..mid] 和 a[mid+1..hi] 两部分，分别通过递归调用将它们单独排序，最后将有序的子数组归并为最终的排序结果。

//将迭代的sort改为递归即可
private static int[] aux;//辅助数组
   public static void sort(int[] a){
       aux = new int[a.length];
       sort(a,0,a.length-1);
       show(a);
   }
   private static void sort(int[] a,int low,int high){
       if(high<=low)	return;
       int mid = low+(high-low)/2;
       sort(a,low,mid);
       sort(a,mid+1,high);
       merge(a,low,mid,high);//上面的merge抽象方法
   }

以N=16为例，对应的递归调用情况：

优化改进

因为递归会使小规模问题中方法的调用过于频繁，所以改进对它们的处理方法就能改进整个算法。对排序来说，我们已经知道插入排序（或者选择排序）非常简单，因此很可能在小数组上比归并排序更快。
我们可以添加一个判断条件，如果 a[mid] 小于等于 a[mid+1] ，我们就认为数组已经是有序的并跳过 merge() 方法。这个改动不影响排序的递归调用，但是任意有序的子数组算法的运行时间就变为线性的了

快速排序

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。在第一种情况中，递归调用发生在处理整个数组之前；在第二种情况中，递归调用发生在处理整个数组之后。在归并排序中，一个数组被等分为两半；在快速排序中，切分（partition）的位置取决于数组的内容。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：

快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

算法步骤

从数列中挑出一个元素，称为 “基准”（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

递归的最底部情形，是数列的大小是零或一。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

动图演示

实现代码

package SortAlgorithm;

/**
 * @Author: Salute61
 * @Date: 2020/8/28 22:30
 * @Description: some description
 */
public class QuickSort {
    private static void exch(int[] a,int i,int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    private static void show(int[] a){
        for(int i=0;i<a.length;i++)
            System.out.print(a[i]+" ");
        System.out.println("本次结束！");
    }
    public static void sort(int[] a, int low, int high){
        if(low>high)
            return;
        int i=low,j=high;
        int povit = a[low];
        while(i<j){
            while(i<j && povit<a[j]){
                j--;
            }
            while(i<j && a[i]<ovit){
                i++;
            }
            if(i!=j){
                exch(a,i,j);
            }
        }
        exch(a,low,i);
        a[i]=povit;
        show(a);
        sort(a,low,i-1);
        sort(a,i+1,high);
    }
    public static void main(String[] args){
        int[] a = {49,38,65,97,76,13,27,49};
        sort(a,0,a.length-1);
    }
}

以数组 a = [49_i，38，65，97，76，13，27，49_j]为例：

基准值v=49；初始指针i=low=0和j=high=5，两个指针是交替进行的，假设先从j开始
<--j向左移动j直到a[j]<v然后赋值a[i]=a[j]，得到[27_i，38，65，97，76，13，27_j，49]；再移动i
i-->向右移动i直到a[i]>v然后赋值a[j]=a[i]，得到[27，38，65_i，97，76，13，65_j，49]；再移动j
<--j向左移动j直到a[j]<v然后赋值a[i]=a[j]，得到[27，38，13_i，97，76，13_j，65，49]；再移动i
i-->向右移动i直到a[i]>v然后赋值a[j]=a[i]，得到[27，38，13，97_i，76，97_j，65，49]；再移动j
<--j向左移动j此时出现i==j，得到[27，38，13，97_i_j，76，97，65，49]；令此时a[i]=49，第一次划分结束，得到[27，38，13，49_i_j，76，97，65，49]，此时满足a[low...j-1] <= a[j] <= a[j+1...high]

代码实现。。。。。。。。27和13位置不对啊。。。。

算法优化

基准选择

对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效率会达到最大。也就是说，基准的选择是很重要的。选择基准的方式决定了两个分割后两个子序列的长度，进而对整个算法的效率产生决定性影响。最理想的方法是，选择的基准恰好能把待排序序列分成两个等长的子序列。

随机基准&三数取中

上面默认的方法采取的是固定基准——即以第一个或最后一个元素为基准。

【固定基准分析】如果输入序列是随机的，处理时间可以接受的。如果数组已经有序时，此时的分割就是一个非常不好的分割。因为每次划分只能使待排序序列减一，此时为最坏情况，快速排序沦为冒泡排序，时间复杂度为Θ(n^2)。而且，输入的数据是有序或部分有序的情况是相当常见的。因此，使用第一个元素作为基准元是非常糟糕的，为了避免这个情况，就引入了随机基准——取待排序列中任意一个元素作为基准元。

1
2
3

Random rd = new Random();
int randomIndex = rd.Next() % (high - low) + low;//取数组中随机下标
exch(a,randomIndex,low);           				 //与第一个数交换

【随机基准分析】：这是一种相对安全的策略。由于基准元的位置是随机的，那么产生的分割也不会总是会出现劣质的分割。在整个数组数字全相等时，仍然是最坏情况，时间复杂度是O(n^2）。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n）。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn）的期望时间复杂度。

虽然随机选取基准时，减少出现不好分割的几率，但是还是最坏情况下还是O(n^2），要缓解这种情况，就引入了三数取中选取基准——从第一项、中间、最后一项三个数中选择中位数作为基准值。如果数据很大，也可以继续延伸到5个甚至更多个

举例：8 1 4 9 0 3 5 2 7 6，取——左8 中0 右6(即low、mid、high位置)，将三个数排序后取中间的数交换到low位置作为基准；这个序列基准值即为6

我们还可以将取样元素放在数组末尾作为“哨兵”来去掉 partition() 中的数组边界测试。

优化一：切换插入排序

和大多数递归排序算法一样，改进快速排序性能的一个简单办法基于以下两点：

虽说插入排序的时间复杂度为O(n2)，但是实际上是：n(n-1)/2。快速排序的时间复杂度为O(nlogn)，实际上是：n(logn+1)。经过计算后发现当n<=8时，插入排序所消耗的时间是少于快速排序的。
因为递归，快速排序的 sort() 方法在小数组中也会调用自己。

因此，在排序小数组时应该切换到插入排序。简单地改动算法代码就可以做到这一点：将sort() 中的语句if (hi <= lo) return;替换成下面这条语句来对小数组使用插入排序：if (hi <= lo + M) { Insertion.sort(a, lo, hi); return; }转换参数 M 的最佳值是和系统相关的，但是 5 ～ 15 之间的任意值在大多数情况下都能令人满意

优化二：处理重复元素

在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割。即将数组分为小于povit、等于povit、大于povit三个分区

举例：

待排序序列 1 4 6 7 6 6 7 6 8 6

三数取中选取基准：下标为4的数6

转换后，待分割序列：6 4 6 7 1 6 7 6 8 6 基准key：6

本次划分后，未对与key元素相等处理的结果：1 4 6 6 7 6 7 6 8 6

下次的两个子序列为：1 4 6 和 7 6 7 6 8 6

本次划分后，对与key元素相等处理的结果：1 4 6 6 6 6 6 7 8 7

下次的两个子序列为：1 4 和 7 8 7

经过对比，我们可以看出，在一次划分后，把与key相等的元素聚在一起，能减少迭代次数，效率会提高不少

具体过程：在处理过程中，会有两个步骤

第一步，在划分过程中，把与key相等元素放入数组的两端

第二步，划分结束后，把与key相等的元素移到枢轴周围

三数取中+插排+聚集相同元素基本上能满足绝大部分需求了

堆排序

先说一下堆的概念：堆是具有以下性质的完全二叉树——每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；arr[i] >= arr[2i] && arr[i] >= arr[2i+1]
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；arr[i] <= arr[2i] && arr[i] <= arr[2i+1]

注：以上两公式都是基于数组1位置开始存储元素

堆的操作

上浮：如果堆的有序状态因为某个结点变得比它的父结点更大而被打破，那么我们就需要通过交换它和它的父结点来修复堆。

//数组0位置不存储元素
private void swim(int k){
    while(k>1 && less(k/2,k)){
        exch(k/2,k);
        k = k/2;
    }
}

下沉：如果堆的有序状态因为某个结点变得比它的两个子结点或是其中之一更小了而被打破了，那么
我们可以通过将它和它的两个子结点中的较大者交换来恢复堆。

private void sink(int k){
    while(2*k<=N){
        int j = 2*k;
        //j没到最后且左子节点<右子节点
        if(j<N && less(j,j+1))  j++;
        if(!less(k,j))  break;
        exch(k,j);//交换对应元素
        k = j;
    }
}

算法步骤

将待排序序列构建成一个堆 H[0……n-1]，根据（升序降序需求）选择大顶堆或小顶堆；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。

动图演示

实现代码

package SortAlgorithm;

/**
 * @Author: Salute61
 * @Date: 2020/8/29 14:48
 * @Description: 堆排序基本思路是将数组转化为一个堆
 *               本代码就是转化为一个大根堆,Heapify操作即调整结构,BuildHeap将整个数组转化
 */
public class HeapSort {
    private static void exch(int[] a,int i,int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    private static void show(int[] a){
        for(int i=0;i<a.length;i++)
            System.out.print(a[i]+" ");
        System.out.println("本次结束！");
    }
    //heapify操作调整二叉树结构
    public static void Heapify(int[] a,int root,int len){
        if(root>=len){
            return ;
        }
        int left = 2*root+1;
        int right = 2*root+2;
        int max = root;
        //判断当前子树的根、左子、右子哪个最大
        if(left<len && a[left]>a[max]){
            max = left;
        }
        if(right<len && a[right]>a[max]){
            max = right;
        }
        //max!=i表示当前子树的根节点不是最大,交换
        if(max!=root){
            exch(a,root,max);
            //交换以后，其对应的max孩子节点的最大堆的性质可能被破坏，因此需递归调用
            Heapify(a,max,len);
        }
    }
    public static void BuildHeap(int[] arr) {
        //从最后一个父节点开始遍历
        for(int i =arr.length/2-1;i>=0;i--) {
            Heapify(arr,i,arr.length);//调用交换节点数据的方法，将最大的数移到顶端节点
        }
    }
    public static void sort(int[] a,int len){
        if(a==null || a.length<=1){
            return ;
        }
        //将a构建为一个大根堆
        BuildHeap(a);
        //依次取出大根堆的堆顶元素
        for(int i=len-1;i>=0;i--){
            exch(a,0,i);
            Heapify(a,0,i);
            show(a);
        }
    }
    public static void main(String[] args){
        int[] a = {49,38,65,97,76,27,13,49};
        sort(a,a.length);
    }
}

计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

总的来说计数排序效率比较低，因为序列中的数是分散的，可能最大值100010，而大部分元素都小于100，这就导致bucket数组有很多空间未被利用，浪费较大

算法步骤

找出原数组中元素值最大的，记为max。
创建一个新数组count，其长度是max加1，其元素默认值都为0。
遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。
创建结果数组result，起始索引index。
遍历count数组，找出其中元素值大于0的元素，将其对应的索引作为元素值填充到result数组中去，每处理一次，count中的该元素值减1，直到该元素值不大于0，依次处理count中剩下的元素。
返回结果数组result。

动图演示

实现代码

package SortAlgorithm;

/**
 * @Author: Salute61
 * @Date: 2020/8/29 22:24
 * @Description: 计数排序的基本思想是存储序列中元素出现次数
 */
public class CountSort {
    private static void exch(int[] a,int i,int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    private static void show(int[] a){
        for(int i=0;i<a.length;i++)
            System.out.print(a[i]+" ");
        System.out.println("本次结束！");
    }
    public static int getMax(int[] a){
        int maxValue = a[0];
        for(int value:a){
            if(maxValue<value)
                maxValue = value;
        }
        return maxValue;
    }
    public static void sort(int[] a){
        int max = getMax(a);
        //设置count数组
        int bucketLen = max + 1;
        int[] bucket = new int[bucketLen];
        //原序列数据出现一次,count对应索引＋1
        for(int value:a){
            bucket[value]++;
        }
        //sortIndex索引用于将count数组元素返回到a
        int sortedIndex = 0;
        for(int i=0;i<bucketLen;i++){
            while(bucket[i]>0){
                a[sortedIndex++] = i;
                bucket[i]--;
            }
        }
        show(a);
    }
    public static void main(String[] args){
        int[] a = {12,6,58,92,55,33,10,38};
        sort(a);
    }
}

桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

什么时候最快

当输入的数据可以均匀的分配到每一个桶中。

什么时候最慢

当输入的数据被分配到了同一个桶中。

动图演示

实现代码

package SortAlgorithm;

import SortAlgorithm.InsertionSort;
import java.util.Arrays;

/**
 * @Author: Salute61
 * @Date: 2020/8/29 22:40
 * @Description: 桶排序相当于计数排序的改进,思想和hash类似
 */
public class BucketSort {
    private static void exch(int[] a,int i,int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    private static void show(int[] a){
        for(int i=0;i<a.length;i++)
            System.out.print(a[i]+" ");
        System.out.println("桶排_本次结束！");
    }
    //桶扩容、保存数据
    private static int[] arrAppend(int[] a,int value){
        a = Arrays.copyOf(a,a.length+1);
        a[a.length-1] = value;
        return a;
    }
    public static int[] BucketSort(int[] a,int bucketSize){
        if(a.length==0) {
            return a;
        }
        //找出序列的最大最小值
        int min = a[0];
        int max = a[0];
        for(int value:a){
            if(value<min)
                min = value;
            else if(value>max)
                max = value;
        }
        //确定桶的个数,通过 最值差值 比上 桶的范围 得到
        int bucketCount = (int)Math.floor((max-min)/bucketSize)+1;
        int[][] buckets = new int[bucketCount][0];
        //利用映射函数将数据放到桶中
        for(int i=0;i<a.length;i++){
            int index = (int) Math.floor((a[i]-min)/bucketSize);
            buckets[index] = arrAppend(buckets[index],a[i]);
        }
        //对桶内元素排序
        int arrIndex = 0;
        for(int[] bucket:buckets){
            if(bucket.length<=0)
                continue;
            //桶内采用插入排序
            bucket = InsertionSort.sort(bucket);
            for(int value:bucket){
                a[arrIndex++] = value;
            }
//            show(a);
        }
        return a;
    }
    public static void main(String[] args){
        int[] a = {12,6,58,92,55,33,10,38};
        a = BucketSort(a,22);
        show(a);
    }
}

基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

算法步骤

基数排序有两种方法：

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异案例看大家发的：

基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；

动图演示

实现代码

/**
 * 基数排序
 * 考虑负数的情况还可以参考： https://code.i-harness.com/zh-CN/q/e98fa9
 */
public class RadixSort implements IArraySort {
    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        int maxDigit = getMaxDigit(arr);
        return radixSort(arr, maxDigit);
    }
    /**
     * 获取最高位数
     */
    private int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }
    //获取最大值
    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }
    //获取数组num的位数
    protected int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }
    //基数排序实现
    private int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
           // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }
        return arr;
    }
    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}