数据结构与算法(六）

冒泡排序

冒泡排序（Bubble Sorting）的基本思想：通过对待排序序列 从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的旗袍一样逐渐向上冒。

优化点：因为排序过程中，个元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志判断元素是否进行过交换。从而减少不必要的比较。（该优化点可以在完成基本的冒泡排序之后再做）

冒泡排序图解

复制代码

原始数组：3，9，-1，10，20

第一趟排序：// 如果相邻的元素逆序就交换
1：3，9，-1，10，20	// 比较 3 和 9，不用交换
2：3，9，-1，10，20	// 比较 9 和 -1，交换位置
3：3，-1，9，10，20	// 比较 9 和 10，不用交换
4：3，-1，9，10，20	// 比较 10 和 20，不用交换；而且确定了最大值 20

第二趟排序：// 因为 20 是最大值，其实只需要比较前面 4 个就行了
1：-1，3，9，10，20	// 比较 3 和 -1，进行交换
2：-1，3，9，10，20  // 比较 3 和 9，不用交换
3：-1，3，9，10，20	// 比较 9 和 10，不用交换；确定了本轮最大值 10

第三趟排序：// 因为 10 是上一轮最大值，只需要比较前 3 个
1：-1，3，9，10，20	// 比较 -1 和 3，不用交换
2：-1，3，9，10，20	// 比较 3 和 9 ，不用交换；确定了本轮最大值 9

第四趟排序：// 上一轮最大值为 9，只需要比较前 2 个
1：-1，3，9，10，20	// 比较 -1 和 3，不需要交换，bending本轮最大值 3

比较结束

冒泡排序小结：

1. 共进行数组大小 -1 次大的循环

2. 每一趟排序的次数在逐渐的减少

3. 如果发现在某趟排序中，没有发生一次交换，则可以提前结束冒泡排序。

   如上图那样，在第二趟的就确定了顺序，在第三趟的时候走完，都没有交换过顺序，就可以提前结束了

代码实现

复制代码

//冒泡排序
int[] arr = {10,3,-2,-1,5,9,4};//要进行排序的数据
int temp = 0;//用于进行交换
for (int i = 0; i < arr.length - 1; i++) {//每走一次外部循环就确定一个数的位置
    boolean flag = true;
    for(int j = 0; j < arr.length -1 - i; j++){//确定一个数的位置，要比较的次数跟元素的位置有关
        if(arr[j] > arr[j+1]){
            flag = false;
            temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
        }
    }
    if(flag){
        break;//排序完成
    }
    System.out.printf("第%d次循环:" + Arrays.toString(arr) + "\n",i+1);

}
System.out.println("结果: " + Arrays.toString(arr));

封装

复制代码

/**
  * 封装冒泡排序算法
  * @param arr 要进行排序的数组
  */
public static void bubbleSort(int[] arr){
    int temp = 0;//用于进行交换
    boolean flag = true;
    for (int i = 0; i < arr.length - 1; i++) {//每走一次外部循环就确定一个数的位置
        for (int j = 0; j < arr.length - 1 - i; j++) {//确定一个数的位置，要比较的次数跟元素的位置有关
            if (arr[j] > arr[j + 1]) {
                flag = false;
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        if (flag) {
            break;//排序完成
        } else {
            flag = true;//重置标志位
        }
    }
}

算法性能测试

随机生成八万条数据进行冒泡算法排序测试

复制代码

//冒泡算法性能测试
int[] arr = new int[80000];
for(int i = 0; i < arr.length; i++){
    arr[i] = (int)(Math.random()*8000000);
}
long time1 =System.currentTimeMillis();
bubbleSort(arr);
long time2 = System.currentTimeMillis();
System.out.println("共耗时："+(time2-time1) + "毫秒");

运行几次都差不多在10秒左右。

选择排序

选择排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出来某个元素，再依规定交换位置后达到排序的目的。

基本思想

选择排序（select sorting）也是一种简单的排序方法。

基本思想为：

• 第一次从 arr[0]~arr[n-1] 中选取最小值，与 arr[0] 交换
• 第二次从 arr[1]~arr[n-1] 中选取最小值，与 arr[1] 交换
• 第 i 次从 arr[i-1]~arr[n-1] 中选取最小值，与 arr[i-1] 交换
• 依次类图，总共通过 n - 1 次，得到一个按排序码从小到大排列的有序序列

思路分析

如上图，每一次找到一个最小值，然后与那一次所在的下标处交换位置。

下面使用：101,34,119,1 这个简单的序列来图解，便于容易理解

说明：

1. 选择排序一共有数组大小 - 1 轮排序
2. 每 1 轮排序，又是一个循环，循环的规则
   1. 先假定当前这个数是最小数
   2. 然后和后面每个数进行比较，如果发现有比当前数更小的数，则重新确定最小数，并得到下标
   3. 当遍历到数组的最后时，就得到本轮最小的数
   4. 交换

代码实现

复制代码

/**
  * 选择排序
  * @param arr 要排序的数组
  */
public static void sort(int[] arr){
    for(int i = 0; i < arr.length-1; i++){
        int min = arr[i];//假定这轮的最小值
        int minIndex = i;//假定这轮的最小值索引
        for(int j = i + 1; j < arr.length; j++){
            if(min > arr[j]){
                //重置最小值和索引位置
                min = arr[j];
                minIndex = j;
            }
        }
        //经过一轮循环之后确定一个最小值的位置
        if(minIndex != i){
            //最小值位置发生变化就交换
            arr[minIndex] = arr[i];
            arr[i] = min;
        }
    }
}

算法性能测试

随机生成八万条数据进行排序

复制代码

int[] arr = new int[80000];
for(int i = 0; i < arr.length; i++){
    arr[i] = (int)(Math.random()*8000000);
}
long time1 =System.currentTimeMillis();
sort(arr);
long time2 = System.currentTimeMillis();
System.out.println("共耗时："+(time2-time1) + "毫秒");

在我的电脑上面多次测试运行，时间一直在2秒左右

插入排序

插入排序属于内部排序法，是对于欲排序的元素以 插入的方式寻找该元素的适当位置，以达到排序的目的。

该 插入排序又被称为 直接插入排序 或 简单插入排序。

基本思想

插入排序（Insertion Sorting）的基本思想是：

1. 把 n 个待排序的元素 看成 为一个 有序表 和 无序表
2. 开始时，有序表中只包含一个元素，无序表中包含有 n - 1 个 元素

排序过程中每次 从无序表中取出第一个元素，把它的排序码 依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

思路分析

如上图，初始有 5 个元素序列。

• 第一个元素作为初始的有序表，剩下的其他作为无序表
• 当第一次比较时：无序表中的第一个元素取出来与有序表倒数第一个元素比较（从小到大），发现 3 小于 17，于是插入到有序表中适当的位置

以此类推，直到比较完成。

代码实现

复制代码

/**
  *
  * @param arr 要进行排序的数组
  */
public static void insertSort(int[] arr){
    for(int i = 1; i < arr.length; i++){
        int insertValue = arr[i];//待插入元素的值
        //要开始进行插入比较的第一个索引位置，将待插入的元素和其前面的所有元素进行比较，找到一个合适的位置
        int insertIndex = i - 1;
        //寻找插入位置
        while(insertIndex >= 0 && insertValue < arr[insertIndex]){
            //将前一个元素位置后移
            arr[insertIndex+1] = arr[insertIndex];
            insertIndex--;//继续和前面元素比较
        }
        //找到位置
        if(insertIndex + 1 != i){
            arr[insertIndex+1] = insertValue;
        }
    }
}

算法性能测试

对8万条数据进行排序

复制代码

//性能测试
int[] arr = new int[80000];
for(int i = 0; i < arr.length; i++){
    arr[i] = (int)(Math.random()*8000000);
}
long time1 =System.currentTimeMillis();
insertSort(arr);
long time2 = System.currentTimeMillis();
System.out.println("共耗时："+(time2-time1) + "毫秒");

在我的电脑上面多次测试运行，时间一直在0.5秒左右

希尔排序

简单插入排序存在的问题

简单的插入排序可能存在的问题。

如数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1（最小），过程是：

复制代码

展示的是要移动 1 这个数，的过程，由于在最后，需要前面的所有数都往后移动一位
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}

结论：当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响。

希尔排序是希尔（Donald Shell）于 1959 年提出的一种排序算法。

希尔排序也是一种 插入排序，它是简单插入排序经过改进后的一个 更高效的版本，也称为 缩小增量排序。

基本思想

希尔排序把记录按 下标的一定增量分组，对每组使用 直接插入排序算法 排序，随着 增量逐渐减少，每组包含的关键词越来越多（要排序的数），当增量减至 1 时，整个文件被分成一组，算法执行完成便终止。

光看上面的描述，对于首次接触的人来说，不知道是啥意思，认真思考下面的说明：

• 原始数组：以下数据元素颜色相同为一组
  

• 初始增量为：gap = length/2 这里为 gap = 10 / 2 = 5

  那么意味着整个数组被分为 5 组。分别为 [8,3][9,5][1,4][7,6][2,0]

  先看明白这里的增量为 5 ，就会分成 5 组。[8,3] 这一组来说，对比看下图，它的意思是：从 8 开始，下标增加 5 既对应的数是 3，所以他们分为一组
  

• 对上面的这 5 组分别进行 直接插入排序

  结果如下图：可以看到，像 3、5、6 这些小元素被调整到了前面。
  

然后缩小增量 gap = 5 / 2 = 2，则数组被分为 2 组 [3,1,0,9,7] 和 5,6,8,4,2

• 对以上 2 组再分别进行直接插入排序

  结果如下图：可以看到，此时整个组数的有序程度更进一步。
  

然后再缩小增量 gap = 2 / 2 = 1，则整个数组被当成一组，再进行一次直接插入排序。由于基本上是有序的了，所以少了很多次的调整

代码实现

对于希尔排序时，对有序序列在 插入 时，有以下两种方式：

• 交换法：容易理解，速度相对较慢
• 移动法：不太容易理解，速度相对较快

先实现交换法，然后再优化成移动法。比较容易

特别注意

1. 希尔排序，是一种插入排序，前面讲解的插入排序算法使用了 移动法（这里先讲解交换法）
2. 希尔排序，对插入排序的改进，先分组，这里分组是通过增量步长和相关算法，来达到在循环中直接获取到这一个组的元素
3. 直接排序的基本思想一定要记得，最重要的两个变量：无序列表中的第一个值，与有序列表中的最后一个值开始比较

复制代码

//交换法
public static void shellSort(int[] arr){
    int temp = 0;//进行交换的时候中间变量
    for(int gap = arr.length/2 ; gap >= 1; gap /= 2){//控制每次分组的增量，每次对数组分成几个组
        for(int i = gap; i < arr.length; i++){
            //遍历每个分组的每个元素，进行比较，找到合适的位置
            temp = arr[i];
            for(int j = i - gap; j >= 0; j -= gap){//这里类似插入排序，跟每个分组前面的有序元素进行比较，找到合适的位置
                if(arr[j] > temp){//进行比较交换
                    arr[j+gap] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
}

使用交换法进行希尔排序的时候，在我的电脑上面运行需要5秒左右，运行的时间比插入排序还要慢

复制代码

//移动法
public static void shellSort2(int[] arr){
    for(int gap = arr.length/2; gap >= 1; gap /= 2){//控制分组个数
        for(int i = gap; i < arr.length; i++){//遍历每个分组的所有元素进行插入排序
            int temp = arr[i];
            int j = i - gap;
            if(temp < arr[j]){
                while(j >= 0 && temp < arr[j]){
                    arr[j+gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = temp;
            }
        }
    }
}

当使用移位发实现希尔排序进行性能测试，发现效率提升非常大，在我的电脑运行测试只需要大概16毫秒，测试数据是对8万条数据进行排序。

快速排序

Quicksort 快速排序 是对 冒泡排序的一种改进。

基本思想

通过一趟排序将要排序的数据 分割成独立的两个部分，一部分的所有数据都比另外一部分的所有数据都要小。

然后再按如上的方法对这两部分数据分别进行快速排序，排序过程可以递归进行，以此达到整个数据变成有序序列。

比如如下的示意图：

• 上图以 最后一个元素的值 作为基准
• 比基准值小的，排在左侧，比基准值大的排在右侧
• 然后再以分好的部分重复以上操作，直到每个部分中只有一个数据时，就排好序了

思路分析

基本思想如上，但是实现思路有多种，这里不以上图那样用数组元素最后一个为基准值，这里使用 数组中间 的作为基准值，进行讲解

如下图

1. 挑选的基准值为数组中间的值
2. 中间值就把数组分成了两组
3. 左边一组，从左到右，挨个与 基准值 比较，找出比基准值大的值
4. 右边一组，从右到左，挨个与 基准值 比较，找出比基准值小的值
5. 左右两边各找到一个值，那么就让这两个值进行交换
6. 然后继续找，直到左右两边碰到，这一轮就结束。这一轮就称为快速排序
7. 继续对分出来的小组，进行上述的快速排序操作，直到组内只剩下一个数时，则排序完成

代码实现

复制代码

/**
  *
  * @param arr 要排序的数组
  * @param left 左索引
  * @param right 右索引
  */
public static void quickSort(int[] arr,int left,int right){
    int l = left;
    int r = right;
    int pivot = arr[(left + right)/2];//中间值
    int temp = 0;
    while(l < r){
        //在pivot左边找到一个比pivot大的值
        while(arr[l] < pivot){
            l += 1;//否则右移继续找，找到一个符合条件的数就退出
        }
        //在pivot右边找一个比pivot小值
        while(arr[r] > pivot){
            r -= 1;//左移继续找
        }
        //在左右都找到了一个符合条件的值
        if(l >= r){
            break;//说明数组的左边都已经是比pivot小的值，pivot右边都是比pivot大的值
        }

        //交换位置
        temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
        // 当交换后，
        // 当数组是： {-9, 78, 0, -23, 0, 70}  时，就可以验证这里的逻辑
        // 如果没有这个判定，将会导致，l 永远 小于 r。循环不能退出来的情况
        if(arr[l] == pivot){
        //不能让自己往前移动 1，因为当交换完成后为：{-9, 0, 0, -23, 78, 70}
        // l = 1, = 0
        // r = 4, = 78
        // 如果 l 等于 2，那么相当于下一轮，基准值 - 将会与 -23 进行交换，导致基准值变化了
        // 所以，让 r - 1，还有一个原因是，r 是刚刚交换过的，一定比 基准值大，所以没有必要再和基准值比较了
            r -= 1;
        }
        if(arr[r] == pivot){
            l += 1;
        }
    }
    // 如果 l = r，会出现死循环
    if(l == r){
        l += 1;
        r -= 1;
    }
    if(r > left){//对左边元素进行递归排序
        quickSort(arr,left,r);
    }
    if(l < right){//对右边元素进行递归排序
        quickSort(arr,l,right);
    }
}

性能测试

当数据量为800万的时候使用快排，时间比较稳定在1秒左右，当数据量越大的时候比希尔排序要更快。

归并排序

归并排序（merge sort）是利用 归并 的思想实现的排序方法，该算法采用经典的 分治（divide-and-conquer）策略 ：

• 分（divide）：将问题分成一些小的问题，然后递归求解
• 治（conquer）：将分的阶段得到的各答案「修补」在一起

即：分而治之

基本思想

• 分：的过程只是为了分解
• 治：分组完成后，开始对每组进行排序，然后合并成一个有序序列，直到最后将所有分组合并成一个有序序列

可以看到这种结构很像一颗 完全二叉树，本文的归并排序我们采 用递归实现（也可采用迭代的方式实现）。分阶段 可以理解为就是递归拆分子序列的过程。

思路分析

对于分阶段相对较简单，下面着重来对治阶段进行分析。

合并相邻有序子序列分析：下图以 归并排序的最后一次合并 为例来分析，即对应上图的 [4,5,7,8] 和 [1,2,3,6] 两个已经有序的子序列合并为最终序列 [1,2,3,4,5,6,7,8]，下图展示了实现步骤

如图所示：这是最后一次的合并 操作，是两个有序序列。

1. 从有序序列开始挨个比较，这里比较 4 和 1，1 < 4，那么 1 进入临时数组中，并且将自己的指针右移动一位
2. 由于上一次 4 大于 1，指针并未移动，然后 4 和 2 对比，2 < 4 , 2 进入到临时数组中，并且将自己的指针右移动一位
3. ...
4. 如果某一组已经全部进入了临时数组，那么剩余一组的剩余有序序列直接追加到临时数组中
5. 最后，将 temp 内容拷贝到原数组中去，完成排序

代码实现

复制代码

/**
  * 对源数组进行分割，分治中分的部分
  * @param arr 原数组
  * @param left 开始分的起始索引
  * @param right 开始分的结束索引，包含这个位置
  * @param temp 辅助数组
  */
public static void mergeSort(int[] arr,int left,int right,int[] temp){
    int middle = (left + right) / 2;//中间索引位置
    if(left < right){
        //递归分解
        //先对左边部分进行分解
        mergeSort(arr,left,middle,temp);
        //再对右边部分进行分解
        mergeSort(arr,middle+1,right,temp);
        //合并两个有序队列
        merge(arr,left,right,temp);
    }
}

/**
  * 归并排序中合的部分
  * @param arr 要进行合并的原数组
  * @param left 开始合并的起始位置
  * @param right 开始合并的结束位置，包含该位置
  * @param temp 辅助合并的数组
  */
public static void merge(int[] arr,int left,int right,int[] temp){
    int i = left;//左边数组开始的索引位置
    int middle = (left + right) / 2;//中间索引位置，是左边索引的最后一个包含元素
    int j = middle + 1;//右边数组开始的索引位置
    int t = 0;//辅助索引，遍历辅助数组
    //1.将两个有序数组中的所有元素添加到辅助数组中
    while(i <= middle && j <= right){
        if(arr[i] < arr[j]){
            //左边数组中的元素较小先添加到辅助数组中
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }else{
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }
    }
    //跳出上面循环的原因是有一个数组元素添加完，另一个数组还有元素没有添加完，继续添加
    while(i <= middle){
        temp[t] = arr[i];
        t += 1;
        i += 1;
    }

    while(j <= right){
        temp[t] = arr[j];
        t += 1;
        j += 1;
    }
    //数据添加完成，这时在temp数组中已经形成一个有序队列，再将这个队列赋值到源数组中
    t = 0;//索引重置为0
    while(left <= right){
        arr[left] = temp[t];
        t += 1;
        left += 1;
    }
}

性能测试

当对8万条数据进行排序测试，综合时间在17毫秒左右

对80万数据进行测试，综合时间在110毫秒左右

基数排序

基数排序（radix sort）属于 分配式排序（distribution sort），又称 桶子法（bucket sort 或 bin sort），顾名思义，它是通过键值的各个位的值，将要排序的 元素分配 至某些「桶」中，达到排序的作用。

基数排序属于 稳定性 的排序，基数排序法是效率高的稳定性排序法。

稳定性简介

2,1,43,1 数组进行排序后变成：1,1,2,43

稳定性指的是：两个 1 的先后顺序不改变。

基数排序（Radix Sort）是 桶排序 的扩展。

基数排序是 1887 年赫尔曼·何乐礼发明的。实现方式：将整数按位数切割成不同的数字，然后按每个位数分别比较。

基本思想

1. 将所有待比较数值 统一为同样的数位长度，数位较短的数 前面补零
2. 然后从最低位开始，依次进行一次排序
3. 这样从最低位排序一直到最高位排序完成以后，序列就变成了一个有序序列

基本思想是抽象的，下面看看思路分析，你就明白是咋回事了。

思路分析

第一轮：比较 个位数

1. 将每个元素的 个位数 取出，然后放到对应的桶中（桶为一个一维数组）
2. 按照这个桶的顺序，依次取出数据，放回原来的数组

以上步骤中，每一轮除了比较的位数不同外，其他的都相同。

第二轮：比较 十位数。

需要注意的是：

• 第一轮使用后的桶并未清理，下图为了讲解方便，并未展示桶中已有的数据，不过会进行覆盖。
• 长度不足的数，用零表示。如 3，没有十位数，则归类到第一个桶中（0）。
  

第三轮：比较 百位数

对于最大值为 3 位数的数组中排序，你会发现，在第三轮排序后，数组已经是有序的了

代码实现

复制代码

//基数排序
public static void radixSort(int[] arr){
    //取得当前数组中最大数的位数
    int max = arr[0];
    for(int i = 1; i < arr.length; i++){
        if(arr[i] > max){
            max = arr[i];
        }
    }
    int maxLength = (max+"").length();
    //进行排序前的准备
    //定义桶子数组,每个桶子最坏保存所有的数据
    int[][] bucket = new int[10][arr.length];
    int[] bucketElementCounts = new int[10];//记录每个桶子实际存放元素的个数
    for(int i = 0; i < maxLength; i++){//进行循环读取每个数中每一位的数据
        //进行第i轮的排序
        for(int j = 0; j < arr.length;j++){
            //得到每轮的位数
            //得到个数 arr[j] / 1 % 10
            //得到十位 arr[j] / 10 % 10
            //得到百位 arr[j] / 100 % 10依次类推
            int digitOfElement = arr[j]/(int)(Math.pow(10,i)) % 10;
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            //记录对应桶子的数要加+
            bucketElementCounts[digitOfElement]++;
        }
        //从桶中取出数据，放到原数组中
        int index = 0;//记录原数组的索引
        for(int l = 0; l < bucketElementCounts.length;l++){
            //每次读取每个桶中的所有数据
            if(bucketElementCounts[l] != 0){
                for(int j = 0; j < bucketElementCounts[l]; j++){
                    arr[index] = bucket[l][j];
                    index++;//原数组指针后移
                }
            }
            //记录每个桶子中的元素个数重置
            bucketElementCounts[l] = 0;
        }
    }
}

性能测试

当对8万条数据进行排序测试，综合时间稳定在50毫秒左右

当对80万条数据进行排序测试，综合时间稳定在350毫秒左右

注意事项

• 基数排序是对 传统桶排序 的扩展，速度很快

• 是经典的空间换时间的方式，占用内存空间很大

  当数据量太大的时候，所耗费的额外空间较大。是原始数据的 10 倍空间

• 基数排序是稳定的

  相同的数，排序之后，他们的先后顺序没有发生变化。

• 有负数时，不用基数排序来进行排序

  如果要支持负数可以参考 中文维基百科(opens new window)

  由于上述算法使用的按位比较，并未考虑负数，直接使用，将导致数组越界。

  改造支持负数的核心思想是：将负数取绝对值，然后再反转成负数。

常用排序算法总结对比

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	排序方式	稳定性
冒泡排序	O(n2)	O(n)	O(n2)	O(1)	In-place	稳定
选择排序	O(n2)	O(n2)	O(n2)	O(1)	In-place	不稳定
插入排序	O(n2)	O(n)	O(n2)	O(1)	In-place	稳定
希尔排序	O(n log n)	O(n log2 n)	O(n log2 n)	O(1)	In-place	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	Out-place	稳定
快速排序	O(n log n)	O(n log n)	O(n2)	O(log n)	In-place	不稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	In-place	不稳定
计数排序	O(n + k)	O(n + k)	O(n + k)	O(k)	Out-place	稳定
桶排序	O(n + k)	O(n + k)	O(n2)	O(n + k)	Out-place	稳定
基数排序	O(n x k)	O(n x k)	O(n x k)	O(n + k)	Out-place	稳定

相关术语解释：

• 稳定：如果 a 原本在 b 前面，而 a=b，排序之后，a 仍然在 b 的前面
• 不稳定：不满足稳定定义
• 内排序（In-place）：所有排序操作都在内存中完成
• 外排序（Out-place）：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
• 时间复杂度：一个算法执行所耗费的时间
• 空间复杂度：运行完一个程序所需内存的大小
• n：数据规模
• k：「桶」的个数
• In-place：不占用额外内存
• Out-place：占用额外内存

以上排序中的「堆排序」与二叉树有关，后续学完二叉树再讲解，「计数排序」与桶排序、基数排序类似，不讲解。