数据结构十大经典排序算法总结

算法概述

算法分类

十种常见排序算法可以分为两大类：

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

算法复杂度

在面试中面试官一般会重点查考时间复杂度为O(n*logn)的排序算法，比如快速排序、归并排序和堆排序，这就需要我们掌握其原理和手撕算法。

相关概念

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当$n$变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模$n$的函数。

1.冒泡排序

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

1.1 算法描述

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤1~3，直到排序完成。

1.2 动图演示

1.3代码实现

public class bubble_sort {
    public int[] bubble_sort(int[] arr) {

        for (int i = 0;i< arr.length;i++) { //计数
            for (int j = 0;j<arr.length-1-i;j++) {
                if (arr[j] > arr[i]) { //相邻元素两两对比
                    int temp = arr[j+1]; //元素交换
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
}

时间复杂度：最好O(n),最坏O(n^2)
空间复杂度：O(1)

2、选择排序（Selection Sort）

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2.1 算法描述

$n$个记录的直接选择排序可经过$n-1$趟直接选择排序得到有序结果。具体算法描述如下：

• 初始状态：无序区为$R[1..n]$，有序区为空；
• 第$i$趟排序($i=1,2,3\dots n-1$)开始时，当前有序区和无序区分别为$R[1..i-1]$和$R(i..n）$。该趟排序从当前无序区中-选出关键字最小的记录 $R[k]$，将它与无序区的第$1$个记录R交换，使$R[1..i]$和$R[i+1..n)$分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
• $n-1$趟结束，数组有序化了。

2.2 动图演示

public class select_sort {
    public static int[] select_sort(int[] arr) {
        int len = arr.length;
        int minIndex,temp;
        for(int i = 0;i<len-1;i++) {
            minIndex = i;
            for (int j = i+1;j<len;j++) {
                if(arr[j]<arr[minIndex]) {
                    minIndex = j;
                }
            }
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        return arr;
    }
    public static void main(String args[]) {
        int[] arr = {3,38,44,5,47,15,36,26,27,2,46,4,19,50,48};
        int[] ans = select_sort(arr);
        for (int i : ans){
            System.out.println(i);
        }
    }
}

2.4 算法分析

表现最稳定的排序算法之一，因为无论什么数据进去都是$\mathrm{O}\left({\mathrm{n}}^2\right)$的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

3、插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

3.1 算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

3.2 动图演示

3.3代码实现

public class Insertion_Sort {
    public static int[] Insert_Sort(int[] arr) {
        int len = arr.length;
        int preIndex,current;
        for (int i = 1;i < len;i++) {
            preIndex = i-1;
            current = arr[i];
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex+1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex+1]=current;
        }
        return arr;
    }
    public static void main(String args[]) {
        int[] arr = {3,38,44,5,47,15,36,26,27,2,46,4,19,50,48};
        int[] ans = Insert_Sort(arr);
        for (int i : ans){
            System.out.println(i);
        }
    }
}

def bubbleSort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

3.4 算法分析

插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

4、希尔排序（Shell Sort）

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

4.1 算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

我们来看下希尔排序的基本步骤，在此我们选择增量$gap=length/2$，缩小增量继续以$gap=gap/2$的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

4.2 动图演示

4.3 代码实现

在希尔排序的理解时，我们倾向于对于每一个分组，逐组进行处理，但在代码实现中，我们可以不用这么按部就班地处理完一组再调转回来处理下一组（这样还得加个for循环去处理分组）比如[5,4,3,2,1,0] ，首次增量设gap=length/2=3,则为3组[5,2] [4,1] [3,0]，实现时不用循环按组处理，我们可以从第gap个元素开始，逐个跨组处理。同时，在插入数据时，可以采用元素交换法寻找最终位置，也可以采用数组元素移动法寻觅。希尔排序的代码比较简单，如下：

package sortdemo;

import java.util.Arrays;

/**
 * Created by chengxiao on 2016/11/24.
 */
public class ShellSort {
    public static void main(String []args){
        int []arr ={1,4,2,7,9,8,3,6};
        sort(arr);
        System.out.println(Arrays.toString(arr));
        int []arr1 ={1,4,2,7,9,8,3,6};
        sort1(arr1);
        System.out.println(Arrays.toString(arr1));
    }

    /**
     * 希尔排序 针对有序序列在插入时采用交换法
     * @param arr
     */
    public static void sort(int []arr){
        //增量gap，并逐步缩小增量
       for(int gap=arr.length/2;gap>0;gap/=2){
           //从第gap个元素，逐个对其所在组进行直接插入排序操作
           for(int i=gap;i<arr.length;i++){
               int j = i;
               while(j-gap>=0 && arr[j]<arr[j-gap]){
                   //插入排序采用交换法
                   swap(arr,j,j-gap);
                   j-=gap;
               }
           }
       }
    }

    /**
     * 希尔排序 针对有序序列在插入时采用移动法。
     * @param arr
     */
    public static void sort1(int []arr){
        //增量gap，并逐步缩小增量
        for(int gap=arr.length/2;gap>0;gap/=2){
            //从第gap个元素，逐个对其所在组进行直接插入排序操作
            for(int i=gap;i<arr.length;i++){
                int j = i;
                int temp = arr[j];
                if(arr[j]<arr[j-gap]){
                    while(j-gap>=0 && temp<arr[j-gap]){
                        //移动法
                        arr[j] = arr[j-gap];
                        j-=gap;
                    }
                    arr[j] = temp;
                }
            }
        }
    }
    /**
     * 交换数组元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a,int b){
        arr[a] = arr[a]+arr[b];
        arr[b] = arr[a]-arr[b];
        arr[a] = arr[a]-arr[b];
    }
}

4.4 算法分析

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。

5、归并排序（Merge Sort）

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

5.1 算法描述

• 把长度为$n$的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

5.2 动图演示

5.3代码实现

package sort_algorithm;

import java.util.Arrays;

public class merge_sort {

    public static int[] merge_Sort(int[] sourceArray)  {
        // 对arr进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray,sourceArray.length);
        if(arr.length < 2) return arr;

        int middle= (int) Math.floor(arr.length/2);
        int[] left = Arrays.copyOfRange(arr,0,middle);//左子序列
        int[] right= Arrays.copyOfRange(arr,middle,arr.length);//右子序列

        return merge(merge_Sort(left),merge_Sort(right));
    }

    public static int[] merge(int[] left,int[] right) {
        int result[]=new int[left.length+right.length];
        int i = 0;
        while(left.length>0 && right.length>0) {
            if(left[0]<=right[0]){
                result[i++]=left[0];
                left=Arrays.copyOfRange(left,1,left.length);
            }else{
                result[i++]=right[0];
                right=Arrays.copyOfRange(right,1,right.length);
            }
        }
        while(left.length>0){
            result[i++]=left[0];
            left=Arrays.copyOfRange(left,1,left.length);
        }
        while(right.length>0){
            result[i++]=right[0];
            right=Arrays.copyOfRange(right,1,right.length);
        }
        return result;
    }
    public static void main(String args[]) {
        int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
        int[] ans = merge_Sort(arr);
        for (int i : ans){
            System.out.println(i);
        }
    }
}

5.4 算法分析

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

6、快速排序（Quick Sort）

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

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

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

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

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

6.1 算法描述

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

6.2举例说明

假设我们现在对6 1 2 7 9 3 4 5 10 8这个 10 个数进行排序。首先在这个序列中随便找一个数作为基准数。为了方便，就让第一个数 6 作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在 6 的右边，比基准数小的数放在 6 的左边，类似下面这种排列。

3 1 2 5 4 6 9 7 10 8

在初始状态下，数字 6 在序列的第 1 位。我们的目标是将 6 挪到序列中间的某个位置，假设这个位置是 k。现在就需要寻找这个 k，并且以第 k 位为分界点，左边的数都小于等于 6，右边的数都大于等于 6。想一想，你有办法可以做到这点吗？

方法其实很简单：分别从初始序列6 1 2 7 9 3 4 5 10 8两端开始“探测”。先从右往左找一个小于 6 的数，再从左往右找一个大于 6 的数，然后交换他们。这里可以用两个变量 $i$ 和 $j$，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵 i”和“哨兵 j”。刚开始的时候让哨兵 i 指向序列的最左边（即 i=1），指向数字 6。让哨兵 j 指向序列的最右边（即 j=10），指向数字 8。

首先哨兵 $j$ 开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵 $j$ 先出动，这一点非常重要。哨兵$j$ 一步一步地向左挪动（即 j–），直到找到一个小于 6 的数停下来。接下来哨兵 $i$ 再一步一步向右挪动（即 i++），直到找到一个数大于 6 的数停下来。最后哨兵 $j$ 停在了数字 5 面前，哨兵 $i$ 停在了数字 7 面前。


现在交换哨兵$i$ 和哨兵$j$ 所指向的元素的值。交换之后的序列如下。

6 1 2 5 9 3 4 7 10 8


到此，第一次交换结束。接下来开始哨兵 $j$ 继续向左挪动（再友情提醒，每次必须是哨兵 j 先出发）。他发现了 4（比基准数 6 要小，满足要求）之后停了下来。哨兵 $i$ 也继续向右挪动的，他发现了 9（比基准数 6 要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下。

6 1 2 5 4 3 9 7 10 8

第二次交换结束，“探测”继续。哨兵 $j$ 继续向左挪动，他发现了 3（比基准数 6 要小，满足要求）之后又停了下来。哨兵 $i$ 继续向右移动，糟啦！此时哨兵 $i$ 和哨兵 $j$ 相遇了，哨兵 $i$ 和哨兵 $j$ 都走到 3 面前。说明此时“探测”结束。我们将基准数 6 和 3 进行交换。交换之后的序列如下。

3 1 2 5 4 6 9 7 10 8

到此第一轮“探测”真正结束。此时以基准数 6 为分界点，6 左边的数都小于等于 6，6 右边的数都大于等于 6。回顾一下刚才的过程，其实哨兵 $j$ 的使命就是要找小于基准数的数，而哨兵 $i$ 的使命就是要找大于基准数的数，直到 $i$ 和 $j$ 碰头为止。

OK，解释完毕。现在基准数 6 已经归位，它正好处在序列的第 6 位。此时我们已经将原来的序列，以 6 为分界点拆分成了两个序列，左边的序列是“3 1 2 5 4”，右边的序列是“ 9 7 10 8 ”。接下来还需要分别处理这两个序列。因为 6 左边和右边的序列目前都还是很混乱的。不过不要紧，我们已经掌握了方法，接下来只要模拟刚才的方法分别处理 6 左边和右边的序列即可。现在先来处理 6 左边的序列现吧。

左边的序列是“3 1 2 5 4”。请将这个序列以 3 为基准数进行调整，使得 3 左边的数都小于等于 3，3 右边的数都大于等于 3。好了开始动笔吧。

如果你模拟的没有错，调整完毕之后的序列的顺序应该是。

2 1 3 5 4

OK，现在 3 已经归位。接下来需要处理 3 左边的序列“ 2 1 ”和右边的序列“5 4”。对序列“ 2 1 ”以 2 为基准数进行调整，处理完毕之后的序列为“1 2”，到此 2 已经归位。序列“1”只有一个数，也不需要进行任何处理。至此我们对序列“ 2 1 ”已全部处理完毕，得到序列是“1 2”。序列“5 4”的处理也仿照此方法，最后得到的序列如下。

1 2 3 4 5 6 9 7 10 8

对于序列“9 7 10 8”也模拟刚才的过程，直到不可拆分出新的子序列为止。最终将会得到这样的序列，如下。

1 2 3 4 5 6 7 8 9 10

到此，排序完全结束。细心的同学可能已经发现，快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了。

快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是 O(N2)，它的平均时间复杂度为 O(NlogN)。

6.3 代码实现

import java.util.Arrays;

public class QuickSort {
    public static int[] quicksort(int[]arr,int left,int right){
        int i,j,t,temp;
        if(left>right) return arr;
        temp=arr[left];
        i=left;
        j=right;
        while(i != j) {
            while(arr[j]>=temp && i<j){
                j--;
            }
            while(arr[i]<=temp && i<j){
                i++;
            }
            if(i<j){
                t=arr[i];
                arr[i]=arr[j];
                arr[j]=t;
            }
        }
        arr[left]=arr[i];
        arr[i]=temp;
        quicksort(arr,left,i-1);
        quicksort(arr,i+1,right);
        return arr;
    }
    public static void main(String args[]) {
        int[] arr = {6,1,2,7,9,3,4,5,10,8};
        int left=0;
        int right=arr.length-1;
        int[] ans = quicksort(arr,left,right);
        for (int i : ans){
            System.out.println(i);
        }
    }
}

7、堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，是一种选择排序。它的最好，最坏，平均时间复杂度均为O(nlogn),它也是不稳定排序。并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

• 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
• 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
  
  同时，我们对堆中的节点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子。
  
  该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
• 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
• 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

ok，了解这些定义。我们来看看堆排序的基本思想及其基本步骤：

7.1 堆排序基本思想及其步骤

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

1.假设给定无序序列结构如下

2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

3.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

此时，我们就将一个无需序列构造成了一个大顶堆。

步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

a.将堆顶元素9和末尾元素4进行交换

b.重新调整结构，使其继续满足堆定义

c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.
后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

再简单总结下堆排序的基本思路：

• a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

• b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

• c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

7.2 动图演示

7.3 代码实现

import java.util.Arrays;

public class HeapSort {
    public static void sort(int[] arr){
        //1.构建大顶堆
        for(int i =arr.length/2-1;i>=0;i--){
            //从第一个非叶子节点从上到下，从由到左调整结构
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j =arr.length-1;j>0;j--){
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }
    }
    /**
     *调整大顶堆(仅是调整过程，建立在大顶堆已构建的基础上)
     */
    public static void adjustHeap(int[]arr,int i,int length){
        int temp=arr[i];//先取出当前元素
        for(int k=i*2+1;k<length;k=k*2+1){//从i节点的左子树开始，也就是2i+1开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子节点小于右子节点，k指向右子节点
                k++;
            }
            if(arr[k]>temp){//如果子节点大于父节点，将子节点赋值给父节点(不用进行交换)
                arr[i]=arr[k];
                i=k;
            }else{
                break;
            }
        }
        arr[i]=temp;//将temp放到最终的位置
    }

    /**
     * 交换元素
     */
    public static void swap(int[]arr,int a,int b){
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }

    public static void main(String args[]){
        int[] arr ={4,6,8,5,9};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

7.4 总结

堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n),在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，近似为nlogn，所以堆排序时间复杂度一般认为就是O(nlogn)级。

8、计数排序（Counting Sort）

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

计数排序的特征

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

通俗地理解，例如有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1 的原因。

8.1 算法描述

• 找出待排序的数组中最大和最小的元素；
• 统计数组中每个值为$i$的元素出现的次数，存入数组C的第$i$项；
• 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
• 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

8.2 动图演示

8.3代码实现

import java.util.Arrays;

public class countingsort {

    public static int[] sort(int[] sourceArray) {
        //对arr进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        int maxValue = getMaxValue(arr);//求出数组中的最大值
        return countingSort(arr, maxValue);
    }

    private static int[] countingSort(int[] arr, int maxValue) {
        int bucketLen = maxValue + 1;
        int[] bucket = new int[bucketLen];
        for (int value : arr) {
            bucket[value]++;
        }
        int sortedIndex = 0;
        for (int j = 0; j < bucketLen; j++) {
            while (bucket[j] > 0) {
                arr[sortedIndex++] = j;
                bucket[j]--;
            }
        }
        return arr;
    }

    private static int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    public static void main(String args[]) {
        int[] arr = {2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 5, 9, 2};
        int[] ans = sort(arr);
        for (int i : ans) {
            System.out.println(i);
        }
    }
}

8.4 算法分析

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

9、桶排序（Bucket Sort）

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

• 设置固定空桶数
• 将数据放到对应的空桶中
• 将每个不为空的桶进行排序
• 拼接不为空的桶中的数据，得到结果

9.1示意图

元素分布在桶中：

然后，元素在每个桶中排序：

9.2 步骤演示

假设一组数据（长度为20）为

[63,157,189,51,101,47,141,121,157,156,194,117,98,139,67,133,181,13,28,109]

现在需要按5个分桶，进行桶排序，实现步骤如下:

• 找到数组中的最大值194和最小值13，然后根据桶数为5，计算出每个桶中的数据范围为(194-13+1)/5=36.4

• 遍历原始数据，(以第一个数据63为例)先找到该数据对应的桶序列Math.floor(63 - 13) / 36.4) =1，然后将该数据放入序列为1的桶中(从0开始算)

• 当向同一个序列的桶中第二次插入数据时，判断桶中已存在的数字与新插入的数字的大小，按从左到右，从小打大的顺序插入。如第一个桶已经有了63，再插入51，67后，桶中的排序为(51,63,67) 一般通过链表来存放桶中数据

• 全部数据装桶完毕后，按序列，从小到大合并所有非空的桶(如0,1,2,3,4桶)

• 合并完之后就是已经排完序的数据

步骤图示

9.3代码实现

import java.util.ArrayList;
import java.util.Iterator;

public class Bucksort   {
    public static double[] bucketsort(double[] arr,int bucketCount) {
        int len = arr.length;
        double[]result=new double[len];
        double min=arr[0];
        double max=arr[0];
        //找到最大值和最小值
        for(int i =1;i<len;i++){
            min=min<=arr[i]?min:arr[i];
            max=max>=arr[i]?max:arr[i];
        }
        //求出每一个桶的数值范围
        double spcae=(max-min+1)/bucketCount;
        //先创建好每一个桶的空间，这里使用了泛型数组
        ArrayList<Double>[]arrList=new ArrayList[bucketCount];
        //把arr中的数均匀的分布到【0,1）上，每个桶是一个list，存放落在此桶上的元素
        for(int i =0;i<len;i++){
            int index=(int)Math.floor((arr[i]-min)/spcae);
            if(arrList[index]==null){
                //如果链表中没有数据
                arrList[index]=new ArrayList<Double>();
                arrList[index].add(arr[i]);
            }else{
                //排序
                int k = arrList[index].size()-1;
                while(k>=0 && (Double) arrList[index].get(k)>arr[i]){
                    if(k+1>arrList[index].size()-1){
                        arrList[index].add(arrList[index].get(k));
                    }else{
                        arrList[index].set(k+1,arrList[index].get(k));
                    }
                    k--;
                }
                if(k+1>arrList[index].size()-1){
                    arrList[index].add(arr[i]);
                }else{
                    arrList[index].set(k+1,arr[i]);
                }
            }
        }
        //把各个桶的排序结果合并，count是当前的数组下标
        int count = 0;
        for(int i =0;i<bucketCount;i++){
            if(null!=arrList[i] && arrList[i].size()>0){
                Iterator<Double>iter=arrList[i].iterator();
                while(iter.hasNext()){
                    Double d = (Double) iter.next();
                    result[count]=d;
                    count++;
                }
            }
        }
        return result;
    }
    public static void main(String args[]) {
        double[] arr = {63,157,189,51,101,47,141,121,157,156,194,117,98,139,67,133,181,13,28,109};
        double[] ans = bucketsort(arr,5);
        for (double i : ans) {
            System.out.println(i);
        }
    }
}

10.1 基数排序

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

1. 基数排序 vs 计数排序 vs 桶排序

基数排序有两种方法：

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

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

2. LSD 基数排序动图演示

10.3代码实现

**
 * 基数排序
 * 考虑负数的情况还可以参考： 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;
    }

    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;
    }
}

参考文献

• https://www.cnblogs.com/chengxiao/p/6104371.html
• https://www.runoob.com/w3cnote/quick-sort-2.html
• https://wiki.jikexueyuan.com/project/easy-learn-algorithm/fast-sort.html
• https://www.cnblogs.com/chengxiao/p/6129630.html
• https://dailc.github.io/2016/12/03/baseKnowlenge_algorithm_sort_bucketSort.html
• https://www.runoob.com/w3cnote/radix-sort.html