世界上最好的排序算法是什么？

Nick

关注

发布于: 2021 年 03 月 07 日

在计算机世界有很多种排序算法，比如冒泡排序、插入排序、选择排序、快速排序、基数排序、桶排序等等。我们通常可以把排序分为比较类排序、非比较类排序。

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

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

这么多排序算法，你知道最好的排序算法是什么吗？目前世界上通常情况下最好的算法是一种叫做"快速排序（Quicksort）"的算法，他是由英国计算机科学家托尼·霍尔（Tony Hoare）于 1959 年想到的，1961 年发表的，这个算法也成了今天世界计算机产业中使用最多的排序算法，霍尔因此获得了爵士头衔，也成为第一个获得这种头衔的科学家。那么快速排序为什么快呢？原因很简单，少做事情，其原理大致是这样的：

首先，对于一大堆无序的数字，从中随机挑选一个，比如是 53，这个被随机选上的数字被称为枢值（枢纽的枢），接下来，将所有要排序的数字分成两部分，第一部分是大于等于枢值 53 的，第二部分是小于枢值 53 的。在第一步完成后，一大堆无序的数字就变得稍微有序一点了。

第二步，从上面得到的两堆数字，分别采用第一步的方法各自再找一个枢值。对于第一堆，由于所有的数字都比 53 大，至少也等于 53，因此，第二次随机挑选的枢值肯定是一个大于 53 的数字，比如 79；类似地，对于第二堆，由于所有的数字都小于 53，因此第二次随机挑选的枢值肯定小于它，比如 4。接下来，再把两堆数字各自分成大于等于相应枢值的数字序列，以及小于枢值的数字序列。这样做下来，原来的一大堆数就变成了四小堆，它们分别是小于 4 的数字，介于 4 到 53 之间的，介于 53 到 79 之间的，以及大于或等于 79 的。

再接下来，用同样的方法，四堆变八堆，八堆变十六堆，很快所有的数字就排好序了。这种算法通常情况下复杂度也是 N 乘以 log（N）。

Talk is cheap, show you the code.

** * @program: Algorithm * @description: 排序算法演练 * @author: NickCheng * @create: 2021-03-07 18:45 **/
public class Sorts {
    /**     * 冒泡排序，a表示数组，n表示数组大小     * */    public static void bubbleSort(int[] a, int n) {        long beginTime = System.currentTimeMillis();        if (n <= 1) return;
        for (int i = 0; i < n; ++i) {            // 提前退出冒泡循环的标志位            boolean flag = false;            for (int j = 0; j < n - i - 1; ++j) {                if (a[j] > a[j+1]) { // 交换                    int tmp = a[j];                    a[j] = a[j+1];                    a[j+1] = tmp;                    flag = true;  // 表示有数据交换                }            }            if (!flag) break;  // 没有数据交换，提前退出        }        System.out.println("冒泡排序时间："+ (System.currentTimeMillis() - beginTime) );    }

    /**     * 插入排序     *     * @param a 表示数组     * @param n 表示数组大小     */    public static void insertionSort(int[] a, int n) {        long beginTime = System.currentTimeMillis();        if (n <= 1) return;
        for (int i = 1; i < n; ++i) {            int value = a[i];            int j = i - 1;            // 查找插入的位置            for (; j >= 0; --j) {                if (a[j] > value) {                    a[j+1] = a[j];  // 数据移动                } else {                    break;                }            }            a[j+1] = value; // 插入数据        }        System.out.println("插入排序时间："+ (System.currentTimeMillis() - beginTime) );    }
    /**     * 快速排序     * @param a     */    public static void quickSort(int[] a, int n) {        long beginTime = System.currentTimeMillis();        int len;        if(a == null                || (len = a.length) == 0                || len == 1) {            return ;        }        quickSortC(a, 0, len - 1);        System.out.println("快速排序时间："+ (System.currentTimeMillis() - beginTime) );    }
    /**     * 快排核心算法，递归实现     * @param array 数字     * @param left 左下标     * @param right 右下标     */    public static void quickSortC(int[] array, int left, int right) {        if(left > right) {            return;        }        // base中存放基准数        int base = array[left];        int i = left, j = right;        while(i != j) {            // 顺序很重要，先从右边开始往左找，直到找到比base值小的数            while(array[j] >= base && i < j) {                j--;            }
            // 再从左往右边找，直到找到比base值大的数            while(array[i] <= base && i < j) {                i++;            }
            // 上面的循环结束表示找到了位置或者(i>=j)了，交换两个数在数组中的位置            if(i < j) {                int tmp = array[i];                array[i] = array[j];                array[j] = tmp;            }        }
        // 将基准数放到中间的位置（基准数归位）        array[left] = array[i];        array[i] = base;
        // 递归，继续向基准的左右两边执行和上面同样的操作        // i的索引处为上面已确定好的基准值的位置，无需再处理        quickSortC(array, left, i - 1);        quickSortC(array, i + 1, right);    }

    /**     * 计数排序，a是数组，n是数组大小。假设数组中存储的都是非负整数     */    public static void countingSort(int[] a, int n) {        long beginTime = System.currentTimeMillis();        if (n <= 1) return;
        // 查找数组中数据的范围        int max = a[0];        for (int i = 1; i < n; ++i) {            if (max < a[i]) {                max = a[i];            }        }
        int[] c = new int[max + 1]; // 申请一个计数数组c，下标大小[0,max]        for (int i = 0; i <= max; ++i) {            c[i] = 0;        }
        // 计算每个元素的个数，放入c中        for (int i = 0; i < n; ++i) {            c[a[i]]++;        }
        // 依次累加        for (int i = 1; i <= max; ++i) {            c[i] = c[i-1] + c[i];        }
        // 临时数组r，存储排序之后的结果        int[] r = new int[n];        // 计算排序的关键步骤，有点难理解        for (int i = n - 1; i >= 0; --i) {            int index = c[a[i]]-1;            r[index] = a[i];            c[a[i]]--;        }
        // 将结果拷贝给a数组        for (int i = 0; i < n; ++i) {            a[i] = r[i];        }        System.out.println("计数排序时间："+ (System.currentTimeMillis() - beginTime) );    }
    /**     * 生成随机数组     * */    public static int[]  gennerateArray(int len,int max){        int[] arr=new int[len];        for(int i=0;i<arr.length;i++){            arr[i]=(int)(Math.random()*max);        }        return arr;    }
    public static void main(String[] args){        //随机生成一个数组        int[] array = gennerateArray(100000,100000);        int arraySize = array.length;        bubbleSort(array,arraySize);        insertionSort(array,arraySize);        quickSort(array,arraySize);        countingSort(array,arraySize);    }}

复制代码

如果你将上面代码跑一下你就会发现，当执行快速排序的时候会出现了堆栈溢出的情况。该例子中快速排序使用了递归，而使用递归则要警惕堆栈溢出。那么如何解决该问题？有如下两个方案：第一种是限制递归深度。一旦递归过深，超过了我们事先设定的阈值，就停止递归。第二种是通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的限制。接下来，我们看下优化后的快速排序方法。

3 种快排优化方法。

    /**     *     *优化:将第一个元素为基准值改为随机一个元素为基准值     *降低退化为O(n^2)的概率     *数学期望值为O(nlogn)     *这样就不会受“几乎有序的数组”的干扰了     *但是对“几乎乱序的数组”的排序性能可能会稍微下降，至少多了排序前交换的那部分     *乱序时这个交换没有意义     * */    public static void quickSort2(int[]arr,int n) {        quickSort2(arr,0,n-1);    }
    private static void quickSort2(int[] arr, int l, int r) {        if(l>=r)            return;        int p = midal(arr,l,r);        quickSort2(arr, l, p-1);        quickSort2(arr, p+1, r);
    }
    private static int midal(int[] arr, int l, int r) {        swap(arr,l,(int)Math.random()*(r-l+1)+l);        //满足arr[l+1,i)<=v,arr(j,r]>=v        int v=arr[l];        int i=l+1,j=r;        while(true) {            //从左到右扫描，扫描出第一个比base大的元素，然后i停在那里            while(arr[i]<v&&i<r)//arr[i]不能=v，会导致v聚集在一边                i++;            //从右到左扫描，扫描出第一个比base小的元素，然后j停在那里            while(arr[j]>v&&j>=l)                j--;            if(i>=j)                break;            swap(arr, i, j);            i++;            j--;        }        //将基准值交换到合适位置        swap(arr, l, j);        return j;    }
    private static void swap(int[] arr, int i, int j) {        if(i!=j) {            int temp=arr[i];            arr[i]=arr[j];            arr[j]=temp;        }    }
    /**     *二路快排：对于方一方二中如果存在大量重复元素，当基准值为重复元素时     *等于base的这些会聚集到右侧(或者稍微改改大小关系就会聚集到左侧)。     *总之就会聚集到一边。这样在数组中重复数字很多的时候，     *就又会导致两边子递归规模差距悬殊的情况，很有可能退化为O(n^2)     *这时想把等于base的那些数分派到base两边，而不是让他们聚集到一起。     *     *优化：可以将swap去掉     */    public static void quickSort3(int[]arr,int n) {        quickSort3(arr,0,n-1);    }
    private static void quickSort3(int[] arr, int l, int r) {        if(l>=r)            return;        int p=Midal(arr,l,r);        quickSort3(arr, l, p-1);        quickSort3(arr, p+1, r);
    }
    private static int Midal(int[] arr, int l, int r) {        swap3(arr,l,(int)Math.random()*(r-l+1)+l);        //满足arr[l+1,i)<=v,arr(j,r]>=v        int v=arr[l];        int i=l+1,j=r;        while(true) {            //从左到右扫描，扫描出第一个比base大的元素，然后i停在那里            while(arr[i]<v&&i<r)//arr[i]不能=v，会导致v聚集在一边                i++;            //从右到左扫描，扫描出第一个比base小的元素，然后j停在那里            while(arr[j]>v&&j>=l)                j--;            if(i>=j)                break;            swap3(arr, i, j);            i++;            j--;        }        //将基准值交换到合适位置        swap3(arr, l, j);        return j;    }    private static void swap3(int[] arr, int i, int j) {        if(i!=j) {            int temp=arr[i];            arr[i]=arr[j];            arr[j]=temp;        }    }
    /**     *三路快排：当大量数据，且重复数多时，用三路快排     *将整个数组分为小于v，等于v，大于v三部分     */    public static void quickSort4(int[]arr,int n) {        quickSort4(arr,0,n-1);
    }    private static void quickSort4(int[] arr, int l, int r) {        if(l>=r)            return;        //因为==v的部分是一个数组而非单独的一个数，所以直接处理，不调用函数        swap(arr,l,(int)Math.random()*(r-l+1)+l);        int v=arr[l];        //变量定义要保证初始空间为空        int i=l+1;//arr[lt+1,i)==v        int lt=l;//arr[l+1,lt]<v        int gt=r+1;//arr[gt,r]>v            while (i<gt) {            if(arr[i]==v) {                i++;            }else if (arr[i]<v) {                swap(arr, i, lt+1);//画示意图，arr[lt+1]==v                i++;                lt++;            }else {                swap(arr, i, gt-1);//arr[gt-1]为未处理的数据                gt--;            }        }        swap(arr, l, lt);        quickSort4(arr, l, lt-1);        quickSort4(arr, gt, r);    }     /**     * 生成随机数组     * */    public static int[]  gennerateArray(int len,int max){        int[] arr=new int[len];        for(int i=0;i<arr.length;i++){            arr[i]=(int)(Math.random()*max);        }        return arr;    }

复制代码

你可能会问，有没有可能发明一种比快速排序更好的算法？从科学上讲，答案是否定的。因为从数学上可以证明 N 个任意随机数的排序，复杂度不可能比 N 乘以 log（N）更低，这是数学给出的极限，或者边界。

参考：《谷歌方法论》、《数据结构与算法之美》

发布于: 2021 年 03 月 07 日阅读数: 23

原文链接:【http://xie.infoq.cn/article/13e7d271c3ca39e839e861cd0】。文章转载请联系作者。

Nick

关注

终身学习，向死而生 2020.03.18 加入

得到、极客时间重度学习者，来infoQ 是为了输出倒逼输入

发布

暂无评论

创作场景

世界上最好的排序算法是什么？

Nick

评论