排序算法

偷得浮生半日闲。想了之前面试的一些经历，虽然没有涉及到算法，但是想起自己掌握一个东西，还真得反复斟酌和深入思考，一时的理解总敌不过岁月的擦抹。总结和理解下当前的一些主要排序算法。

算法与复杂度

稳定性及复杂度概述

排序算法	是否稳定	最坏时间复杂度	平均时间复杂度	最好时间复杂度	空间复杂度
直接插入	稳定	O(n^2)	O(n^2)	O(n)	O(1)
二分插入	稳定	O(n^2)	O(n^2)	O(nlog2(n))	O(1)
希尔排序	不稳定	O(n^2)	O(n^1.3)	O(n))	O(1)
冒泡排序	稳定	O(n^2)	O(n^2)	O(n)	O(1)
选择排序	不稳定	O(n^2)	O(n^2)	O(n^2)	O(1)
堆排序	不稳定	O(nlog2(n))	O(nlog2(n))	O(nlog2(n))	O(1)
快速排序	不稳定	O(n^2)	O(nlog2(n))	O(nlog2(n))	O(1)
归并排序	稳定	O(nlog2(n))	O(nlog2(n))	O(nlog2(n))	O(n)
计数排序	稳定	O(n)	O(n)	O(n)	O(n)
桶排序	稳定	O(n)	O(N+C)	O(n)	O(N+M)

算法的优化点与解析

• 直接插入法处理的待排数组是有序数组时：
  • 当处理顺序与有序数组的顺序表现一致时，时间复杂度为O(n);
  • 当处理顺序与有序数组的顺序表现相反时，为最坏场景。　　
• 二分插入在直接插入法取得0(n)时间复杂度时，其最好表现也是O(nlog2(n))。但是当n很大时，其搜索插入点时比较的次数会比直接插入法少得多，但是由于找到插入点，两个算法都需要对后续部分元素进行挪动，故时间复杂度一样为O(n^2)。=。=二分插入大喊我不服！　　
• 希尔排序对比与直接插入法，当待排数组元素个数n值很大时，增量m(数据项的距离)也很大，数据项每一趟排序需要的个数很少;当n值减小时每一趟需要和动的数据增多，但已经接近于排序后的最终位置。这使得希尔排序效率比插入排序高很多。但是对于n很大时，我们会选择更好的算法，如快排等！需要注意的是，希尔的最坏时间复杂度会收增量算法的影响。
• 当在某一趟冒泡排序中没有出现过元素交换，则认为剩余的元素都是有序状态，可以直接停止！
• 选择排序实际上我是不推荐使用，在任何场景下都会默认走一遍比较，就是那么辣鸡！
• 快排优化方案
  • 三平均分区法，选择待排数组的第一个数作为中轴，而是选用待排数组最左边、最右边和最中间的三个元素的中间值作为中轴。
  • 当快排处理大数据过程中，当数据集被递归到较小时，改用堆排序（Instrosirt）来克服在处理小规模数据中复杂的中轴选择；或者在规模达到一定小的情况下，改用插入排序，这时几乎是线性处理效果。
  • 当块排分区的所有元素都一样时会出现选轴糟糕状态，可以把分区分成三部分，小于等于大于中轴值;或当发现最左和最右两个值相等时采用其他排序算法。 　　 　　　　　
• 快速排序过程中，每次划分分区为1和n-1为最坏情况，此时为时间复杂度为O(n^2);而最好的情况出现在每次划分的分区都为n/2。 　　
• 上述表格中，快速排序的空间复杂度O(1)为辅助变量空间;但是对于递归空间来说，当出现最坏情况，其会被退化为冒泡排序，且空间复杂度为O(n);当在最有情况下，其空间复杂度为O(log2(n))。
• 归并排序中，所使用的空间为临时空间n加上递归使用的空间log2(n)，故空间复杂度为O(n)。
• 对于桶排序，如N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：
  O(N)+O(M(N/M)log(N/M))=O(N+N(logN-logM))=O(N+NlogN-NlogM)
  当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。
  总结：桶排序的平均时间复杂度为线性的O(N+C)，其中C=N(logN-logM)，如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。

算法实现

考虑到java编程中，除了基础类型的比较之外经常涉及到对象之间的比较。意味着，特定类实现 Comparable 接口即可在逻辑上给定对象之间的比较逻辑。下面算法的实现大部分都是基于 Comparable 实例展开。

直接插入

/**
 * 插入排序 - 直接插入（稳定）
 * 基本思想：从待排数组第二位到尾部最后一位元素，依次向元素的前方比较插入;后一趟开始插入时，默认前面的元素是有序的。
 *
 * @param types
 * @param <SortType>
 */
public static <SortType extends Comparable<? super SortType>> void insertionSort(SortType[] types) {

    if(types == null || types.length == 0){
        return;
    }
    int length = types.length;
    //插入排序默认n-1是已排序的
    for (int i = 1; i < length; i++) {
        SortType temp = types[i];
        //从temp的前一位开始比较
        int j = i - 1;
        while (j >= 0 && temp.compareTo(types[j]) < 0) {
            //如果比较数比temp大，则把比较数赋值给其后面的一个数
            //赋值完之后“j这个位置的值暂时不确定”
            types[j + 1] = types[j];
            j--;
        }
        //赋值时机出现在：
        //1. 如果“前一个数”的下标已经是0，即意味着插入的数是目前所有比较数中最小的，插在头部
        //2. 如果“前一个数”比temp小时，则上述“暂时不确定值的位置”插入temp。
        types[j + 1] = temp;
    }
}

二分插入

/**
 * 插入排序 - 二分插入（稳定）
 * 基本思想：基于直接插入的过程中“后一趟开始插入是，默认前面的元素是有序的”的前提，可以选择对前面的元素进行二分查找后
 * 找到小于“当前想要插入元素”的最大元素，把元素的后面所有元素（但在当前想要插入元素之前）往后挪一位，再把想要插入的元
 * 素插入留空未知。
 *
 * @param types
 * @param <SortType>
 */
public static <SortType extends Comparable<? super SortType>> void bInsertSort(SortType[] types) {

    if(types == null || types.length == 0){
        return;
    }
    int length = types.length;
    //插入排序默认n-1是已排序的
    for (int i = 1; i < length; i++) {
        SortType temp = types[i];
        int start = 0;
        int end = i - 1;
        //跳出循环时必定，end为小于temp的最大元素，start为大于temp的最小元素
        while (start <= end) {
            int mid = (start + end) / 2;
            if (types[mid].compareTo(temp) < 0) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        int j = i;
        while (j > end && j > 0) {
            types[j] = types[j - 1];
            j--;
        }
        types[end + 1] = temp;
    }
}

希尔排序

/**
  * 插入排序 - 希尔排序（不稳定）
  * 基本思想：高级版的插入排序，制定增量规则进行分组插入，逐步让增量变小直到为1完成排序
  *
  * @param types
  * @param <SortType>
  */
 public static <SortType extends Comparable<? super SortType>> void shellSort(SortType[] types) {
 
     if(types == null || types.length == 0){
         return;
     }
     int length = types.length;
     int increment = length / 2;
     //增量递减
     while (increment > 0) {
         //在增量区间内进行插入排序，保证所有数都能被处理
         for (int i = 0; i < increment; i++) {
             //插入排序
             for (int j = i + increment; j < length; j += increment) {
                  SortType temp = types[j];
                  int k = j - increment;
                  while (k >= 0 && types[k].compareTo(temp) > 0) {
                      types[k + increment] = types[k];
                      k -= increment;
                  }
                  types[k + increment] = temp;
             }
         }
         increment /= 2;
     }
 }

冒泡排序

/**
 * 冒泡排序（稳定）
 * 基本思想：第一次从头部开始向尾部冒泡，第一次过后最大的数出现在尾部;第二次也是从头部开始，不过只需要处理到倒数第二位...依次处理
 *
 * @param types
 * @param <SortType>
 */
public static <SortType extends Comparable<? super SortType>> void bubbleSort(SortType[] types) {

    if(types == null || types.length == 0){
        return;
    }
    int lenght = types.length;
    boolean exchange;
    for (int i = 0; i < lenght - 1; i++) {
        exchange = false;
        for (int j = 0; j < lenght - i - 1; j++) {
            if (types[j].compareTo(types[j + 1]) > 0) {
                SortType temp = types[j];
                types[j] = types[j + 1];
                types[j + 1] = temp;
                exchange = true;
            }
        }
        if(!exchange){
            break;
        }
    }
}

选择排序

/**
 * 选择排序（不稳定）
 * 基本思想：其实类似与冒泡排序，区别在于不直接交换且每一趟只比较当“前趟的最后一位元素”。
 * 从头部到“尾部往前一位”找出最大的值，并放到尾部
 *
 * @param types
 * @param <SortType>
 */
public static <SortType extends Comparable<? super SortType>> void selectSort(SortType[] types) {

    if(types == null || types.length == 0){
        return;
    }
    int length = types.length;
    for (int i = 0; i < length - 1; i++) {
        //默认当前末尾最大
        int max = length - 1 - i;
        for (int j = 0; j < length - 1 - i; j++) {
            if (types[j].compareTo(types[max]) > 0) {
                max = j;
            }
        }
        if (max != length - 1 - i) {
            SortType temp = types[max];
            types[max] = types[length - 1 - i];
            types[length - 1 - i] = temp;
        }
    }
}

堆排序

/**
 * 堆排序（不稳定）
 * 整个堆排序过程分为：
 * 1. 初始化大/小根堆
 * 2. 交换极值重新调整堆{@link #headAdjust}
 *
 * @param types
 * @param <SortTpye>
 */
public static <SortTpye extends Comparable<? super SortTpye>> void heapSort(SortTpye[] types) {

    if(types == null || types.length == 0){
        return;
    }
    int length = types.length;
    //从下往上建堆，且保证从非叶子结点开始建堆
    for (int i = length / 2 - 1; i >= 0; i--) {
        headAdjust(types, i, length - 1);
    }
    //交换堆顶之后重新调整
    for (int i = length - 1; i >= 0; i--) {
        SortTpye temp = types[i];
        types[i] = types[0];
        types[0] = temp;
        headAdjust(types, 0, i - 1);
    }
}

/**
 * 从数组按照下标展开构建完全二叉树时，若非结点结点下边为n，则左孩子为2n+1，右孩子为2n+2;
 *
 * @param types
 * @param start
 * @param end
 * @param <SortTpye>
 */
public static <SortTpye extends Comparable<? super SortTpye>> void headAdjust(SortTpye[] types, int start, int end) {
    int lChild = 2 * start + 1;
    int rChild = 2 * start + 2;
    //假设当前父节点最大
    int max = start;
    //保证从非叶子结点开始检索,若一个孩子为偶数结点，则按照“右孩子为2n+2”的规则/2-1;
    int flag = (end % 2 == 0 ? end / 2 - 1 : end / 2);
    if (start <= flag) {
        //如果左结点不超过end且比父亲结点大
        if (lChild <= end && types[lChild].compareTo(types[max]) > 0) {
            max = lChild;
        }
        //如果右结点不超过end且比父亲结点大
        if (rChild <= end && types[rChild].compareTo(types[max]) > 0) {
            max = rChild;
        }
        //如果发生交换，则交换后递归调整
        if (max != start) {
            SortTpye temp = types[max];
            types[max] = types[start];
            types[start] = temp;
            headAdjust(types, max, end);
        }
    }
}

快速排序

/**
 * 快速排序（不稳定）
 * 基本思想：每一趟排序都会把待排的数据分割成独立的两部分，其中一部分的所有数据会比另一部分的所有数据都要小。
 * 递归处理
 *
 * @param types
 * @param <SortTpye>
 */
public static <SortTpye extends Comparable<? super SortTpye>> void quickSort(SortTpye[] types, int start, int end){
    if(types == null || types.length == 0){
        return;
    }
    if(start < end){
        int position = getPosition(types, start, end);
        quickSort(types, start, position-1);
        quickSort(types, position+1, end);
    }
}

/**
 * 获取临街值
 * @param types
 * @param start
 * @param end
 * @param <SortTpye>
 * @return
 */
public static <SortTpye extends Comparable<? super SortTpye>> int getPosition(SortTpye[] types, int start, int end){
    SortTpye flag = types[start];
    while(start < end){
        //从尾部往前一直找，如果找到比flag小，则与第一个数交换
        while(start < end && types[end].compareTo(flag) >= 0){
            end --;
        }
        types[start] = types[end];
        //从头部往后一直找，如果找到比flag大，则
        while (start < end && types[start].compareTo(flag) <= 0){
            start++;
        }
        types[end] = types[start];
    }
    types[start] = flag;
    return start;
}

归并排序

/**
  * 归并排序（稳定）
  * 基本思想：分而治之，递归处理。
  *
  * @param types
  * @param start
  * @param end
  * @param <SortTpye>
  */
 public static <SortTpye extends Comparable<? super SortTpye>> void mergeSort(SortTpye[] types, int start, int end){
     if(types == null || types.length == 0){
         return;
     }
     int mid = (start + end)/2;
     if(start < end){
         mergeSort(types,start,mid);
         mergeSort(types,mid+1,end);
         merge(types,start,mid,end);
     }
 }

 /**
  * 合并两个元素数组
  *
  * @param types
  * @param start
  * @param mid
  * @param end
  * @param <SortTpye>
  */
 public static <SortTpye extends Comparable<? super SortTpye>> void merge(SortTpye[] types,int start, int mid, int end){
     SortTpye[] temp = (SortTpye[]) new Comparable[end-start+1];
     int i = start;//左侧数组头部
     int j = mid + 1; //右侧数组头部
     int index = 0;
     //存放到临时区，直到其中一个数组全部填入
     while(i <= mid && j <= end){
         if(types[i].compareTo(types[j]) < 0){
             temp[index++] = types[i++];
         }else{
             temp[index++] = types[j++];
         }
     }
     //左侧数组是否剩余
     while(i <= mid){
         temp[index++] = types[i++];
     }
     //右侧数据是否剩余
     while(j <= end){
         temp[index++] = types[j++];
     }

     for(index = 0; index < temp.length; index++){
         types[start+index] = temp[index];
         temp[index] = null;
     }
     temp = null;
 }

计数排序

/**
 * 计数排序
 * 基本思想：对于待排数组中的某一个元素types[n],确定小于types[n]的元素个数
 * 需要借助的空间，假如待排数组中最小对象的值为10，最大对象的值为100，则需要一个(100-10+1)的辅助空间，
 * 适合的场景：数据值比较集中的待排数集
 *
 * @param nums
 */
public static void countSort(Integer[] nums){

    if(nums == null || nums.length == 0){
        return;
    }
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    int length = nums.length;
    for(int i = 0; i < nums.length; i++){
        max = Math.max(max, nums[i]);
        min = Math.min(min, nums[i]);
    }

    int tLength = max-min+1;
    int[] temp = new int[tLength];

    //在temp空间中存放每个数字出现的次数
    for(int i = 0; i < length; i++){
        temp[nums[i]-min]++;
    }


    int index = 0;
    for(int i = 0; i < tLength; i++){
        //某个位置的个数不为0
        while(temp[i]-- > 0){
            nums[index++] = i + min;
        }
    }
}

桶排序

/**
 * 桶排序
 * 基本思想：先确定数值范围（这部分和技术排序相同），再按照一定的规则初始化桶
 * 初始化完桶之后里面的元素为排序，可选择任意一种方式进行排序。
 *
 * @param nums
 */
public static void bucketSort(Integer[] nums){

    if(nums == null || nums.length == 0){
        return;
    }
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    int length = nums.length;
    for(int i = 0; i < length; i++){
        max = Math.max(max, nums[i]);
        min = Math.min(min, nums[i]);
    }

    //初始化桶
    //可以看出，如果max、min区间特别大但是数组个数特别小，则会有很多桶分布
    int bucketNum = (max - min) / length + 1;
    ArrayList<ArrayList<Integer>> bucketArry = new ArrayList<>(bucketNum);
    for (int i = 0; i < bucketNum; i++){
        bucketArry.add(new ArrayList<>());
    }

    //入桶
    for(int i = 0; i < length; i++){
        int index = (nums[i]-min) / length;
        bucketArry.get(index).add(nums[i]);
    }

    //对每个桶进行排序，这里借用java api直接排序
    for(int i = 0; i < bucketArry.size(); i++){
        Collections.sort(bucketArry.get(i));
    }
}

10W随机数测试

直接上测试代码

    public static void main(String[] args){
        int num = 100000;
        Integer[] types = new Integer[num];
        Random random = new Random();
        for(int i = 0; i <num; i++){
           types[i] = random.nextInt(num);
        }
        long time1 = System.currentTimeMillis();
//        Sort.insertionSort(types);
//        Sort.bInsertSort(types);
//        Sort.shellSort(types);
//        Sort.bubbleSort(types);
//        Sort.selectSort(types);
//        Sort.heapSort(types);
//        Sort.quickSort(types,0,num-1);
//        Sort.mergeSort(types,0,num-1);
//        Sort.countSort(types);
//        Sort.bucketSort(types);
          long time2 = System.currentTimeMillis();
          System.out.print(time2-time1 + "ms");
    }

由于每次测试花费时间都是重新产生数组，可能会导致排序的难度场景不太相同，但是对于整体验证复杂度还是可以比较直观体验。

测试机器：
	cpu： 4核   Intel(R) Core(TM) i5-6300HQ CPU @ 2.30GHz
	内存：8G
测试结果：
	直接插入：11782ms
	二分插入：8464ms
	希尔排序：65ms
	冒泡排序：56564ms
	选择排序：14697ms
	堆排序：72ms
	快速排序：61ms
	归并排序：115ms
	计数排序：11ms
	桶排序：62ms

忽略测试数据的随机性，大致参考总结为：

• 计数和桶排序都非常快，但是消耗了更多的额外空间，具体场景具体取舍
• 堆排序/快排序/归并排序表现差不多，这三者大部分场景下都优于希尔排序
• 数据量大适合快速排序和归并排序，数据量小可考虑堆排序，且堆排序稳定性最高

作者水平有限，本文仅供参考学习，如有错误遗漏，望慷慨指出！