开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 11 种内部排序算法大PK（Java 语言实现），究竟谁最快？ -> 正文阅读

[数据结构与算法]11 种内部排序算法大PK（Java 语言实现），究竟谁最快？

声明：

本篇文章用到的算法代码均是本人复习完对应的算法后，用自己的思维亲手编写的，由于时间问题，没有能够参考权威、标准的 api 源码，因此本文中的所有排序算法大概率还有优化的可能，执行效率大概率还可以更快，更稳，更省空间；希望大神发现以后可以在评论区广泛讨论，毕竟社区的力量是伟大的，开源的力量是无穷的！！！

一、PK 结果

废话不说，先看 PK 结果

1. 1000 级别数据量下各种排序算法排序速度比较

从图片可以看出，如果数据量非常小，堆排序、归并排序、快速排序、桶排序、timeSort排序、计数排序的表现都是非常优异的；那么数据量非常小的情况下，我们应该选择哪种排序算法进行排序呢？笔者推荐堆排序或归并排序或快速排序或timesort排序，以下是参考条件

冒泡排序属于暴力排序，对cpu的运算负载非常大，直接忽略
插入排序，希尔排序，选择排序属于低阶排序算法，在本轮测试中表现不是非常好，而且其一般用于其他排序算法的辅助性工具，所以忽略
堆排序没有用到辅助性的数组，所以它占用的空间可以忽略为待排序数组的大小，测试中耗时最短，对栈的依赖适中，可以接受
归并排序用到了辅助性数组，所以它占用的空间可以忽略为两倍的待排序数组的大小，测试中耗时最短，对栈的依赖适中，比堆排序稍差
快速排序没有用到辅助性的数组，所以它占用的空间可以忽略为待排序数组的大小，测试中耗时偏短，但对栈的依赖最高，所以递归深度最深，比堆排序稍差
桶排序严格意义上说是一种策略，一种思想，且桶排序的执行效率与编码人员的综合素质息息相关，是一种下限极低，上限极高的极度自由的排序算法，用到小数据量的排序有点大材小用
timeSort是 jdk 官方默认排序算法，能被官方作为默认的排序算法，必然非常优秀；且它结合了归并排序和插入排序的优点
基数排序用到了辅助性数组，所以它占用的空间可以忽略为两倍的待排序数组的大小，测试中耗时偏高，但空间复杂度极低，也比较优秀
计数排序用到了模板性的辅助数组，所以它占用的空间可以很小，也可以很大，取决于待排序数组的分布情况，但时间复杂度极低，也比较优秀，如果待排序数组的最大最小值较小，可以考虑

?2. 10000 级别数据量下各种排序算法排序速度比较

从图片可以看出，如果?timeSort排序，堆排序，归并排序，快速排序，基数排序均可作为选择，计数排序需要开发人员判断待排序序列的取值范围再做打算

? 3. 100000 级别数据量下各种排序算法排序速度比较

从图片可以看出，如果数据量稍微大的情况下，因此数据量稍微大的情况下?timeSort排序，堆排序，归并排序，快速排序均可作为选择；至于冒泡排序，插入排序，希尔排序，选择排序，在十万级别数据量及以上的情况下可以彻底放弃了，性能差距非常大；对其余排序算法做简单分析

可以明显看出，基数排序算法从此刻开始，已经有点力不从心了，所以如果数据量以万为单位的话，可以基数排序算法了
计数排序算法的变现也比较优秀，但是它还是老问题，需要开发人员判断待排序序列的取值范围再做打算，否则可能会太过耗费内存空间
快速排序在到达 100000 这个级别（甚至更多）的时候，会明显的暴露出一个问题——对栈（递归）的依赖太高了，如果不修改参数，大概率会出现爆栈的情况，运行时，需要配置以下参数给 jvm 虚拟机

# 具体值根据实际情况确定

# -Xms: 设置初始化堆内存大小
# -Xmx: 设置最大可分配堆内存大小
# -Xss: 栈内存大小,设置单个线程栈大小
# -XX:newSize：表示新生代初始内存的大小，应该小于-Xms的值
# -XX:MaxnewSize：表示新生代可被分配的内存的最大上限；当然这个值应该小于-Xmx的值
# -Xmn：至于这个参数则是对 -XX:newSize、-XX:MaxnewSize两个参数的同时配置，也就是说如果通过-Xmn来配置新生代的内存大小

-Xmx2048m -Xms1024m -Xmn512m -Xss256m

4. 1000000 级别数据量下各种排序算法排序速度比较

从图片可以看出，如果数据量偏大的情况下，timeSort 排序算法的表现依旧非常卓越，必然为首选；因此数据量偏大的情况下?timeSort排序，归并排序，堆排序，快速排序，桶排序均可作为选择，对其余排序算法做简单分析

堆排序、归并排序在百万级数据量下的表现差距还不是很明显，且实际表现都比较优秀，可以作为选择
快速排序需要注意的是，从 100000 这个级别开始就会出现明显的爆栈问题，但是其综合变现还是非常优秀的，如果要使用，注意配置 jvm 参数
可以明显看出，在数据量达到百万级别甚至更多的情况下，桶排序开始发力了，且不鸣则已，一鸣惊人
计数排序算法的变现尤其优秀，但是它还是老问题，需要开发人员判断待排序序列的取值范围再做打算，否则可能会太过耗费内存空间

4. 10000000 级别数据量下各种排序算法排序速度比较

从图片可以看出，如果数据量较大的情况下，桶排序算法强悍的统治力已经显现；除此之外数据量较大的情况下?timeSort排序，归并排序，快速排序，桶排序均可作为选择，对其余排序算法做简单分析

可以明显看出，堆排序算法从此刻开始，已经有点力不从心了，有点跟不上老对手归并排序的步伐了，所以如果数据量以千万为单位甚至更多的话，可以忽略堆排序算法了
计数排序的表现虽然十分亮眼，但是根据其特性，笔者建议，在数据量达到千万级别甚至更多的情况下，不要考虑计数排序了，否则参考模板给内存空间的压力是在太大了

5. 100000000 级别数据量下各种排序算法排序速度比较

从图片可以看出，如果数据量较大的情况下，桶排序算法已经可以做到一枝独秀了；除此之外数据量较大的情况下?timeSort排序，归并排序，快速排序，桶排序均可作为选择，对其余排序算法做简单分析

可以明显看出，堆排序算法在此刻已经被彻底淘汰
根据实战，可以得出一个结论，如果数据量以亿为单位，首选桶排序，可以这么说，桶排序就是为大数据量排序量身定制的，在足够大的数据量下，无论是作为武林盟主（IT界被人人奉为经典的排序王者）的快速排序还是身居兵马大元帅（被 Java 和 Python 钦点为官方默认排序算法）的 TimeSort ，都在绝对实力的面前显得黯然失色！！！

二、算法分析

1. 通用排序下的王者，不分情形下的巅峰

从始至终，你可以看到有两种排序算法一直处于巅峰状态，它们就是——归并排序、快速排序、TimeSort排序。因此，无论在何种情况下，你都可以毫不犹豫的选择归并排序或快速排序或TimeSort排序进行对任意目标数据的排序操作，它们绝对不会让你失望；那么他们三者，谁最强？下面进行分析

归并排序不仅快，而且稳，无论数据是全部有序，还是部分有序甚至完全倒序的情况下，他都可以做到一如既往的快，这就是王者的实力！可以说是宗师般的存在，这也是 TimeSort 将归并作为主要底层排序算法的底气所在，因此说归并排序是曾经的王者，教科书般的典范自然毫不夸张
快速排序在绝大多数情况下，的确要比归并排序更快，但是它有两个缺点——其一是不稳定，如果数据在大致有序甚至完全有序的情况下，快排的效率会大打折扣，可谓是一步一坑！要比归并慢很多；其二是快排对栈内存的依赖太高了，在一般的情况下，数据量达到 10万级别，就会出现爆栈的情况，需要修改 jvm 运行参数，否则会直接奔溃
TimeSort 排序算法是一种混合型的排序算法，和归并，快排并不是完全一样的类型；但是从它一出生那一刻起，便注定了荣华富贵，师承天下第一的归并排序，还又使用插入排序将存在的逆序序列矫正，最后将多个有序的序列利用归并排序合并，无论在那种情况，TimeSort 都比归并排序有过之而无不及，可谓是青出于蓝而胜于蓝。因此 TimeSort 是当之无愧的天下第一

综上所述，如果说归并排序是张三丰，那么 TimeSort 就是张无忌，从对武学的修养，领悟，造诣方面讲，张无忌自然不是张三丰的对手，甚至不在一个级别，但是若真起来，张三丰也不一定能打赢张无忌，毕竟九阳神功提供强大的源源不断的内力，乾坤大挪移更是开挂般的存在，可以瞬间恢复伤势；那么快速排序是谁？自然是?常胜宝树王，论综合实力，不敌张三丰与张无忌，但是若配合圣火令中的武功，有时候张无忌也不敌

2. 术业专攻

是个人就有优缺点，同样排序算法也一样；归并排序没有缺点吗？有！归并排序需要用到额外的数组，内存空间更大，而冒泡排序不需要用到额外的内存空间；TimeSort没有缺点吗？有，数据量极大的情况下，没有桶的思想，属实更不上时代的步伐；快速排序缺点不止一个，就更不用说了。所以要想在每种情况下都想得到最快的排序结果，单独使用一种排序算法肯定做不到，得分情况而论；以下情况不一定就是最优解，需要配合各自机器的配置特点进一步分析

Ⅰ10000 及以下数据量排序算法的选择

在数据完全有序或完全倒序的情况下，TimeSort排序的表现最为优秀

在数据部分有序的情况下，堆排序、归并排序、快速排序、计数排序、TimeSort排序会轮流登上王者，可随意选择，但注意计数排序的特性

Ⅱ 100000 左右数据量排序算法的选择

在数据完全有序或完全倒序的情况下，TimeSort 的表现最为优秀

在数据部分有序的情况下，如果取值范围不是很大，计数排序的表现最为优秀

在数据部分有序，且确定不适合使用计数排序的情况下，堆排序、归并排序、快速排序、TimeSort排序会轮流登上王者，可随意选择

Ⅲ 100000 左右数据量排序算法的选择

经核实，在数据完全有序或完全倒序的情况下，TimeSort 的表现最为优秀

在数据部分有序的情况下，如果取值范围不是很大，计数排序的表现最为优秀

在数据部分有序，且确定不适合使用计数排序的情况下堆排序、归并排序、快速排序、TimeSort排序会轮流登上王者，可随意选择

Ⅳ?1000000 左右数据量排序算法的选择

在数据完全有序或完全倒序的情况下，TimeSort 的表现最为优秀

在数据部分有序的情况下，如果取值范围不是很大，计数排序的表现最为优秀

在数据部分有序，且确定不适合使用计数排序的情况下，桶排序、堆排序、归并排序、快速排序、TimeSort排序会轮流登上王者，可随意选择

Ⅴ 10000000 及以上左右数据量排序算法的选择

在数据完全有序或完全倒序的情况下，TimeSort 的表现最为优秀

在数据部分有序情况下，桶排序一直处于巅峰，第一梯队首选桶排序，第二梯队为?TimeSort排序，第三梯队为快速排序，第四梯队为归并排序

三、代码分享

传送门（已设置终生免费下载，可放心下载）

1.项目结构

2.源码

时间工具类

package com.lanyue.sort.util;

public class TimeUtil {

    private long startTime;
    private long endTime;

    private void init(){
        this.startTime = 0L;
        this.endTime = 0L;
    }

    public void start(){
        init();
        this.startTime = System.currentTimeMillis();
    }

    public void end(){
        this.endTime = System.currentTimeMillis();
    }

    public long getSpendTime(){
        return this.endTime - this.startTime;
    }
}

排序工具类

package com.lanyue.sort.util;

import com.lanyue.sort.impl.*;
import com.lanyue.sort.interstand.Sort;
import java.lang.reflect.Constructor;
import java.util.List;
import java.util.Random;

public class SortUtil {

    private int nums;
    private int[] data;
    // 计算性能的工具类
    private TimeUtil timeUtil;

    public SortUtil(int nums) {

        this.nums = nums;
        init();
        this.timeUtil = new TimeUtil();
    }

    public SortUtil(int[] data){
        this.nums = data.length;
        this.data = data;
        this.timeUtil = new TimeUtil();
    }

    public SortUtil(List<Integer> data){
        this.nums = data.size();
        for (int index = 1; index <= this.nums; index++){
            this.data[index - 1] = data.get(index - 1);
        }
        this.timeUtil = new TimeUtil();
    }

    // 造假数据
    private void init(){
        dataInit();
    }

    private void dataInit(){
        data = new int[this.nums];

        for (int index = 1; index <= this.nums; index++){
            data[index - 1] = new Random().nextInt(index);
            // data[index - 1] = this.nums - index;
            // data[index - 1] = index;

        }
    }

    public void doSort(String arithmetic, String sortName){
        timeUtil.start();

        try {
            Class sortClass = Class.forName(arithmetic);
            Constructor constructor = sortClass.getConstructor(int[].class, String.class);
            Sort sort = (Sort) constructor.newInstance(this.data, sortName);
            sort.handle();
            timeUtil.end();

            System.out.println(sort.getSortName() + " 算法对存在 " + this.nums + " 个元素的无序序列排序耗时 " + timeUtil.getSpendTime() + " ms");

        } catch (Exception e) {
            // System.out.println("未定位到指定的排序算法");
            e.printStackTrace();
        }

    }

    public void doCompare(){
        sortAnalyse(new BubbleSort(this.data, "冒泡排序"));
        sortAnalyse(new InsertionSort(this.data, "插入排序"));
        sortAnalyse(new ShellSort(this.data, "希尔排序"));
        sortAnalyse(new SelectionSort(this.data, "选择排序"));
        sortAnalyse(new HeadSort(this.data, "堆排序"));
        sortAnalyse(new MergeSort(this.data, "归并排序"));
        sortAnalyse(new QuickSort(this.data, "快速排序"));
        sortAnalyse(new BucketSort(this.data, "桶排序"));
        sortAnalyse(new TimeSort(this.data, "timeSort排序(jdk自带)"));
        sortAnalyse(new RadixSort(this.data, "基数排序"));
        sortAnalyse(new CountSort(this.data, "计数排序"));
    }

    private void sortAnalyse(Sort sort){
        // 保证每次比较时，待排序数据都是无序的
        init();

        timeUtil.start();

        sort.handle();

        timeUtil.end();

        System.out.println(sort.getSortName() + " 算法对存在 " + this.nums + " 个元素的无序序列排序耗时 " + timeUtil.getSpendTime() + " ms");
    }

    public void show(){
        for (int value : this.data){
            System.out.println(value + " ");
        }
    }

    public boolean jud(){
        for (int index = 2; index <= this.nums; index++){
            if (this.data[index - 1] < this.data[index - 1 - 1]){
                return false;
            }
        }

        return true;
    }
}

排序算法公用抽象类

package com.lanyue.sort.interstand;

import java.lang.reflect.Array;
import java.util.Arrays;

public abstract class Sort {
    // 排序算法名称
    private final String sortName;
    // 存放数据源
    private int[] data;
    // 记录元素的个数
    private final int length;

    public Sort(int[] data, String sortName){
        this.sortName = sortName;
        this.data = data;
        this.length = this.data.length;
    }

    public int getLength(){
        return this.length;
    }

    public String getSortName(){
        return this.sortName;
    }

    protected int getElement(int index){
        return this.data[index - 1];
    }

    protected void setElement(int index, int value){
        this.data[index - 1] = value;
    }

    protected void swapElement(int leftIndex, int rightIndex){
        int leftElementValue = getElement(leftIndex);
        setElement(leftIndex, getElement(rightIndex));
        setElement(rightIndex, leftElementValue);
    }

    public abstract void handle();

    protected void timeSort(){
        Arrays.sort(this.data);
    }
}

冒泡排序

package com.lanyue.sort.impl;

import com.lanyue.sort.interstand.Sort;

/**
 * 内部排序-冒泡排序
 *
 * 优点：思维简单，容易理解，不占用多余内存空间
 * 缺点：属于暴力排序，如果数据量过大，会给 cpu 带来极大的计算压力；是 “非常稳定的完整版” 的 O(n^2) 排序算法
 * 时间、空间复杂度：空间复杂度最低，时间复杂度最高
 * 适用场景：由于是暴力排序，所以是所有排序算法中最慢的一种，没有之一，不推荐在任何场景下使用
 */
public class BubbleSort extends Sort {

    public BubbleSort(int[] data, String sortName){
        super(data, sortName);
    }

    @Override
    public void handle() {
        for (int currTime = 1; currTime <= getLength(); currTime++){
            for (int index = 1; index <= getLength() - currTime; index++){
                if (getElement(index) > getElement(index + 1)){
                    swapElement(index, index + 1);
                }
            }
        }
    }
}

插入排序

package com.lanyue.sort.impl;

import com.lanyue.sort.interstand.Sort;

// 内部排序-插入排序
public class InsertionSort extends Sort {

    public InsertionSort(int[] data, String sortName){
        super(data, sortName);
    }

    @Override
    public void handle() {
        // 将 index 之前的视为已经排序好的子序列
        for (int index = 2; index <= getLength(); index++){
            moveElement(index);
        }
    }

    private void moveElement(int currIndex){
        int currentValue = getElement(currIndex);
        int moveSignIndex = currIndex;
        boolean isMoveSign = false;

        for (int index = currIndex - 1; index >= 1; index--){
            if (getElement(index) > currentValue){
                setElement(index + 1, getElement(index));

                isMoveSign = true;
                moveSignIndex = index;
            }
        }

        if (isMoveSign){
            setElement(moveSignIndex, currentValue);
        }
    }
}

希尔排序

package com.lanyue.sort.impl;

import com.lanyue.sort.interstand.Sort;

// 内部排序-插入排序-希尔排序
public class ShellSort extends Sort {

    public ShellSort(int[] data, String sortName){
        super(data, sortName);
    }

    @Override
    public void handle() {
        // 增量、步长
        int increment = 2;
        handleSort(increment);
    }

    private void handleSort(int increment){
        while (increment >= 1){
            for (int subSeqStartIndex = 1 + increment; subSeqStartIndex <= 2 * increment; subSeqStartIndex++){
                departSort(subSeqStartIndex, increment);
            }
            increment = increment / 2;
        }
    }

    private void departSort(int startIndex, int increment){
        for (int index = startIndex; index <= getLength(); index = index + increment){
            moveElement(index, increment);
        }
    }

    private void moveElement(int currIndex, int increment){
        int currentValue = getElement(currIndex);
        int moveSignIndex = currIndex;
        boolean isMoveSign = false;

        for (int index = currIndex - increment; index >= 1; index = index - increment){
            if (getElement(index) > currentValue){
                setElement(index + increment, getElement(index));

                isMoveSign = true;
                moveSignIndex = index;
            }
        }

        if (isMoveSign){
            setElement(moveSignIndex, currentValue);
        }
    }
}

选择排序

package com.lanyue.sort.impl;

import com.lanyue.sort.interstand.Sort;

// 内部排序-选择排序
public class SelectionSort extends Sort {

    public SelectionSort(int[] data, String sortName){
        super(data, sortName);
    }


    @Override
    public void handle() {
        for (int index = 1; index <= getLength(); index++){
            findMinimumElement(index, getLength());
        }
    }

    private void findMinimumElement(int startIndex, int endIndex){
        if (startIndex < endIndex){
            int minimumIndex = startIndex;
            int minimumValue = getElement(startIndex);

            for (int index = startIndex + 1; index <= endIndex; index++){
                if (getElement(index) < minimumValue){
                    minimumIndex = index;
                    minimumValue = getElement(index);
                }
            }

            if (startIndex != minimumIndex){
                swapElement(startIndex, minimumIndex);
            }
        }
    }
}

堆排序

package com.lanyue.sort.impl;

import com.lanyue.sort.interstand.Sort;

// 内部排序-选择排序-堆排序
public class HeadSort extends Sort {

    private int virLength;

    public HeadSort(int[] data, String sortName){
        super(data, sortName);
        init();
    }

    public int getVirLength() {
        return virLength;
    }

    public void setVirLength(int newVirLength) {
        this.virLength = newVirLength;
    }

    @Override
    public void handle() {
        handleSort();
    }

    private void handleSort(){
        while (getVirLength() > 0){
            swapElement(1, getVirLength());

            removeElement();
            adapter(1);
        }
    }

    private void init(){
        this.virLength = getLength();

        for (int index = getVirLength() / 2; index >= 1; index--){
            if (getElement(2 * index) > getElement(index) || ((2 * index + 1 <= getVirLength()) && (getElement(2 * index + 1) > getElement(index)))){
                int bigerIndex;

                if (2 * index + 1 > getVirLength()){
                    swapElement(index, 2 * index);
                    adapter(2 * index);

                }else {
                    if (getElement(2 * index + 1) > getElement(2 * index)){
                        bigerIndex = 2 * index + 1;

                    }else {
                        bigerIndex = 2 * index;
                    }

                    swapElement(index, bigerIndex);
                    adapter(bigerIndex);
                }
            }
        }
    }

    private void removeElement(){
        setVirLength(getVirLength() - 1);
    }

    // 小元素的下坠过程
    private void adapter(int index){
        // 有子节点
        if (index <= getVirLength() / 2){
            // 只有左子节点
            if (2 * index + 1 > getVirLength()){
                if (getElement(2 * index) > getElement(index)){
                    swapElement(index, 2 * index);
                    adapter(2 * index);
                }
            }else {
                int bigIndex = getElement(2 * index + 1) > getElement(2 * index) ? (2 * index + 1) : (2 * index);

                if (getElement(bigIndex) > getElement(index)){
                    swapElement(index, bigIndex);
                    adapter(bigIndex);
                }
            }
        }
    }

}

归并排序

package com.lanyue.sort.impl;

import com.lanyue.sort.interstand.Sort;

// 内部排序-归并排序
public class MergeSort extends Sort {

    private int[] tempData;

    public MergeSort(int[] data, String sortName){
        super(data, sortName);
        init();
    }

    private void init(){
        tempData = new int[getLength()];
        for (int index = 1; index <= getLength(); index++){
            tempData[index - 1] = -1;
        }
    }

    @Override
    public void handle() {
        depart(1, (getLength() + 1) / 2, getLength());
    }

    private void depart(int startIndex, int middleIndex, int endIndex){
        if (startIndex != endIndex){
            depart(startIndex, (startIndex + middleIndex) / 2, middleIndex);
            depart(middleIndex + 1, (middleIndex + 1 + endIndex) / 2, endIndex);

            merge(startIndex, middleIndex, endIndex);
        }
    }

    private void merge(int startIndex, int middleIndex, int endIndex){
        int signIndex = startIndex;

        int leftIndex = startIndex;
        int rightIndex = middleIndex + 1;

        while(signIndex <= endIndex){
            if (leftIndex <= middleIndex && rightIndex <= endIndex){
                if (getElement(leftIndex) < getElement(rightIndex)){
                    this.tempData[signIndex - 1] = getElement(leftIndex++);

                }else {
                    this.tempData[signIndex - 1] = getElement(rightIndex++);
                }

                signIndex++;

            }else if(leftIndex <= middleIndex && rightIndex > endIndex){
                this.tempData[signIndex - 1] = getElement(leftIndex++);
                signIndex++;

            }else if(leftIndex > middleIndex && rightIndex <= endIndex){
                this.tempData[signIndex - 1] = getElement(rightIndex++);
                signIndex++;
            }
        }

        for (int index = startIndex; index <= endIndex; index++){
            setElement(index, this.tempData[index - 1]);
        }
    }
}

快速排序

package com.lanyue.sort.impl;

import com.lanyue.sort.interstand.Sort;

// 内部排序-快速排序
public class QuickSort extends Sort {

    public QuickSort(int[] data, String sortName){
        super(data, sortName);
    }

    @Override
    public void handle() {
        if (getLength() >= 2){
            handleSort(1 ,getLength());
        }
    }

    private void handleSort(int leftIndex, int rightIndex){
        if (rightIndex - leftIndex >= 1 && leftIndex >= 1 && rightIndex <= getLength()){
            // 拿到本次排序中 基准 选定的正确的数列索引位置
            int pivotIndex = getNextPivotIndex(leftIndex, rightIndex);

            handleSort(leftIndex, pivotIndex - 1);
            handleSort(pivotIndex + 1, rightIndex);
        }
    }

    // 将比 基准 大的元素移动到基准的右边，反之，则移动到左边
    private int getNextPivotIndex(int leftIndex, int rightIndex){

        // 基于 随机基准数 的优化
        optimizeOnPivot(leftIndex, rightIndex);

        int pivotIndex;
        int pivotValue = getElement(leftIndex);

        // 1 代表此次移动 rightIndex 指针
        // 2 代表此次移动 leftIndex 指针
        int compareSign = 1;

        while (leftIndex != rightIndex){
            if (compareSign == 1){
                if (getElement(rightIndex) < pivotValue){
                    setElement(leftIndex, getElement(rightIndex));
                    compareSign = 2;
                    leftIndex++;

                }else{
                    rightIndex--;
                }

            }else{
                if (getElement(leftIndex) > pivotValue){
                    setElement(rightIndex, getElement(leftIndex));
                    compareSign=1;
                    rightIndex--;

                }else{
                    leftIndex++;
                }
            }
        }

        // 如果 leftIndex == rightIndex，则设置 pivotIndex = leftIndex
        pivotIndex = leftIndex;
        setElement(pivotIndex, pivotValue);
        return pivotIndex;
    }

    // 基于经典快速排序的优化
    private void optimizeOnPivot(int leftIndex, int rightIndex){
        /*
            由于快速排序每轮选取「子数组最左元素」作为「基准数」，因此在输入数组 完全有序 或 完全倒序 时， partition() 每轮只划分一个元素，达到最差时间复杂度 O(N^2)
            因此，可使用 随机函数 ，每轮在子数组中随机选择一个元素作为基准数，这样就可以极大概率避免以上劣化情况
            值得注意的是，由于仍然可能出现最差情况，因此快速排序的最差时间复杂度仍为 O(N^2)
        */
        // 在闭区间 [leftIndex, rightIndex] 随机选取任意索引，并与 nums[l] 交换
        int randomPivotIndex = (int)(leftIndex + Math.random() * (rightIndex - leftIndex + 1));
        swapElement(leftIndex, randomPivotIndex);
    }
}

桶排序

package com.lanyue.sort.impl;

import com.lanyue.sort.interstand.Sort;
import java.lang.reflect.Constructor;

/**
 * 内部排序-桶排序优化版
 *
 * 与其说桶排序是一种算法，不如说桶排序是一种思维，一种策略
 * 桶排序上限很高，下限也很低。算法的最终执行效率与编写代码的人的综合能力息息相关，可以说是最考验程序员能力的一种算法
 * 它可以比快速排序快，也可以比 选择/插入 排序慢；它可以和冒泡排序一样省内存空间，也可以和归并排序一样耗费内存空间
 *
 * 桶排序中
 * 可以直接定义所有的桶（费空间，省时间），也可以一桶多用（省空间，费时间）
 * 可以将桶设置的很大，也可以设置的很小
 * 可以在桶内使用堆排序、归并排序、快速排序等高阶排序，也可以使用冒泡排序，插入排序，选择排序等低阶排序
 */
public class BucketSort extends Sort {

    // 桶的容量，每个桶种最多可以存放多少个不同的元素（去重后的个数）
    private final int bucketVolume = 100000;
    // 桶内的排序算法
    private final String bucketInnerArithmetic = CountSort.class.getCanonicalName();

    // 最小桶的最小值
    private int startBucketSign;
    // 最大桶的最小值
    private int endBucketSign;

    // 各个桶的长度
    private int[] bucketLength;
    // 各个桶的当前索引（插入桶数据时用到）
    private int[] bucketCurrIndex;
    // 排序中需要用到的桶
    private int[][] bucketData;

    public BucketSort(int[] data, String sortName){
        super(data, sortName);
    }

    private int getMaxElement(){
        int maximum = getElement(1);

        for (int index = 2; index <= getLength(); index++){
            if (getElement(index) > maximum){
                maximum = getElement(index);
            }
        }

        return maximum;
    }

    private int getMinElement(){
        int minimum = getElement(1);

        for (int index = 2; index <= getLength(); index++){
            if (getElement(index) < minimum){
                minimum = getElement(index);
            }
        }

        return minimum;
    }

    // 将元素放进对应的桶
    private void putElementToBucket(){
        for (int index = 1; index <= getLength(); index++){
            int oneDim = (getElement(index) - startBucketSign) / bucketVolume;

            bucketData[oneDim][bucketCurrIndex[oneDim]] = getElement(index);
            bucketCurrIndex[oneDim] = bucketCurrIndex[oneDim] + 1;
        }
    }

    private void init(){
        startBucketSign = getMinElement() / bucketVolume * bucketVolume;
        endBucketSign = getMaxElement() / bucketVolume * bucketVolume;
        // 二维数组的 一维、二维 长度
        int oneDim = (endBucketSign - startBucketSign) / bucketVolume + 1;
        int twoDim;

        bucketLength = new int[oneDim];
        bucketCurrIndex = new int[oneDim];
        bucketData = new int[oneDim][];

        for (int index = 1; index <= oneDim; index++){
            bucketLength[index - 1] = 0;
            bucketCurrIndex[index - 1] = 0;
        }

        for (int index = 1; index <= getLength(); index++){
            oneDim = (getElement(index) - startBucketSign) / bucketVolume;
            bucketLength[oneDim] = bucketLength[oneDim] + 1;
        }

        for (int bucketSign = startBucketSign; bucketSign <= endBucketSign; bucketSign += bucketVolume){
            oneDim = (bucketSign - startBucketSign) / bucketVolume ;
            twoDim = bucketLength[oneDim];
            bucketData[oneDim] = new int[twoDim];
        }
    }

    @Override
    public void handle() {
        init();
        handleSort();
    }

    private void handleSort(){
        putElementToBucket();
        bucketDataSort();
    }

    private void bucketDataSort(){
        int index = 1;
        int oneDim;

        for (int bucketSign = startBucketSign; bucketSign <= endBucketSign; bucketSign += bucketVolume){
            // list.stream().mapToInt(Integer::valueOf).toArray();

            // 对桶内的数据进行排序
            oneDim = (bucketSign - startBucketSign) / bucketVolume;

            // auxSort(bucketData[oneDim]);
            auxSort(bucketData[oneDim], bucketInnerArithmetic, "桶内排序算法");

            // 将桶内排序好的数据放到原数据中
            copyValueFromBucketToData(index, bucketData[oneDim]);
            index += bucketData[oneDim].length;
        }
    }

    private void auxSort(int[] data, String auxArithmetic, String sortName){
        try {
            Class sortClass = Class.forName(auxArithmetic);
            Constructor constructor = sortClass.getConstructor(int[].class, String.class);
            Sort sort = (Sort) constructor.newInstance(data, sortName);
            sort.handle();

        } catch (Exception e) {
            System.out.println("[桶排序]: 未定位到指定的排序算法");
        }
    }

    private void auxSort(int[] data){
        new MergeSort(data, "桶内排序算法").handle();
    }

    private void copyValueFromBucketToData(int startIndex, int[] tempData){

        if (tempData.length >= 1){
            for (int index = 1; index <= tempData.length; index++){
                setElement(startIndex++, tempData[index - 1]);
            }
        }
    }
}

基数排序

package com.lanyue.sort.impl;

import com.lanyue.sort.interstand.Sort;

// 内部排序-桶排序-基数排序
public class RadixSort extends Sort {

    private int[][] bitData;
    private int[] bitSignIndex;

    public RadixSort(int[] data, String sortName){
        super(data, sortName);
        init();
    }

    private void init(){
        bitData = new int[10][getLength()];
        bitSignIndex = new int[10];

        initBitData();
    }

    private void initBitSignIndex(){
        for (int index = 0; index <= 9; index++){
            bitSignIndex[index] = 0;
        }
    }

    private void initBitData(){
        for (int bit = 0; bit <= 9; bit++){
            for (int index = 1; index <= getLength(); index++){
                bitData[bit][index - 1] = -1;
            }
        }
    }

    @Override
    public void handle() {
        handleSort();
    }

    private void handleSort(){
        int maxBit = getMaxBit();

        for (int radixIndex = 1; radixIndex <= maxBit; radixIndex++){
            initBitSignIndex();
            initBitData();

            for (int index = 1; index <= getLength(); index++){
                int bitPos = getPosValueMath(getElement(index), radixIndex);
                bitData[bitPos][bitSignIndex[bitPos]++] = getElement(index);
            }

            copyDataToData();

        }
    }

    // 得到当前数值的最大位数
    private int getMaxBit(){
        int maximum = getElement(1);

        for (int index = 2; index <= getLength(); index++){
            if (getElement(index) > maximum){
                maximum = getElement(index);
            }
        }

        return (int) Math.log10(maximum) + 1;
    }

    // 得到一个数值的总位数
    private int getBit(int data){
        return (int) Math.log10(data) + 1;
    }

    // 得到 elementValue 第 position 位的值（从右往左）
    private int getPosValue(int elementValue, int bit){
        String elementString = String.valueOf(elementValue);
        if (bit > elementString.length()){
            return 0;

        }else {
            return Integer.parseInt(String.valueOf(elementString.charAt(getBit(elementValue) - bit)));
        }
    }

    // 得到 elementValue 第 position 位的值（从右往左）
    private int getPosValueMath(int elementValue,int position){
        if(position < 1){
            return -1;
        }
        return (int)(elementValue / Math.pow(10,position - 1) % 10);
    }

    // 将 本次按位 排好序的数 赋值给 tempData
    private void copyDataToData(){
        int index = 1;

        for (int oneDim = 0; oneDim <= 9; oneDim++){
            for (int twoDim = 0; twoDim <= getLength(); twoDim++){
                if (bitData[oneDim][twoDim] != -1){
                    setElement(index, bitData[oneDim][twoDim]);
                    index++;

                }else{
                    break;
                }
            }
        }
    }
}

计数排序

package com.lanyue.sort.impl;

import com.lanyue.sort.interstand.Sort;

// 内部排序-桶排序-计数排序
public class CountSort extends Sort {

    // 为了减少参照数据的长度，特意设置偏移量
    private int offset;
    // 参照数组的一维长度
    private int virLength;
    private int[][] countData;

    public CountSort(int[] data, String sortName){
        super(data, sortName);
    }

    private int getMaxElement(){
        int maximum = getElement(1);

        for (int index = 2; index <= getLength(); index++){
            if (getElement(index) > maximum){
                maximum = getElement(index);
            }
        }

        return maximum;
    }

    private int getMinElement(){
        int minimum = getElement(1);

        for (int index = 2; index <= getLength(); index++){
            if (getElement(index) < minimum){
                minimum = getElement(index);
            }
        }

        return minimum;
    }

    private void init(){
        offset = getMinElement();
        virLength = getMaxElement() - getMinElement() + 1;
        countData = new int[virLength][1];
    }

    @Override
    public void handle() {
        init();
        handleSort();
    }

    private void handleSort(){
        initCountData();
        initData();
    }

    private void initCountData(){
        for (int index = 1; index <= virLength; index++){
            countData[index - 1][0] = 0;
        }

        for (int index = 1; index <= getLength(); index++){
            countData[getElement(index) - offset][0] = countData[getElement(index) - offset][0] + 1;
        }
    }

    private void initData(){
        int currIndex = 1;
        for (int index = 1; index <= getLength(); index++){
            setElement(index, -1);
        }

        for (int index = 1; index <= virLength; index++){
            int occurTimes = countData[index - 1][0];
            if (occurTimes >= 1){
                for (int currTime = 1; currTime <= occurTimes; currTime++){
                    setElement(currIndex, offset + index - 1);
                    currIndex++;
                }
            }
        }
    }
}

TimeSort 排序（JDK默认排序算法）

package com.lanyue.sort.impl;

import com.lanyue.sort.interstand.Sort;

public class TimeSort extends Sort {

    public TimeSort(int[] data, String sortName){
        super(data, sortName);
    }

    @Override
    public void handle() {
        super.timeSort();
    }
}

3.使用方法

package com.lanyue.sort;

import com.lanyue.sort.impl.*;
import com.lanyue.sort.util.SortUtil;

public class Test {

    public static void main(String[] args) {
        performPK();
        // arithSort();
    }

    // 比较所有排序算法的执行效率
    private static void performPK(){
        // 掺入参数为待排序元素的个数
        SortUtil util = new SortUtil(100000000);
        util.doCompare();
    }

    // 查看指定排序算法的执行效率并且输出排序结果
    private static void arithSort(){
        // 掺入参数为待排序元素的个数
        SortUtil util = new SortUtil(10000000);
        // 第一个参数为 指定的排序算法，第二个参数为排序算法名
        util.doSort(TimeSort.class.getCanonicalName(), "桶排序");
        // util.show();
        System.out.println(util.jud());
    }
}