前言

本文是排序算法系列的第六篇，是一个总结篇

但它不是最后一篇~

还有一个堆排序，因为涉及到二叉树的概念，不太好写，暂时放在后边

本文将在多个方面（稳定性、时间性能、空间性能）对所有排序算法进行对比

参与对比的有下列共十种排序算法：

冒泡排序、选择排序、插入排序、二分插入排序、希尔排序、快速排序、归并排序、基数排序、计数排序、堆排序

稳定性对比

本文主要对比性能，稳定性只展示个结论，不做集具体说明，这里再解释一次稳定性的概念：

稳定性就是，比如下面这组数字

31，44（a），44（b），86，18，28

有两个相同的44，给两个44打上标记，a号44和b号44

排好后两种可能：18，28，31，44（b），44（a），86 或 18，28，31，44（a），44（b），86

两个44谁前谁后都不影响排序的结果是正确的

但两个44和排序前相比，如果被逆序了（b号44跑到a号44前面），这种就称为不稳定

稳定的排序就是，除了完成排序规则必须进行的顺序改变外，不改变原有的顺序

也就是两个数字相等的时候原先在前面的还在前面，原先在后面的还在后面，才叫稳定排序

结论在下方时间性能对比的表格中

时间性能对比

理论时间复杂度：

r代表关键字基数，d代表长度，n代表关键字个数

计数排序稳定性说明：计数排序优势在于只对整数排序时，记录数量即可，所以一般不考虑稳定性，如果考虑稳定性，会多占用非常大量的空间，得不偿失

实际测试排序用时：

1.测试环境

同一台电脑、相同运行环境、JDK1.8、idea 2021.1.1x64

2.测试数据

区间：[-5*n,5*n] 中随机生成的 n 个整数，例如8w数据将在 [-40w,40w] 区间生成随机的8w数据

    /**
     * 生成num个随机的正负整数
     * （从-5*num到5*num的范围，生成num个整数）
     *
     * @param num 生成的数量
     * @return num个随机整数的int数组
     */
    private static int[] getIntsAll(int num) {
        int[] arr = new int[num];
        for (int i = 0; i < num; i++) {
            arr[i] = (int) (Math.random()*(Math.random()>0.5?1:-1) * num*5);
        }
        return arr;
    }

为了严谨的计算时间，会在如下代码中间执行排序算法

保证排序正确的前提下，得到执行时间

所有排序算法的代码，都在之前的文章中有，我也会整理本次测试使用到的所有代码，贴在文章的末尾，读者可自行拿来复测

long startTime = System.currentTimeMillis();

//这里是排序算法的执行
//BubbleSort.bubbleSort(arr);//冒泡
//SelectSort.selectSort(arr);//选择
//InsertSort.insertSort3(arr);//插入（while循环）
//InsertSort.insertSort4(arr);//插入（for循环）
//InsertSort.binarySort(arr);//二分插入排序
//ShellSort.shellSort2(arr);//希尔排序
//QuickSort.quickSort3(arr);//快速排序（填坑法）
//QuickSort.quickSort3(arr);//快速排序（交换法）
//MergeSort.mergeSort(arr);//归并排序
//RadixSort.radixSortPlus(arr);//基数排序（支持负整数版）
//CountSort.countSort(arr);//计数排序（支持负整数版）
//HeapSort.heapSort(arr);//堆排序

System.out.println("总执行时长(毫秒)："+(System.currentTimeMillis()-startTime));

//这里调用了一个判断数组是否有序的方法，防止算法因为写错进行了错误的排序，从而导致的数据没有参考价值
System.out.println(ifSort(arr));
//方法如下：
/**
 * 判断一个数组是否是从小到大有序的
 * @param arr 待判断数组
 * @return 是否有序
 */
static boolean ifSort(int[] arr){
    for (int i = 0; i < arr.length-1; i++) {
        if (arr[i+1]<arr[i]){
            return false;
        }
    }
    return true;
}

3.测试结果

测试结果都分别执行七次，去掉一个最快一个最慢，余下五个取平均值，单位都是毫秒

注：详细测试数据放在文末

4.性能排名

8000w数据基数和计数排序都内存溢出了，为了比较，降低了数量级

用2000w数据进行了测试，结论是：计数>堆>基数>JDK，类推到8000w得出的数据

5.测试结论分析

首先测试数据具有一定的局限性，属于是均匀散列的随机整数组，未考虑特殊情况比如小范围内的大量数据，或大范围内的少量数据等。

1.堆排序效率几乎任何数据量情况都是第一第二，稳居榜首

2.计数排序数据量越大越好，但其实这里对计数排序测试不够细致，计数排序如果数据范围很大，数据量很小会很不友好，而数据范围很小数据量很大时是非常快的。

3.快速排序数据量较大时，填坑法实现性能优于交换法，数据量特效小时交换法优于填坑法

4.同作为非比较排序，基数排序性能比计数排序差，而两者都随着数据量增大性能排名有所提升

5.实在是有点搞不懂，为什么二分插入排序性能实测弱与插入排序...貌似这并不是插入排序的一个好的优化

6.JDK排序性能并没有表现很好，弱于所有非比较排序，也弱于堆排序，数据量较小时表现也不佳（值得关注的是，JDK源码中，数据量小于47时，完全使用的是插入排序，却比我自己实现的插入排序性能要略好一些，后续有空时应该稍作研究，看看差在哪里）

7.选择、冒泡、插入，完全不适合大数据量的排序，效率非常低

8.实践得出的结果表明，在对10个数据排序的性能表现中，最优秀的是选择排序，但JDK排序源码中却使用了插入排序作为数据量低于47时的排序方式，或许是经过测试数据<47时，插入排序综合性能更好？

9.对于for实现的插入和while实现的插入，比较发现，执行次数较多时，while优于for，次数较少时好像是for更快？

暂时就这么多，读者朋友有什么新结论可在评论区讨论~

空间性能对比

这里不做过多的测试和赘述，直接上结论

附录

附录一：测试使用的排序算法代码

1.冒泡排序

	public static void bubbleSort(int[] arr){
        //用来表示某一趟发生的排序次数
        int times = 0;

        //外层控制总趟数，所以i=1表示从第一趟开始，当等于length就不执行了也就是一共执行length-1趟
        for (int i = 1; i < arr.length; i++) {
            //内层，进行从第1个数到第length-i个数，依次与后一个数字比较，逆序就交换
            // 这里让j=0,因为第一个数下标为0
            for (int j = 0; j < arr.length-i; j++) {
                if (arr[j]>arr[j+1]){
                    //进入这里说明发生了一次交换
                    times++;
                    int t = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = t;
                }
            }
            //一趟排序结束，打印一下这一趟后的数组，以及发生了几次交换
//            System.out.println("第"+i+"趟后的数组：");
//            System.out.println(Arrays.toString(arr));
//            System.out.println("这一趟发生了"+times+"次交换");
            //如果发生过交换，就重置次数为0进入下一次循环
            if (times>0){
                times = 0;
            }
            //否则说明这一趟没有进行任何交换，直接跳出循环即可
            else {
//                System.out.println("本轮没有进行交换，排序已完成");
                break;
            }
        }
//        System.out.println(Arrays.toString(arr));
    }

2.选择排序

    public static void selectSort(int[] arr){
        //记录某一趟的最小值的索引
        int minIndex;
        //比较变量——最终保存某一趟的最小值
        int min;
        for (int i = 0; i < arr.length-1; i++) {
            //每一趟排序开始前，把这一趟要扫描的第一个数放到比较变量上，假定他就是最小的
            minIndex = i;
            min = arr[i];
            for (int j = i+1; j < arr.length; j++) {
                if (arr[j]<min) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            //一趟排序扫描完毕后，是第几趟就把这一趟找到的最小值和第几个交换
            if (minIndex!=i){
                //如果当前i索引位置本身就是最小值了，就没有必要执行交换操作
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }

3.while插入

    public static void insertSort3(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            //待插入的数
            int insertVal = arr[i];
            int insertIndex = i-1;
            /*
             * 1.insertIndex>=0保证插入位置索引不越界
             * 2.insertVal < arr[insertIndex]表示待插入数据还没有找到应该插入的位置
             * 满足这两个条件，需要将arr[insertIndex]后移，insertIndex--
             */
            while (insertIndex>=0 && insertVal < arr[insertIndex]){
                arr[insertIndex+1] = arr[insertIndex];
                insertIndex--;
            }
            //退出while循环后，说明当前insertIndex+1就是待插入数据的位置
            arr[insertIndex+1] = insertVal;
        }
    }

4.for插入

    public static void insertSort4(int[] arr){
        //从第二个数开始遍历
        for (int i = 1; i < arr.length; i++) {
            //待插入的数存进临时变量
            int temp = arr[i];
            //记录待插入数应该插入的位置(初始化为要被插入的数据本身的位置)
            int index = i;
            //内层遍历待插入数前面的所有数去找到他的位置
            for (int j = i-1; j >= 0 && arr[j]>temp; j--) {
                /*
                 * 依次向下标i之前的数据，挨个比较
                 * 如果当前位置数据比自己大就将其后移，记录下当前这个位置的索引
                 * 后续有两种情况会退出这个循环：
                 * 1.当前要遍历的数字比自己小时就不会再进入循环了，而那个上一次循环中记录下来的索引位置就是要插入的位置
                 * 2.如果一直到索引0的位置还没有找到比自己小的，下一次也会退出循环，上一次循环中记录的索引位置必然为0，也是要插入的位置
                 */
                arr[j+1]=arr[j];
                index = j;
            }
            //综上只要是退出了循环，index就是指向数据要插入的位置，直接插入就好
            arr[index] = temp;
        }
    }

5.二分插入

    public static void binarySort(int[] source) {
        int temp;
        int low, mid, high;
        for (int i = 1; i < source.length; i++) {
            temp = source[i];
            // 在待插入排序的序号之前进行折半插入
            low = 0;
            high = i - 1;
            while (low <= high) {
                mid = (low + high) / 2;
                if (temp < source[mid])
                    high = mid - 1;
                else
                    // low=high的时候也就是找到了要插入的位置，
                    // 此时进入循环中，将low加1，则就是要插入的位置了
                    low = mid + 1;
            }
            //找到了要插入的位置，从该位置一直到插入数据的位置之间数据向后移动
            for (int j = i; j >= low + 1; j--){
                source[j] = source[j - 1];
            }
            // low已经代表了要插入的位置了
            source[low] = temp;
        }
    }

6.希尔排序

    public static void shellSort2(int[] arr) {
        int temp, j;
        for (int path = arr.length / 2; path > 0; path /= 2) {
            for (int i = path; i < arr.length; i++) {
                j = i;
                temp = arr[j];
                while (j - path >= 0 && temp < arr[j - path]) {
                    arr[j] = arr[j - path];
                    j -= path;
                }
                arr[j] = temp;
            }
        }
    }

7.快速排序（填坑法）

    public static void quickSort2(int[] arr){
        quickSort2(arr,0, arr.length-1);
    }
    private static void quickSort2(int[] arr, int start, int end){
        //1.找一个数字作为基准p，让这个数左边都<p，右边都>=p
        int index = partition2(arr, start, end);
        //2.完成之后，比基准数字小都都在左边，大的都在右边，再重复对左右两边的部分进行上述操作
        //3.考虑递归边界，判断如果左右边总数据量小于两个(0个或1个)就不再递归了
        if (index-1-start>=1){
            quickSort2(arr,start,index-1);
        }
        if (end-index-1>=1){
            quickSort2(arr,index+1,end);
        }
    }
    private static int partition2(int[] arr, int start, int end) {
        //1.指定第一个数为基准数字，将基准数字挖出来存在这里，原来的位置当做一个坑用于排序
        int p = arr[start];
        //2.定义两个指针，一个在最左边，一个最右边
        int left = start;
        int right = end;
        //3.只要左指针还在右指针的左边，就循环用右边找一个小于p的填左边坑，右边作为新坑，再从左边找一个>=p的填右边的坑
        while (left<right){
            //进入循环坑一定在左边，所以先从右向左
            //先从右到左寻找比基准数字小的，找到就让右指针指向这个数字
            while (left<right && arr[right] >= p){
                right--;
            }
            //退出从右到左的寻找循环表示找到了，或者left=right了
            if (left==right){
                //说明排好了
                break;
            }
            //到这里没有退出循环说明找到了，用它填左边的坑，再将左指针后移，此时右指针位置变成新坑
            arr[left] = arr[right];
            left++;
            //再从左到右寻找比基准数字大的，找到就让左指针指向这个数字
            while (left<right && arr[left] < p){
                left++;
            }
            //退出从左到右的寻找循环表示找到了或者left==right了
            if (left==right){
                //说明排好了
                break;
            }
            //到这里没有退出循环说明找到了，用它填右边的坑，再将右指针前移，此时左指针位置变成新坑
            arr[right] = arr[left];
            right--;
        }
        //直到退出大循环，此时的left一定等于right，就是基准数字应该在的位置，将基准数字安插在这里
        arr[left] = p;
        //返回基准数字所在位置索引
        return left;
    }

8.快速排序（交换法）

    public static void quickSort3(int[] arr){
        quickSort3(arr,0, arr.length-1);
    }
    private static void quickSort3(int[] arr, int start, int end){
        //1.找一个数字作为基准p，让这个数左边都<p，右边都>=p
        int index = partition3(arr, start, end);
        //2.完成之后，比基准数字小都都在左边，大的都在右边，再重复对左右两边的部分进行上述操作
        //3.考虑递归边界，判断如果左右边总数据量小于两个(0个或1个)就不再递归了
        if (index-1-start>=1){
            quickSort3(arr,start,index-1);
        }
        if (end-index-1>=1){
            quickSort3(arr,index+1,end);
        }
    }
    private static int partition3(int[] arr, int start, int end) {
        //1.指定第一个数为基准数字
        int p = arr[start];
        //2.定义两个指针，一个在基准数的下一个，一个在最右边，用于左到右和右到左的扫描
        int left = start+1;
        int right = end;
        //3.保持一个循环，再循环中判断排好，直接用返回结束循环
        while (true){
            //这里先左到右或先右到左都可以
            //先从左指针开始向右指针扫描（不用扫右指针及右指针之后的）,直到发现一个大于基准数字的就指向它
            while (left < right && arr[left] <= p){
                left++;
            }
            //再从右指针开始向左扫描（需要扫左指针及左指针之后的），直到发现一个小于等于基准数字的就指向他
            while (arr[right] > p){
                right--;
            }
            //这里有两种情况需要区别对待，如果right>left，说明两个指针交错前两边都找到了，两个数据进行交换
            if (right>left){
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
            //否则说明两边交错后才找到，此时交换基准数字和right就排好了,返回基准数字索引right
            else {
                int temp = arr[start];
                arr[start] = arr[right];
                arr[right] = temp;
                return right;
            }
        }
    }

9.归并排序

    public static void mergeSort(int[] arr){
        MergeSort.mergeSort(arr,0,arr.length-1,new int[arr.length]);
    }
    private static void mergeSort(int[] arr, int start, int end, int[] temp){
        //如果数组段中的数据大于等于2个，就分割成左右两边
        if (start < end){
            //中间数索引（左边的终点）
            int mid = (start + end) / 2;
            mergeSort(arr, start, mid, temp);
            mergeSort(arr, mid + 1, end, temp);
            //无论是否需要再次分割，分割完毕或不分割，都执行一次合并操作
            merge(arr,start,mid,end,temp);
        }
    }
    private static void merge(int[] arr, int start, int mid, int end, int[] temp) {
        //左起点为start，左终点为mid，右起点为mid+1，右终点为end
        //左指针
        int lPointer = start;
        //右指针
        int rPointer = mid + 1;
        //临时数组指针
        int t = 0;
        //当左右指针都没越界比较左右两个指针指向数据的大小，谁小就把谁放在临时数组指针位置，并将指针后移一个
        while (lPointer<= mid && rPointer<= end){
            if (arr[lPointer]<arr[rPointer]) {
                temp[t++] = arr[lPointer++];
            }else {
                temp[t++] = arr[rPointer++];
            }
        }
        //当某个指针没越界，剩余的都放入临时数组
        while (lPointer<= mid){
            temp[t++] = arr[lPointer++];
        }
        while (rPointer<= end){
            temp[t++] = arr[rPointer++];
        }
        //将排好序的temp放回arr的start到end
        int index = start;
        t = 0;
        while (index<=end){
            arr[index++] = temp[t++];
        }
    }

10.基数排序

    public static void radixSortPlus(int[] arr){
        //1.判断最小的数字是否是负数，如果不是就按正整数处理，如果是，就获取这个值
        int minNum = arr[0];

        //在一个循环中，获取到最小的数字
        for (int i : arr) {
            if (i<minNum){
                minNum = i;
            }
        }
        //如果最小的数字是负数,遍历数组，给所有数字减去这个负数（相当于加上这个数的绝对值）
        if (minNum<0){
            for (int i = 0; i < arr.length; i++) {
                arr[i]-=minNum;
            }
        }

        //减去最小的负数后，整个数组被转换为非负整数了，进行非负整数的基数排序
        radixSort(arr);

        //排序结束后，如果最小的数字是负数，再遍历数组，给每个数据加上这个负数（相当于减去这个数的绝对值）
        if (minNum<0){
            for (int i = 0; i < arr.length; i++) {
                arr[i]+=minNum;
            }
        }
    }

11.计数排序

    public static void countSort(int[] arr){
        //设置默认最大最小值
        int min=arr[0];
        int max=arr[0];
        //找出最大，最小值
        for (int value : arr) {
            if (max < value) {
                max = value;
            }
            if (min > value) {
                min = value;
            }

        }
        //创建计数数组
        int[] countArr=new int[max-min+1];
        //遍历待排序数组，确定每个数字的数量存入技术数组
        for (int value : arr) {
            countArr[value - min]++;
        }
        //遍历计数数组，把数据按顺序放回arr
        int begin=0;
        for (int i = 0; i < countArr.length; i++) {
            if (countArr[i]!=0){
                //有几个当前数字，就放几个
                for (int j = 0; j <countArr[i] ; j++) {
                    arr[begin]=min+i;
                    begin++;
                }
            }
        }
    }

12.堆排序

    public static void heapSort(int[] arr){
        //从右到左，从下到上，遍历每个非叶子节点，都执行一次转换为大顶堆的方法
        // 此时整个数组都是一个大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--){
            toLargeTopHeap(arr,i,arr.length);
        }
        //此时的arr已经全部转化为了大顶堆的形状，arr[0]就是数组中的最大值
        for (int j = arr.length-1; j>0 ; j--){
            //将最大值和最后一个数据交换位置
            int temp = arr[0];
            arr[0] = arr[j];
            arr[j] = temp;
            //交换后，对大顶堆的破坏只有两个数据，
            // 最后一个arr[j]等于排好序了，下次不参与，所以不用管，
            // 相当于只影响了第一个arr[0],
            // arr[1]到arr[j-1]都还是大顶堆
            // 就只需要对arr[0]做前j个数据转化大顶堆的操作
            toLargeTopHeap(arr,0,j);
            //然后继续循环交换再转换，直到交换后只剩一个数字就排好序了
        }
    }
    private static void toLargeTopHeap(int[] arr, int i, int length){
        //临时存储当前非叶子节点的值，等找到他的位置再去存放
        int temp = arr[i];
        //相当于此时的i位置被空出来了

        //进入一个循环，这里理解起来比较复杂：
        // 1.首先让k指向i的左子节点k=2*i+1
        for (int k = i * 2 + 1; k < length;) {
            //2.再将k指向i的左右子节点中更大的一个
            if (k+1 < length && arr[k] < arr[k+1]){
                //进入这里说明右子节点更大
                k++;
            }
            //3.判断需要找到位置的temp和左右子节点中更大的一个arr[k]的大小关系
            if (arr[k] > temp){
                //如果arr[k]更大，说明原先arr[i]的位置应该存放arr[k]
                arr[i] = arr[k];
                //i位置被arr[k]填上了，相当于k位置空出来了，让i指针移动过来
                i = k;
                //然后k会指向新i的左子节点，然后进入下一次循环，继续寻找temp的位置
                // （其实这个可以写在for的第三个表达式处k = k * 2 + 1）
                k = i * 2 + 1;
            }
            //因为下方必然是大顶堆的形状，那么如果temp更大，说明i这里就是temp的位置
            else {
                arr[i] = temp;
                //temp的位置找到了，退出循环
                break;
            }
        }
    }

附录二：详细测试数据

冒泡：

​ 8w： 8189、8237、8203、8210、8220、8312、8250

​ 800w次10个数据排序： 1182、1170、1162、1218、1170、1171、1196

选择：

​ **8w： **2338、2339、2312、2310、2469、2288、2498

​ 800w次10个数据排序： 565、569、576、564、564、569、569

while插入：

​ 8w： 613、587、602、622、593、596、614

​ 800w次10个数据排序： 834、833、835、829、833、831、833

for插入：

​ 8w： 647、627、628、613、604、636、624

​ 800w次10个数据排序： 792、793、794、790、795、794、796

二分插入：

​ 8w： 1245、1208、1203、1185、1208、1176、1287（不理解为什么比插入慢。。。）

​ 800w次10个数据排序： 1232、1245、1266、1260、1253、1233、1242

希尔：

​ 8w： 12、17、12、12、11、11、11

​ 800w： 1855、1986、2146、2086、2067、1964、1993

​ 8000w： 29540、30355、28921、29402、32338、30412、26619

​ 800w次10个数据排序： 947、945、951、932、1001、957、1009

填坑法快速：

​ 8w： 10、11、10、12、11、7、12

​ 800w： 860、900、842、838、860、861、800

​ 8000w： 9864、9013、9205、9052、9348、10004、8940

​ 800w次10个数据排序： 1409、1469、1409、1415、1523、1454、1445

交换法快速：

​ 8w： 12、11、13、11、9、10、12

​ 800w： 911、936、887、861、921、972、937

​ 8000w： 9951、9987、10106、9986、9727、9808、9709

​ 800w次10个数据排序： 1342、1364、1335、1345、1345、1357、1363

归并：

​ 8w： 11、12、13、12、12、42、14

​ 800w： 1134、1167、1125、1160、1096、1117、1180

​ 8000w： 12160、12185、12163、12124、11896、12125、12196

​ 800w次10个数据排序： 3611、3599、3631、3637、3639、3548、3644

基数：

​ 8w： 26、14、25、26、14、25、13

​ 800w： 555、531、569、556、537、557、547

​ 2000w： 1359、1211、1245、1220、1230、1228、1263（1237.2）

​ 8000w： 内存溢出...这个需要开辟的空间和计数排序差不多

​ 800w次10个数据排序： 6863、6810、6825、6832、6827、6932、6858

计数：

​ 8w： 6、7、7、6、6、6、8

​ 800w： 388、379、387、379、398、391、385

​ 2000w： 954、942、983、926、995、933、996（961.4）

​ 8000w： 内存溢出...需要开辟880000000个int[]空间，一个int是4个字节，所需内存为：8.8亿✖4/(1024✖1024✖1024)=3.27GB的连续空间内存，当前环境溢出了，没法测

​ 800w次10个数据排序： 3044、2952、3032、2990、2987、2960、2911

堆排序：

​ 8w： 7、6、6、7、5、7、6

​ 800w： 453、394、397、433、348、305、317

​ 2000w： 1004、1320、823、821、1073、1157、1297（1070.8）

​ 8000w： 3385、4329、4258、4228、3403、3403、4280

​ 800w次10个数据排序： 689、699、671、693、701、703、699

JDK排序Arrays.sort()：

​ 8w： 19、12、21、9、21、19、12

​ 800w： 754、713、797、749、717、731、722

​ 8000w： 7608、7484、7798、7424、8199、7282、7548

​ 800w次10个数据排序： 773、769、770、771、770、771、772