vlambda博客
学习文章列表

0. 前言

大家好，我是多选参数的程序锅，一个正在 neng 操作系统、学数据结构和算法以及 Java 的硬核菜鸡。数据结构和算法是我准备新开的坑，主要是因为自己在这块确实很弱，需要大补（残废了一般）。这个坑以排序为开端，介绍了 7 种最经典、最常用的排序算法，分别是：冒泡排序、插入排序、选择排序、归并排序、快速排序、桶排序、计数排序、基数排序。对应的时间复杂度如下所示：

整篇文章的主要知识提纲如图所示：

1. 排序算法分析

学习排序算法除了学习它的算法原理、代码实现之外，最重要的是学会如何评价、分析一个排序算法。分析一个排序算法通常从以下几点出发。

1.1. 执行效率

而对执行效率的分析，一般从这几个方面来衡量：

• 最好情况、最坏情况、平均情况

  除了需要给出这三种情况下的时间复杂度还要给出对应的要排序的原始数据是怎么样的。

• 时间复杂度的系数、常数、低阶

  大 O 时间复杂度反应的是算法时间随 n 的一个增长趋势，比如 O(n^2) 表示算法时间随 n 的增加，呈现的是平方的增长趋势。这种情况下往往会忽略掉系数、常数、低阶等。但是实际开发过程中，排序的数据往往是 10 个、100 个、1000 个这样规模很小的数据，所以在比较同阶复杂度的排序算法时，这些系数、常数、低阶不能省略。

• 比较次数和交换（或移动）次数

  在基于比较的算法中，会涉及到元素比较和元素交换等操作。所以分析的时候，还需要对比较次数和交换次数进行分析。

1.2. 内存消耗

内存消耗其实就是空间复杂度。针对排序算法来说，如果该排序算法的空间复杂度为 O(1)，那么这个排序算法又称为原地排序。

1.3. 稳定性

是什么

稳定性是指待排序的序列中存在值相等的元素。在排序之后，相等元素的前后顺序跟排序之前的是一样的。

为什么

我们将排序的原理和实现排序时用的大部分都是整数，但是实际开发过程中要排序的往往是一组对象，而我们只是按照对象中的某个 key 来进行排序。

比如一个对象有两个属性，下单时间和订单金额。在存入到数据库的时候，这些对象已经按照时间先后的顺序存入了。但是我们现在要以订单金额为主要 key，在订单金额相同的时候，以下单时间为 key。那么在采用稳定的算法之后，只需要按照订单金额进行一次排序即可。比如有这么三个数据，第一个数据是下单时间、第二数据是订单金额：（20200515、20）、（20200516、10）、（20200517、30）、（20200518、20）。在采用稳定的算法之后，排序的情况如下：（20200516、10）、(20200515、20)、（20200518、20）、（20200517、30）可以发现在订单金额相同的情况下是按订单时间进行排序的。

2. 经典的常用排序算法

2.1. 冒泡排序

冒泡排序就是依次对两个相邻的元素进行比较，然后在不满足大小条件的情况下进行元素交换。一趟冒泡排序下来至少会让一个元素排好序（元素排序好的区域相当于有序区，因此冒泡排序中相当于待排序数组分成了两个已排序区间和未排序区间）。因此为了将 n 个元素排好序，需要 n-1 趟冒泡排序（第 n 趟的时候就不需要）。

下面用冒泡排序对这么一组数据4、5、6、3、2、1，从小到大进行排序。第一次排序情况如下：

可以看出，经过一次冒泡操作之后，6 这个元素已经存储在正确的位置上了，要想完成有所有数据的排序，我们其实只需要 5 次这样的冒泡排序就行了。图中给出的是带第 6 次了的，但是第 6 次其实没必要。

2.1.1. 优化

使用冒泡排序的过程中，如果有一趟冒泡过程中元素之间没有发生交换，那么就说明已经排序好了，可以直接退出不再继续执行后续的冒泡操作了。

2.1.2. 实现

下面的冒泡排序实现是优化之后的：

/**
 * 冒泡排序：
 * 以升序为例，就是比较相邻两个数，如果逆序就交换，类似于冒泡；
 * 一次冒泡确定一个数的位置，因为要确定 n-1 个数，因此需要 n-1
 * 次冒泡；
 * 冒泡排序时，其实相当于把整个待排序序列分为未排序区和已排序区
 */
public void bubbleSort(int[] arr, int len) {
    // len-1 趟
    for (int j = 0; j < len-1; j++) {
        int sortedFlag = 0;
        // 一趟冒泡
        for (int i = 0; i < len-1-j; i++) {
            if (arr[i] > arr[i+1]) {
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
                sortedFlag = 1;
            }
        }

        // 该趟排序中没有发生，表示已经有序
        if (0 == sortedFlag) {
            break;
        }
    }
}

2.1.3. 算法分析

• 冒泡排序是原地排序。因为冒泡过程中只涉及到相邻数据的交换，相当于只需要开辟一个内存空间用来完成相邻的数据交换即可。

• 在元素大小相等的时候，不进行交换，那么冒泡排序就是稳定的排序算法。

• 冒泡排序的时间复杂度。

• 当元素已经是排序好了的，那么最好情况的时间复杂度是 O(n)。因为只需要跑一趟，然后发现已经排好序了，那么就可以退出了。

• 当元素正好是倒序排列的，那么需要进行 n-1 趟排序，最坏情况复杂度为 O(n^2)。

• 一般情况下，平均时间复杂度是 O(n^2)。使用有序度和逆序度的方法来求时间复杂度，冒泡排序过程中主要是两个操作：比较和交换。每交换一次，有序度就增加一，因此有序度增加的次数就是交换的次数。又因为有序度需要增加的次数等于逆序度，所以交换的次数其实就等于逆序度。

  因此当要对包含 n 个数据的数组进行冒泡排序时。最坏情况下，有序度为 0 ，那么需要进行 n*(n-1)/2 次交换；最好情况下，不需要进行交换。我们取中间值 n*(n-1)/4，来表示初始有序度不是很高也不是很低的平均情况。由于平均情况下需要进行 n*(n-1)/4 次交换，比较操作肯定比交换操作要多。但是时间复杂度的上限是 O(n^2)，所以平均情况下的时间复杂度就是 O(n^2)。

  ★

  这种方法虽然不严格，但是很实用。主要是因为概率的定量分析太复杂，不实用。（PS：我就喜欢这种的）

  ”

2.2. 插入排序

**插入排序中将数组中的元素分成两个区间：已排序区间和未排序区间（最开始的时候已排序区间的元素只有数组的第一个元素），插入排序就是将未排序区间的元素依次插入到已排序区间（需要保持已排序区间的有序）。最终整个数组都是已排序区间，即排序好了。**假设要对 n 个元素进行排序，那么未排序区间的元素个数为 n-1，因此需要 n-1 次插入。插入位置的查找可以从尾到头遍历已排序区间也可以从头到尾遍历已排序区间。

如图所示，假设要对 4、5、6、1、3、2进行排序。左侧橙红色表示的是已排序区间，右侧黄色的表示未排序区间。整个插入排序过程如下所示

2.2.1. 优化

• 采用希尔排序的方式。
• **使用哨兵机制。**比如要排序的数组是[2、1、3、4]，为了使用哨兵机制，首先需要将数组的第 0 位空出来，然后数组元素全都往后移动一格，变成[0、2、1、3、4]。 那么数组 0 的位置用来存放要插入的数据，这样一来，判断条件就少了一个，不用再判断 j >= 0 这个条件了， 只需要使用 arr[j] > arr[0] 的条件就可以了。因为就算遍历到下标为 0 的位置，由于 0 处这个值跟要插入的值是一样的，所以会退出循环，不会出现越界的问题。

2.2.2. 实现

这边查找插入位置的方式采用从尾到头遍历已排序区间，也没有使用哨兵。

/**
 * 插入排序：
 * 插入排序也相当于把待排序序列分成已排序区和未排序区；
 * 每趟排序都将从未排序区选择一个元素插入到已排序合适的位置；
 * 假设第一个元素属于已排序区，那么还需要插入 len-1 趟；
 */
public void insertSort(int[] arr, int len) {
    // len-1 趟
    for (int i = 1; i < len; i++) {
        // 一趟排序
        int temp = arr[i];
        int j;
        for (j = i-1; j >= 0; j--) {
            if (arr[j] > temp) {
                arr[j+1] = arr[j];
            } else {
                break;
            }
        }
        arr[j+1] = temp;
    }
}

2.2.3. 算法分析

• 插入排序是原地算法。因为只需要开辟一个额外的存储空间来临时存储元素。

• 当比较元素时发现元素相等，那么插入到相等元素的后面，此时就是稳定排序。也就是说只有当有序区间中的元素大于要插入的元素时才移到到后面的位置，不大于（小于等于）了的话直接插入。

• 插入排序的时间复杂度。

• 待排序的数据是有序的情况下，不需要搬移任何数据。那么采用从尾到头在已排序区间中查找插入位置的方式，最好时间复杂度是 O(n)。

• 待排序的数据是倒序的情况，需要依次移动 1、2、3、...、n-1 个数据，因此最坏时间复杂度是 O(n^2)。

• 平均时间复杂度是 O(n^2)。因此将一个数据插入到一个有序数组中的平均时间度是 O(n)，那么需要插入 n-1 个数据，因此平均时间复杂度是 O(n^2)

  ★

  最好的情况是在这个数组中的末尾插入元素的话，不需要移动数组，时间复杂度是 O(1)，假如在数组开头插入数据的话，那么所有的数据都需要依次往后移动一位，所以时间复杂度是 O(n)。往数组第 k 个位置插入的话，那么 k~n 这部分的元素都需要往后移动一位。因此此时插入的平均时间复杂度是 O(n)

  ”

2.2.4. VS 冒泡排序

冒泡排序和插入排序的时间复杂度都是 O(n^2)，都是原地稳定排序。而且冒泡排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度。插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度。但是，从代码的实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，而插入排序只需要一个赋值操作。所以，虽然冒泡排序和插入排序在时间复杂度上都是 O(n^2)，但是如果希望把性能做到极致，首选插入排序。其实该点分析的主要出发点就是在同阶复杂度下，需要考虑系数、常数、低阶等。

2.3. 选择排序

选择排序也分为已排序区间和未排序区间（刚开始的已排序区间没有数据），选择排序每趟都会从未排序区间中找到最小的值（从小到大排序的话）放到已排序区间的末尾。

2.3.1. 实现

/**
 * 选择排序：
 * 选择排序将待排序序列分成未排序区和已排序区；
 * 第一趟排序的时候整个待排序序列是未排序区；
 * 每一趟排序其实就是从未排序区选择一个最值，放到已排序区；
 * 跑 len-1 趟就好
 */
public void switchSort(int[] arr, int len) {
    // len-1 趟，0-i 为已排序区
    for (int i = 0; i < len-1; i++) {
        int minIndex = i;
        for (int j = i+1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

2.3.2. 算法分析

• 选择排序是原地排序，因为只需要用来存储最小值所处位置的额外空间和交换时所需的额外空间。
• 选择排序不是一个稳定的算法。因为选择排序是从未排序区间中找一个最小值，并且和前面的元素交换位置，这会破坏稳定性。比如 1、5、5、2 这样一组数据中，使用排序算法的话。当找到 2 为 5、5、2 当前未排序区间最小的元素时，2 会与第一个 5 交换位置，那么两个 5 的顺序就变了，就破坏了稳定性。
• 时间复杂度分析。最好、最坏、平均都是 O(n^2)，因为无论待排序数组情况怎么样，就算是已经有序了，都是需要依次遍历完未排序区间，需要比较的次数依次是 n-1、n-2，所以时间复杂度是 O(n^2)。

2.4. 归并排序（Merge Sort）

**归并排序的核心思想就是我要对一个数组进行排序：首先将数组分成前后两部分，然后对两部分分别进行排序，排序好之后再将两部分合在一起，那整个数组就是有序的了。对于分出的两部分可以采用相同的方式进行排序。**这个思想就是分治的思想，就是先将大问题分解成小的子问题来解决，子问题解决之后，大问题也就解决了。而对于子问题的求解也是一样的套路。这个套路有点类似于递归的方式，所以分治算法一般使用递归来实现。分治是一种解决问题的处理思想，而递归是一种实现它的编程方法。

2.4.1. 实现

下面使用递归的方式来实现归并排序。递归的递推公式是：merge_sort(p...r) = merge(merge_sort(p...q), merge_sort(q+1...r))，终止条件是 p>=r，不再递归下去了。整个实现过程是先调用 __mergeSort() 函数将两部分分别排好序，之后再使用数组合并的方式将两个排序好的部分进行合并。

/**
 * 归并排序
 */
public void mergeSort(int[] arr, int len) {
    __mergerSort(arr, 0, len-1);
}

private void __mergerSort(int[] arr, int begin, int end) {
    if (begin == end){
        return;
    }

    __mergerSort(arr, begin, (begin+end)/2);
    __mergerSort(arr, (begin+end)/2 + 1, end);
    merge(arr, begin, end);
    return;
}

private void merge(int[] arr, int begin, int end) {
    int[] copyArr = new int[end-begin+1];
    System.arraycopy(arr, begin, copyArr, 0, end-begin+1);

    int mid = (end - begin + 1)/2;
    int i = 0;  // begin - mid 的指针
    int j =  mid;   // mid - end 的指针
    int count = begin;  // 合并之后数组的指针

    while (i <= mid-1 && j <= end - begin) {
        arr[count++] = copyArr[i] < copyArr[j] ? copyArr[i++] : copyArr[j++];
    }

    while (i <= mid-1) {
        arr[count++] = copyArr[i++];
    }

    while (j <= end - begin) {
        arr[count++] = copyArr[j++];
    }
}

2.4.2. 算法分析

• 归并排序可以是稳定的排序算法，只要确保合并时，如果遇到两个相等值的，前半部分那个相等的值是在后半部分那个相等的值的前面即可保证是稳定的排序算法。

• 归并排序的时间复杂度为 O(nlogn)，无论是最好、最坏还是平均情况都一样。

  归并的时间复杂度分析则是递归代码的时间复杂度的分析。假设求解问题 a 可以分为对 b、c 两个子问题的求解。那么问题 a 的时间是 T(a) 、求解 b、c 的时间分别是 T(b) 和 T(c)，那么 T(a) = T(b) +T(c) + K。k 等于将 b、c 两个子问题的结果合并问题 a 所消耗的时间。

  套用上述的套路，假设对 n 个元素进行归并排序需要的时间是 T(n)，子问题归并排序的时间是 T(n/2)，合并操作的时间复杂度是 O(n)。所以，T(n) =2 * T(n/2) +O(n)，T(1) = C。最终得到：

  T(n)= 2*T(n/2) + n
      = 2*(2*T(n/4)+ n/2)+n = 2^2*T(n/4) + 2*n
      = 2^2*(2*T(n/8)+n/4) + 2*n = 2^3*T(n/8) + 3*n
      = ....
      = 2^k*T(n/2^K) + k*n
      = ....
      = 2^(log_2^n)*T(1) + log_2^n*n
  

  最终得到  ，使用大 O 时间复杂表示 T(n)=O(nlogn)。

  归并排序中，无论待排数列是有序还是倒序，最终递归的层次都是到只有一个数组为主，所以归并排序跟待排序列没有什么关系，最好、最坏、平均的时间复杂度都是 O(nlogn)。

• 归并排序并不是原地排序，因为在归并排序的合并函数中，还需要额外的存储空间，这个存储空间是 O(n)。递归过程中，空间复杂度并不能像时间复杂度那样累加。因为在每次递归下去的过程中，虽然合并操作都会申请额外的内存空间，但是合并之后，这些申请的内存空间就会被释放掉。因此其实主要考虑最大问题合并时所需的空间复杂度即可，该空间复杂度为 O(n)。

2.5. 快速排序（Quick Sort）

快速排序利用的也是分治思想，核心思想是从待排数组中选择一个元素，然后将待排数组划分成两个部分：左边部分的元素都小于该元素的值，右边部分的元素都大于该元素的值，中间是该元素的值。然后对左右两个部分套用相同的处理方法，也就是将左边部分的元素再划分成左右两部分，右边部分的元素也再划分成左右两部分。以此类推，当递归到只有一个元素的时候，就说明此时数组是有序了的。

2.5.1. 实现

首先要对下标从 begin 到 end 之间的数据进行分区，可以选择 begin 到 end 之间的任意一个数据作为 pivot（分区点），一般是最后一个数据作为分区点。之后遍历 begin 到 end 之间的数据，将小于 pivot 的放在左边，大于的 pivot 的放在右边，将pivot 放在中间（位置 p）。经过这一操作之后，数组 begin 到 end 之间的数据就被分成了三个部分：begin 到 p-1、p、p+1 到 end。最后，返回 pivot 的下标。那么这个过程一般有三种方式：

• 首先说明这种方法不可取。在不考虑空间消耗的情况下，分区操作可以非常简单。使用两个临时数组 X 和 Y，遍历 begin 到 end 之间的数据，将小于 pivot 的数据都放到数组 X 中，将大于 pivot 的数据都放到数组 Y 中，最后将数组 X 拷贝到原数组中，然后再放入 pivot，最后再放入数组 Y。但是采用这种方式之后，快排就不是原地排序算法了，因此可以采用以下两种方法在原数组的基础之上完成分区操作。
• 第一种方法还是使用两个指针：i 和 j，i 和 j 一开始都放置在 begin 初。之后 j 指针开始遍历，如果 j 指针所指的元素小于等于 pivot，那么则将 j 指针的元素放到 i 指针的处，i  指针的元素放置于 j 处，然后 i 后移，j 后移。如果 j 指针所指的元素大于 pivot 那么 j 后移即可。首先个人觉得其实整个数组被分成三个区域：0-i-1 的为小于等于 pivot 的区域，i-j-1 为大于 pivot 的区域，j 之后的区域是未排序的区域。
• 第二种方法还是使用两个指针：i 和 j，i 从 begin 处开始，j 从 end 处开始。首先 j 从 end 开始往前遍历，当遇到小于 pivot 的时候停下来，然后此时 i 从 begin 开始往后遍历，当遇到大于 pivot 的时候停下来，此时交换 i 和 j 处的元素。之后 j 继续移动，重复上述过程，直至 i >= j。

在返回 pivot 的下标 q 之后，再根据分治的思想，将 begin 到 q-1 之间的数据和下标 q+1 到 end 之间的数据进行递归。这边一定要 q-1 和 q+1 而不能是 q 和 q+1 是因为：考虑数据已经有序的极端情况，一开始是对 begin 到 end；当分区之后 q 的位置还是 end 的位置，那么相当于死循环了。最终，当区间缩小至 1 时，说明所有的数据都有序了。

如果用递推公式来描述上述的过程的话，递推公式：quick_sort(begin...end) = quick_sort(begin...q-1) + quick_sort(q+1...end)，终止条件是：begin >= end。将这两个公式转化为代码之后，如下所示：

/**
 * 快速排序
 */
public void quickSort(int[] arr, int len) {
    __quickSort(arr, 0, len-1);
}

// 注意边界条件
private void __quickSort(int[] arr, int begin, int end) {
    if (begin >= end) {
        return;
    }

    // 一定要是 p-1！
    int p = partition(arr, begin, end); // 先进行大致排序，并获取区分点
    __quickSort(arr, begin, p-1);
    __quickSort(arr, p+1, end);
}

private int partition(int[] arr, int begin, int end) {
    int pValue = arr[end];

    // 整两个指针，两个指针都从头开始
    // begin --- i-1（含 i-1）：小于 pValue 的区
    // i --- j-1（含 j-1）：大于 pValue 的区
    // j --- end：未排序区
    int i = begin;
    int j = begin;
    while (j <= end) {
        if (arr[j] <= pValue) {
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            i++;
            j++;
        } else {
            j++;
        }
    }

    return i-1;
}

2.5.2. 优化

• 由于分区点很重要（为什么重要见算法分析），因此可以想方法寻找一个好的分区点来使得被分区点分开的两个分区中，数据的数量差不多。下面介绍两种比较常见的算法：
• **三数取中法。就是从区间的首、尾、中间分别取出一个数，然后对比大小，取这 3 个数的中间值作为分区点。**但是，如果排序的数组比较大，那“三数取中”可能不够了，可能就要“五数取中”或者“十数取中”，也就是间隔某个固定的长度，取数据进行比较，然后选择中间值最为分区点。
• 随机法。随机法就是从排序的区间中，随机选择一个元素作为分区点。随机法不能保证每次分区点都是比较好的，但是从概率的角度来看，也不太可能出现每次分区点都很差的情况。所以平均情况下，随机法取分区点还是比较好的。
• 递归可能会栈溢出，最好的方式是使用非递归的方式；

2.5.3. 算法分析

• 快排不是一个稳定的排序算法。因为分区的过程涉及到交换操作，原本在前面的元素可能会被交换到后面去。比如 6、8、7、6、3、5、9、4 这个数组中。在经过第一次分区操作之后，两个 6 的顺序就会发生改变。

• 快排是一种原地的排序算法。

• 快排的最坏时间复杂度是 O(n^2)，最好时间复杂度是O(nlogn)，平均时间复杂度是 O(nlogn)。

  快排也是使用递归来实现，那么递归代码的时间复杂度处理方式和前面类似。

  快排的时间复杂度取决于 pivot 的选择，通过合理地选择 pivot 来使得算法的时间复杂度尽可能不出现 O(n^2) 的情况。

• 假设每次分区操作都可以把数组分成大小接近相等的两个小区间，那么快排的时间复杂度和归并排序一样，都是 O(nlogn)。
• 但是分区操作不一定都能把数组分成大小接近相等的两个小区间。极端情况如数组中的数组已经有序了，如果还是取最后一个元素作为分割点，左边区间是 n-1 个数，右边区间没有任何数。此时， T(n)=T(n-1)+n，最终时间复杂度退化为 O(n^2)。大部分情况下，采用递归树的方法可得到时间复杂度是 O(nlogn)。由于极端情况是少数，因此平均时间复杂度是 O(nlogn)。

2.5.4. VS 归并排序

首先从思想上来看：归并排序的处理过程是由下到上的，先处理子问题，然后对子问题的解再合并；而快排正好相反，处理过程是由上到下的，先分区，再处理子问题。

从性能上来看：归并是一个稳定的、时间复杂度为 O(nlogn) 的排序算法，但是归并并不是一个原地排序算法（所以归并没有快排应用广泛）。而快速排序算法时间复杂度不一定是 O(nlogn)，最坏情况下是 O(n^2)，而且不是一个稳定的算法，但是通过设计可以让快速排序成为一个原地排序算法。

2.6. 桶排序

**桶排序的核心思想就是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。**桶内排序完成之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。一般步骤是：

• 先确定要排序的数据的范围；
• 然后根据范围将数据分到桶中（可以选择桶的数量固定，也可以选择桶的大小固定）；
• 之后对每个桶进行排序；
• 之后将桶中的数据进行合并；

2.6.1. 实现

public void buckerSort(int[] arr, int len, int bucketCount) {

    // 确定数据的范围
    int minVal = arr[0];
    int maxVal = arr[0];
    for (int i = 1; i < len; ++i) {
        if (arr[i] < minVal) {
            minVal = arr[i];
        } else if (arr[i] > maxVal){
            maxVal = arr[i];
        }
    }

    // 确认每个桶的所表示的范围
    bucketCount =  (maxVal - minVal + 1) < bucketCount ? (maxVal - minVal + 1) : bucketCount;
    int bucketSize = (maxVal - minVal + 1) / bucketCount;
    bucketCount = (maxVal -  minVal + 1) % bucketCount == 0 ? bucketCount : bucketCount + 1;

    int[][] buckets = new int[bucketCount][bucketSize];
    int[] indexArr = new int[bucketCount];  // 数组位置记录

    // 将数据依次放入桶中
    for (int i = 0; i < len; i++) {
        int bucketIndex = (arr[i] - minVal) / bucketSize;
        if (indexArr[bucketIndex] == buckets[bucketIndex].length) {
            expandCapacity(buckets, bucketIndex);
        }
        buckets[bucketIndex][indexArr[bucketIndex]++] = arr[i];
    }

    // 桶内排序
    for (int i = 0; i < bucketCount; ++i) {
        if (indexArr[i] != 0) {
            quickSort(buckets[i], 0, indexArr[i] - 1);
        }
    }

    // 桶内数据依次取出
    int index = 0;
    for (int i = 0; i < bucketCount; ++i) {
        for (int j = 0; j < indexArr[i]; ++j) {
            arr[index++] = buckets[i][j];
        }
    }

    // 打印
    for (int i = 0; i < len; ++i) {
        System.out.print(arr[i] + " ");
    }
    System.out.println();
}

// 对数组进行扩容
public void expandCapacity(int[][] buckets, int bucketIndex) {
    int[] newArr = new int[buckets[bucketIndex].length * 2];
    System.arraycopy(buckets[bucketIndex], 0, newArr, 0, buckets[bucketIndex].length);
    buckets[bucketIndex] = newArr;
}

2.6.2. 算法分析

• 最好时间复杂度为 O(n)，最坏时间复杂度为 O(nlogn)，平均时间复杂度为 O(n)。

  如果要排序的数据为 n 个，把这些数据均匀地分到 m 个桶内，每个桶就有 k=n/m 个元素。每个桶使用快速排序，时间复杂度为 O(k.logk)。m 个 桶的时间复杂度就是 O(m*k*logk)，转换的时间复杂度就是 O(n*log(n/m))。当桶的数量 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。

  如果数据经过桶的划分之后，每个桶的数据很不平均，比如一个桶中包含了所有数据，那么桶排序就退化为 O(nlogn) 的排序算法了。

  这边的平均时间复杂度为 O(n) 没有经过严格运算，只是采用粗略的方式得出的。因为桶排序大部分情况下，都能将数据进行大致均分，而极少情况出现所有的数据都在一个桶里。

• 非原地算法

  因为桶排序的过程中，需要创建 m 个桶这个的空间复杂度就肯定不是 O(1) 了。在桶内采用快速排序的情况下，桶排序的空间复杂度应该是 O(n)。

• 桶排序的稳定与否，主要看两块：1.将数据放入桶中的时候是否按照顺序放入；2.桶内采用的排序算法。所以将数据放入桶中是按照顺序的，并且桶内也采用稳定的排序算法的话，那么整个桶排序则是稳定的。既然能稳定的话，那么一般算稳定的。

2.6.3. 总结

• 桶排序对要排序的数据的要求是非常苛刻的。

• 首先，要排序的数据需要很容易被划分到 m 个桶。并且，桶与桶之间有着天然的大小顺序，这样子每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序；

• 其次，数据在各个桶中的分布是比较均匀的。如果数据经过桶的划分之后，每个桶的数据很不平均，比如一个桶中包含了所有数据，那么桶排序就退化为 O(nlogn) 的排序算法了。

• **桶排序适合应用在外部排序中。**比如要排序的数据有 10 GB 的订单数据，但是内存只有几百 MB，无法一次性把  10GB 的数据全都加载到内存中。这个时候，就可以先扫描 10GB 的订单数据，然后确定一下订单数据的所处的范围，比如订单的范围位于 1~10 万元之间，那么可以将所有的数据划分到 100 个桶里。再依次扫描 10GB 的订单数据，把 1~1000 元之内的订单存放到第一个桶中，1001~2000 元之内的订单数据存放到第二个桶中，每个桶对应一个文件，文件的命名按照金额范围的大小顺序编号如 00、01，即第一个桶的数据输出到文件 00 中。

  理想情况下，如果订单数据是均匀分布的话，每个文件的数据大约是 100MB，依次将这些文件的数据读取到内存中，利用快排来排序，再将排序好的数据存放回文件中。最后只要按照文件顺序依次读取文件中的数据，并将这些数据写入到一个文件中，那么这个文件中的数据就是排序好了的。

  但是，订单数据不一定是均匀分布的。划分之后可能还会存在比较大的文件，那就继续划分。比如订单金额在 1~1000 元之间的比较多，那就将这个区间继续划分为 10 个小区间，1~100、101~200 等等。如果划分之后还是很大，那么继续划分，直到所有的文件都能读入内存。

  ★

  外部排序就是数据存储在磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

  ”

2.7. 计数排序

计数排序跟桶排序类似，可以说计数排序其实是桶排序的一种特殊情况。**当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 K，那么就可以把数据划分到 K 个桶，每个桶内的数据值都是相同的，**从而省掉了桶内排序的时间。可以说计数排序和桶排序的区别其实也就在于桶的大小粒度不一样。

下面通过举例子的方式来看一下计数排序的过程。假设数组 A 中有 8 个数据，值在 0 到 5 之间，分别是：2、5、3、0、2、3、0、3。

• 首先使用大小为 6 的数组 C[6] 来存储每个值的个数，下标对应具体值。从而得到，C[6] 的情况为：2、0、2、3、0、1。
• 那么，值为 3 分的数据个数有 3 个，小于 3 分的数据个数有 4 个，所以值为 3 的数据在有序数组 R 中所处的位置应该是 4、5、6。为了快速计算出位置，对 C[6] 这个数组进行变化，C[k] 里存储小于等于值 k 的数据个数。变化之后的数组为 2、2、4、7、7、8。
• 之后我们从后往前依次扫描数据 A（ 从后往前是为了稳定），比如扫描到 3 的时候，从数据 C 中取出下标为 3 的值，是7（也就说到目前为止，包含自己在内，值小于等于 3 的数据个数有 7 个），那么 3 就是数组 R 中第 7 个元素，也就是下标为 6。当然 3 放入到数组 R 中后，C[3] 要减 1，变成 6，表示此时未排序的数据中小于等于 3 的数据个数有 6 个。
• 以此类推，当扫描到第 2 个值为 3 的数据的时候，就会将这个数据放入到 R 中下标为 5 的位置。当扫描完整个数组 A 后，数组 R 内的数据就是按照值从小到大的有序排列了。

2.7.1. 实现

/**
 * 计数排序，暂时只能处理整数（包括整数和负数）
 * @param arr
 * @param len
 */
public void countingSort(int[] arr, int len) {
    // 确定范围
    int minVal = arr[0];
    int maxVal = arr[0];
    for (int i = 1; i < len; ++i) {
        if (maxVal < arr[i]) {
            maxVal = arr[i];
        } else if (arr[i] < minVal) {
            minVal = arr[i];
        }
    }

    // 对数据进行处理
    for (int i = 0; i < len; ++i) {
        arr[i] = arr[i] - minVal;
    }
    maxVal = maxVal - minVal;

    // 遍历数据数组，求得计数数组的个数
    int[] count = new int[maxVal + 1];
    for (int i = 0; i < len; ++i) {
        count[arr[i]] ++;
    }
    printAll(count, maxVal + 1);

    // 对计数数组进行优化
    for (int i = 1; i < maxVal + 1; ++i) {
        count[i] = count[i - 1] + count[i];
    }
    printAll(count, maxVal + 1);

    // 进行排序，从后往前遍历（为了稳定）
    int[] sort = new int[len];
    for (int i = len - 1; i >= 0; --i) {
        sort[count[arr[i]] - 1] = arr[i] + minVal;
        count[arr[i]]--;
    }
    printAll(sort, len);
}

2.7.2. 算法分析

• 非原地算法

  计数排序相当于桶排序的特例一样。计数排序需要额外的 k 个内存空间和 n 个新的内存空间存放排序之后的数组。

• 稳定算法

  前面也提到了，假如采用从后往前遍历的方式话，那么是稳定算法。

• 时间复杂度

  最好、最坏、平均时间复杂度都是一样，为 O(n+k)，k 为数据范围。这个从代码的实现可以看出，无论待排数组的情况怎么样，都是要循环同样的次数。

2.7.3. 总结

• 计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。
• 计数排序只能直接对非负整数进行排序，如果要排序的数据是其他类型的，需要在不改变相对大小的情况下，转化为非负整数。比如当要排序的数是精确到小数点后一位时，就需要将所有的数据的值都先乘以 10，转换为整数。再比如排序的数据中有负数时，数据的范围是[-1000,1000]，那么就需要先将每个数据加上 1000，转换为非负整数。

2.8. 基数排序

桶排序和计数排序都适合范围不是特别大的情况（请注意是范围），但是桶排序的范围可以比计数排序的范围稍微大一点。假如数据的范围很大很大，比如对手机号这种的，桶排序和技术排序显然不适合，因为需要的桶的数量也是十分巨大的。此时，可以使用基数排序。**基数排序的思想就是将要排序的数据拆分成位，然后逐位按照先后顺序进行比较。**比如手机号中就可以从后往前，先按照手机号最后一位来进行排序，之后再按照倒数第二位来进行排序，以此类推。当按照第一位重新排序之后，整个排序就算完成了。

需要注意的是**，按照每位排序的过程需要稳定的**，因为假如后一次的排序不稳定，前一次的排序结果将功亏一篑。比如，第一次对个位进行排序结果为 21、11、42、22、62，此时 21 在 22 前面；第二次对十位的排序假如是不稳定的话，22 可能跑到 21 前面去了。那么整个排序就错了，对个位的排序也就相当于白费了。

下面举个字符串的例子，整个基数排序的过程如下图所示：

2.8.1. 实现

/**
 * 基数排序
 * @param arr
 * @param len
 */
public void radixSort(int[] arr, int len, int bitCount) {
    int exp = 1;
    for (int i = 0; i < bitCount; ++i) {
        countingSort(arr, len, exp);
        exp = exp * 10;
    }
}

public int getBit(int value, int exp) {
    return (value / exp) % 10;
}
/**
 * 计数排序，暂时只能处理整数（包括整数和负数）
 * @param arr
 * @param len
 */
public void countingSort(int[] arr, int len, int exp) {

    // 确定范围
    int maxVal = getBit(arr[0], exp);
    for (int i = 1; i < len; ++i) {
        if (maxVal < getBit(arr[i], exp)) {
            maxVal = getBit(arr[i], exp);
        }
    }

    // 遍历数据数组，求得计数数组的个数
    int[] count = new int[maxVal + 1];
    for (int i = 0; i < len; ++i) {
        count[getBit(arr[i], exp)] ++;
    }

    // 对计数数组进行优化
    for (int i = 1; i < maxVal + 1; ++i) {
        count[i] = count[i - 1] + count[i];
    }

    // 进行排序，从后往前遍历（为了稳定）
    int[] sort = new int[len];
    for (int i = len - 1; i >= 0; --i) {
        sort[count[getBit(arr[i], exp)] - 1] = arr[i];
        count[getBit(arr[i], exp)]--;
    }
    System.arraycopy(sort, 0, arr, 0, len);
    printAll(sort, len);
}

2.8.2. 算法分析

• 非原地算法

  是不是原地算法其实看针对每一位排序时所使用的算法。为了确保基数排序的时间复杂度以及每一位的稳定性，一般采用计数排序，计数排序是非原地算法，所以可以把基数排序当成非原地排序。

• 稳定算法

  因为基数排序需要确保每一位进行排序时都是稳定的，所以整个基数排序时稳定的。

• 时间复杂度是 O(kn)，k 是数组的位数

  最好、最坏、平均的时间复杂度都是 O(n)。因为无论待排数组的情况怎么样，基数排序其实都是遍历每一位，对每一位进行排序。假如每一位排序的过程中使用计数排序，时间复杂度为 O(n)。假如有 k 位的话，那么则需要 k 次桶排序或者计数排序。因此总的时间复杂度是 O(kn)，当 k 不大时，比如手机号是 11 位，那么基数排序的时间复杂度就近似于 O(n)。也可以从代码中看出。

2.8.3. 总结

• 基数排序的一个要求是排序的数据要是等长的。当不等长时候可以在前面或者后面补 0，比如字符串排序的话，就可以在后面补 0，因为 ASCII 码中所有的字母都大于 “0”，所以补 “0” 不会影响到原有的大小排序。
  基数排序的另一个要求就是数据可以分割出独立的 “位” 来比较，而且位之间存在递进关系：如果 a 数据的高位比 b 数据大，那么剩下的低位就不用比较了。
  除此之外，每一个位的数据范围不能太大，要能用线性排序算法来排序，否则，基数排序时间复杂度无法达到 O(n)。
  
  

3. 排序函数

几乎所有编程语言都会提供排序函数，比如 C 语言中 qsort()、C++ STL 中的 sort()/stable_sort()、Java 中的 Collections.sort()。这些排序函数，并不会只采用一种排序算法，而是多种排序算法的结合。当然主要使用的排序算法都是 O(nlogn) 的。

• glibc 的 qsort() 排序函数。qsort() 会优先使用归并排序算法。当排序的数据量很大时，会使用快速排序。使用排序算法的时候也会进行优化，如使用 “三数取中法”、在堆上手动实现一个栈来模拟递归来解决。在快排的过程中，如果排序的区间的元素个数小于等于 4 时，则使用插入排序。而且在插入排序中还用到了哨兵机制，减少了一次判断。

  ★

  在小规模数据面前 O(n^2) 时间复杂度的算法并不一定比 O(nlogn)的算法执行时间长。主要是因为时间复杂度会将系数和低阶去掉。

  ”

• Array.sort() 排序函数，使用 TimSort 算法。TimSort 算法是一种归并算法和插入排序算法混合的排序算法。基本工作过程就是：

  整个排序过程，分段选择策略可以保证 O(nlogn) 的时间复杂度。TimSort 主要利用了待排序列中可能有些片段已经基本有序的特性。之后，对于小片段采用插入算法进行合并，合并成大片段。最后，再使用归并排序的方式进行合并，从而完成排序工作。

• 扫描数组，确定其中的单调上升段和单调下降段，将严格下降段反转；
• 定义最小基本片段长度，长度不满足的单调片段通过插入排序的方式形成满足长度的单调片段（就是长度大于等于所要求的最小基本片段长度）
• 反复归并一些相邻片段，过程中避免归并长度相差很大的片段，直至整个排序完成。

4. 附加知识

4.1. 有序度、逆序度

在以从小到大为有序的情况中，有序度是数组中有序关系的元素对的个数，用数学公式表示如下所示。

如果 i < j，那么 a[i] < a[j]

比如 2、4、3、1、5、6 这组数据的有序度是 11；倒序排列的数组，有序度是 0；一个完全有序的数组，有序度为满有序度，为 n*(n-1)/2，比如1、2、3、4、5、6，有序度就是 15。

逆序度的定义正好跟有序度的定义相反

如果 i < j，那么 a[i] > a[j]

关于逆序度、有序度、满有序度满足如下公式

逆序度 = 满有序度 - 有序度

排序的过程其实就是减少逆序度，增加有序度的过程，如果待排序序列达到满有序度了，那么此时的序列就是有序了。

5. 总结

• 冒泡排序、选择排序可能就停留在理论的层面，实际开发应用中不多，但是插入排序还是挺有用的，有些排序算法优化的时候就会用到插入排序，比如在排序数据量小的时候会先选择插入排序。

• 冒泡、选择、插入三者的时间复杂度一般都是按 n^2 来算。**并且这三者都有一个共同特点，那就是都会将排序数列分成已排序和未排序两部分。**外层循环一次，其实是让有序部分增加一个，因此外层循环相当于对有序部分和未排序部分进行分割。而外层循环次数就是待排序的数据的个数；内层循环则主要负责处理未排序部分的元素。

• 快排的分区过程和分区思想其实特别好用，在解决很多非排序的问题上都会遇到。比如如何在 O(n) 的时间复杂度内查找一个 k 最值的问题（还用到分治，更多是分区这种方式）；比如将一串字符串划分成字母和数字两部分（其实就是分区，所以需要注意分区过程的应用）。以后看到类似分区什么的，可以想想快排分区过程的操作。

• 快排和归并使用都是分治的思想，都可使用递归的方式实现。只是归并是从下往上的处理过程，是先进行子问题处理，然后再合并；而快排是从上往下的处理过程，是先进行分区，而后再进行子问题处理。

• 桶排序、计数排序、基数排序的时间复杂度是线性的，所以这类排序算法叫做线性排序。之所以这能做到线性排序，主要是因为这三种算法都不是基于比较的排序算法，不涉及到元素之间的比较操作。但是这三种算法对排序的数据要求很苛刻。如果数据特征比较符合这些排序算法的要求，这些算法的复杂度可以达到 O(n)。

• 桶排序、计数排序针对范围不大的数据是可行的，它们的基本思想都是将数据划分为不同的桶来实现排序。

• 各种算法比较

  排序算法	平均时间复杂度	最好时间复杂度	最坏时间复杂度	是否是原地排序	是否稳定
  冒泡	O(n^2)	O(n)	O(n^2)	√	√
  插入	O(n^2)	O(n)	O(n^2)	√	√
  选择	O(n^2)	O(n^2)	O(n^2)	√	×
  归并	O(nlogn)	O(nlogn)	O(nlogn)	×  O(n)	√
  快排	O(nlogn)	O(nlogn)	O(n^2)	√	×
  桶排序	O(n)	O(n)	O(nlogn)	×	√
  计数排序	O(n+k)	O(n+k)	O(n+k)	×	√
  基数排序	O(kn)	O(kn)	O(kn)	×	√

巨人的肩膀

1. 极客时间，《数据结构与算法之美》
2. 《算法图解》