# 排序

这一节介绍一些常用的排序算法。

# 如何分析一个 “排序算法”

# 执行效率

对于排序算法执行效率的分析，我们一般会从这几个方面来衡量：

# 最好情况、最坏情况、平均情况时间复杂度

在分析排序算法的时间复杂度时，要分别给出最好情况、最坏情况、平均情况下的时间复杂度。

除此之外，你还要说出最好、最坏时间复杂度对应的要排序的原始数据是什么样的。

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

算法时间复杂度反应的是数据规模 n 增大的时候的一个增长趋势。当 n 很大的时候，我们会忽略系数、常数、低阶。

但是实际的软件开发中，我们排序的可能是 10 个、100 个、1000 个这样规模很小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。

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

基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。

所以，如果我们在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。

# 内存消耗

针对排序算法的空间复杂度，我们引入了一个新的概念，原地排序（Sorted in place）。

原地排序算法，就是指在排序过程中不申请多余的存储空间，只在原来存储 “待排数据” 的存储空间，进行比较和交换的排序算法。其空间复杂度是 $O(1)$ 。

# 稳定性

针对排序算法，还有一个重要的度量指标，稳定性。

这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

举例来讲，比如我们有一组数据 2，9，3，4，8，3，按照大小排序之后就是 2，3，3，4，8，9。这组数据里有两个 3。经过某种排序算法排序之后，如果两个 3 的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。

🌰 通过一个例子来说明，为什么要判断一个算法是否稳定。

# 冒泡排序

💡 思路：

• 对相邻的两个元素进行比较，看是否满足大小关系要求；
• 如果不满足就交换，满足就不动；
• 一次冒泡会让至少一个元素移动到它应该在的位置。重复 n 次，就完成了 n 个数据的排序；

// 冒泡排序，a 表示数组，n 表示数组大小
void bubbleSort(int[] a, int n) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (a[j] > a[j + 1]) { // 交换
        int tmp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = tmp;
      }
    }
  }
}

上面的代码还可以优化。当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。

上面的代码修改之后如下：

// 冒泡排序，a 表示数组，n 表示数组大小
void bubbleSort(int[] a, int n) {
  for (int i = 0; i < n; i++) {
    // 用以判断是否可以提前退出循环
    boolean flag = false;

    for (int j = 0; j < n - i - 1; j++) {
      if (a[j] > a[j + 1]) { // 交换
        int tmp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = tmp;
        flag = true; // 表示有数据交换
      }
    }

    if (!flag) break; // 没有数据交换，提前退出
  }
}

# 冒泡排序是原地排序算法吗？

冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 $O(1)$，是一个原地排序算法。

# 冒泡排序是稳定的排序算法吗？

为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

# 冒泡排序的时间复杂度是多少？

最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是 $O(n)$。

而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 $O(n^2)$。

# 插入排序

💡 思路：

• 将数组中的数据分为两个区间，“已排序区间” 和 “未排序区间”；
• 初始已排序区间只有第一个元素；
• 依次将未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入；
• 直至未排序区间为空；

用 for-loop 实现：

// 插入排序，a 表示数组，n 表示数组大小
void insertionSort(int[] a, int n) {
  for (int i = 1; i < n; i++) {
    int value = a[i];
    // 查找插入的位置
    for (int j = i - 1; j >= 0; j--) {
      if (value < a[j]) a[j + 1] = a[j];
      else break;
    }
    a[j + 1] = value; // 插入数据
  }
}

用 while 实现：

void insert_sort(int[] a, int n) {
  for (int i = 1; i < n; i++) {
    int value = a[i];
    int j = i - 1;
    while (j >= 0 && a[j] > value) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = value;
  }
}

# 插入排序是原地排序算法吗？

插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 $O(1)$，这是一个原地排序算法。

# 插入排序是稳定的排序算法吗？

在插入排序中，对于值相同的元素，插入排序依旧保持原有的前后顺序，所以插入排序是稳定的排序算法。

# 插入排序的时间复杂度是多少？

如果要排序的数据已经是有序的，并不需要搬移任何数据。从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好情况时间复杂度为 $O(n)$。

如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，最坏情况时间复杂度为 $O(n^2)$。

# 选择排序

💡 思路：

• 将数组中的数据分为两个区间，“已排序区间” 和 “未排序区间”；
• 从 “未排序区间” 中找到最小值并将其放置在 “已排序区间” 的末尾；
• 循环这个步骤，直至未排序区间为空；

void select_sort(int[] a, int n) {
  for (int i = 0; i < n; i++) {
    int minIndex = i;
    // 找到最小元素
    for (int j = i + 1; j < n; j++) {
      if(a[j] < a[minIndex]) minIndex = j;
    }
    // 交换最小元素与第一个未排序元素
    int temp = a[i];
    a[i] = a[minIndex];
    a[minIndex] = temp;
  }
}

# 选择排序是原地排序算法吗？

选择排序空间复杂度为 $O(1)$，是一种原地排序算法。

# 选择排序是稳定的排序算法吗？

选择排序是一种不稳定的排序算法。从我前面画的那张图中，你可以看出来，选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。

🌰 比如 5，8，5，2，9 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以就不稳定了。

# 选择排序的时间复杂度是多少？

选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 $O(n^2)$。

# 归并排序

采用分治思想，将一个大问题分解成小的子问题来解决。

分治算法一般都是用递归来实现的。

💡 思路：

• 采用分治思想, 将原始数组切分成较小的数组，直到每个小数组只有一个项；
• 接着将小数组归并成较大的数组，归并的时候将两个小数组排序成一个顺序的大数组；
• 直到最后只有一个排序完毕的大数组；

我们先写出归并排序算法的 “递推公式” 和 “终止条件”：

递推公式：merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
终止条件：p >= r 不用再继续分解

public static void merge_sort(int[] a, int n) {
  divide(a, 0, n - 1);
}

// 切分
public static void divide(int[] a, int low, int high) {
  int mid = (low + high) / 2;

  if (low < high) {
    // 左边
    divide(a, low, mid);
    // 右边
    divide(a, mid + 1, high);
    // 左右归并
    merge(a, low, mid, high);
  }
}

// 合并
public static void merge(int[] a, int low, int mid, int high) {
  int[] temp = new int[high - low + 1];

  int i = low;
  int j = mid + 1;
  int k = 0;

  // 按照从小到大排列
  while (i <= mid && j <= high) {
    if (a[i] <= a[j]) {
      temp[k] = a[i];
      k++;
      i++;
    } else {
      temp[k] = a[j];
      k++;
      j++;
    }
  }

  // 把左边剩余的数移入数组
  while (i <= mid) {
    temp[k] = a[i];
    k++;
    i++;
  }
  // 把右边边剩余的数移入数组
  while (j <= high) {
    temp[k] = a[j];
    k++;
    j++;
  }
  // 把新数组中的数覆盖原数组
  for (k = 0; k < temp.length; k++) {
    a[k + low] = temp[k];
  }
}

# 归并排序是原地排序算法吗

归并排序在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。在合并完成之后，临时开辟的内存空间就会被释放掉。

在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 $O(n)$。

# 归并排序是稳定的排序算法吗

归并排序稳不稳定关键要看 merge() 函数，也就是两个有序子数组合并成一个有序数组的那部分代码。在合并的过程中，如果 A[p…q] 和 A[q+1…r] 之间有值相同的元素，那我们先把 A[p…q] 中的元素放入临时数组。这样就保证了值相同的元素，在合并前后的先后顺序不变。

所以，归并排序是一个稳定的排序算法。

# 归并排序的时间复杂度是多少

在递归算法中，不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。

假设对 n 个元素进行归并排序需要的时间是 $T(n)$，那分解出的两个子数组的排序时间都是 $T(n/2)$。

从代码中可以看出，merge() 函数合并两个有序子数组的时间复杂度是 $O(n)$。

归并排序的时间复杂度的计算公式就是：

• $T(1) = C$；$n = 1$ 时，只需要常量级的执行时间，所以表示为 $C$；
• $T(n) = 2 * T(n / 2) + n$； $n > 1$ 后面加上的 $n$ 是合并的时间；

根据上面的两个公式，我们递归的分解：

$T(n) = 2*T(n/2) + n$ $= 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n$ $= 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n$ $= 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n$ $......$ $= 2^k * T(n/2^k) + k * n$ $......$

当 $T(n/2^k)=T(1)$ 时，也就是 $n/2^k=1$ 时，分解停止。我们得到 $k=log_2n$。将 $k$ 值代入上面的公式，得到 $T(n)=Cn+nlog_2n$。

用大 O 标记法来表示的话，$T(n)$ 就等于 $O(nlogn)$。所以归并排序的时间复杂度是 $O(nlogn)$。

# 快速排序

💡 思路：

• 采用分治策略. 首先，从数组中选择任意一项作为主元（piovt）；
• 创建两个指针，左边一个指向数组第一个项，右边一个指向数组最后一个项。移动左指针直到我们找到一个比主元大的元素，接着，移动右指针直到找到一个比主元小的元素，然后交换它们;
• 重复这个过程，直到左指针超过了右指针. 这个过程将使得比主元小的值都排在主元之前，而比主元大的值都排在主元之后。这一步叫作划分操作；
• 接着，算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的子数组）重复之前的两个步骤，直至数组已完全排序；

下图中, 对有较小值的子数组执行划分操作

下图是针对上图中有较大值的子数组执行划分操作

然后较大子数组 $[5, 4]$ 也继续进行划分。最终，较大子数组 $[6, 7]$ 也会进行划分操作。

public static void quick_sort(int[] a, int n) {
  quick(a, 0, n - 1);
}

public static int partition(int[] a, int left, int right) {
  // 取数组的中间元素作为主元
  int index = (left + right) / 2;
  int pivot = a[index];
  int i = left;
  int j = right;

  while (i <= j) {
    // 如果左边元素小于主元，就将左边指针向右移动一格
    // 如果左边元素大于或等于主元，左边指针就不动了
    while (a[i] < pivot) {
      i++;
    }
    // 如果右边元素大于主元，就将右边指针向左移动一格
    // 如果右边元素小于或等于主元，右边指针就不动了
    while (a[j] > pivot) {
      j--;
    }
    // 如果左边指针比右边指针小，那么就交换指针各自指向的元素
    // 并且指针继续向前走一格
    if (i <= j) {
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
      i++;
      j--;
    }
  }
  // 返回左边指针所在位置
  return i;
};

public static void quick(int[] a, int left, int right) {
  if (right - left < 1)
    return;

  // 进行分区
  int index = partition(a, left, right);
  System.out.println("\n");
  System.out.print("主元：" + a[index] + " -- ");
  for (int i = 0; i < a.length; i++) {
    System.out.print(a[i] + " ");
  }

  if (left < index - 1) {
    quick(a, left, index - 1);
  }

  if (right > index) {
    quick(a, index, right);
  }
};

# 归并排序是原地排序算法吗

快速排序可以实现原地排序。相较于归并排序，占用的内存更少。

# 归并排序是稳定的排序算法吗

因为分区的过程涉及交换操作，如果数组中有两个相同的元素，比如序列 6，8，7，6，3，5，9，4，在经过第一次分区操作之后，两个 6 的相对先后顺序就会改变。所以，快速排序是一个不稳定的排序算法。

# 归并排序的时间复杂度是多少

如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，那快排的时间复杂度递推求解公式跟归并是相同的。所以，快排的最好情况时间复杂度也是 $O(nlogn)$。

但如果数组中的数据原来已经是有序的了，比如 1，3，5，6，8。如果我们每次选择最后一个元素作为 pivot，那每次分区得到的两个区间都是不均等的。我们需要进行大约 $n$ 次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约 $n/2$ 个元素，这种情况下，快排的时间复杂度就从 $O(nlogn)$ 退化成了最坏情况时间复杂度 $O(n^2)$。

# 堆排序

直接看 『 堆 』那一篇

# 桶排序

桶排序是一种线性排序，它的时间复杂度是 $O(n)$

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

• 找到数组中的 “最大值” 和 “最小值”；
• 设置每个桶存放数据的粒度；
• 用最大值与最小值之间的差，除以每个桶的范围，得到需要的桶的数量；
• 把数据放到对应的桶中；
• 对每个不为空的桶中数据进行排序；
• 拼接不为空的桶中数据，得到结果；

public static int[] bucket_sort(int[] arr, int bucketSize) throws Exception {

  if (arr.length == 0) {
    return arr;
  }

  // 找到数组中的 “最大值” 和 “最小值”
  int minValue = arr[0];
  int maxValue = arr[0];
  for (int i = 0; i < arr.length; i++) {
    int value = arr[i];
    if (value < minValue) {
      minValue = value;
    } else if (value > maxValue) {
      maxValue = value;
    }
  }
  // 创建桶
  // 注意：因为是整数除法，等于进行了 floor 操作，所以要在结果加 1
  int bucketCount = (maxValue - minValue) / bucketSize + 1;
  int[][] buckets = new int[bucketCount][0];
  // 利用映射函数将数据分配到各个桶中
  for (int i = 0; i < arr.length; i++) {
    int index = (arr[i] - minValue) / bucketSize;
    buckets[index] = arr_append(buckets[index], arr[i]);
  }

  int arrIndex = 0;
  for (int j = 0; j < buckets.length; j++) {
    int[] bucket = buckets[j];

    // 如果桶是空的，就直接跳过
    if (bucket.length <= 0) {
      continue;
    }
    // 对每个桶进行排序，这里使用了快速排序
    quick_sort(bucket, bucket.length);
    for (int k = 0; k < bucket.length; k++) {
      int value = bucket[k];
      arr[arrIndex] = value;
      arrIndex++;
    }
  }

  return arr;
}

// 自动扩容，并保存数据
public static int[] arr_append(int[] arr, int value) {
  arr = Arrays.copyOf(arr, arr.length + 1);
  arr[arr.length - 1] = value;
  return arr;
}

# 桶排序的应用条件 & 应用场景

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

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

其次，数据在各个桶内数据的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。

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

🌰 比如说我们有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百 MB，没办法一次性把 10GB 的数据都加载到内存中。

• 我们可以先扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后我们得到，订单金额最小是 1 元，最大是 10 万元；
• 我们将所有订单根据金额划分到 100 个桶里，第一个桶我们存储金额在 1 元到 1000 元之内的订单，第二桶存储金额在 1001 元到 2000 元之内的订单，以此类推；
• 每一个桶对应一个文件，并且按照金额范围的大小顺序编号命名（00，01，02…99）；
• 理想的情况下，如果订单金额在 1 到 10 万之间均匀分布，那订单会被均匀划分到 100 个文件中，每个小文件中存储大约 100MB 的订单数据；
• 我们就可以将这 100 个小文件依次放到内存中，用快速排序来排序；
• 等所有文件都排好序之后，我们只需要按照文件编号，从小到大依次读取每个小文件中的订单数据，并将其写入到一个文件中，那这个文件中存储的就是按照金额从小到大排序的订单数据了；

# 桶排序的时间复杂度分析

如果要排序的数据有 $n$ 个，我们把它们均匀地划分到 $m$ 个桶内，每个桶里就有 $k=n/m$ 个元素。

每个桶内部使用快速排序，时间复杂度为 $O(k * logk)$。$m$ 个桶排序的时间复杂度就是 $O(m * k * logk)$。

因为 $k=n/m$，所以整个桶排序的时间复杂度就是 $O(n*log(n/m))$。

当桶的个数 $m$ 接近数据个数 $n$ 时，$log(n/m)$ 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 $O(n)$。

# 计数排序

计数排序是一种线性排序，它的时间复杂度是 $O(n)$

💡 思路：计数排序其实是桶排序的一种特殊情况。每个桶的粒度只有 1。

• 花 $O(n)$ 的时间扫描一下整个序列 A，获取最小值 min 和最大值 max；
• 开辟一块新的空间创建新的数组 B，长度为 $max - min + 1$；
• 数组 B 中的元素记录的值是 A 中某元素出现的次数；
• 最后遍历数组 B，输出相应元素以及对应的个数，到顺序数组中；

注意：计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，我们需要把数据映射为非负整数。

🌰 举例说明，在高考查分数系统中。我们查分数的时候，系统会显示我们的成绩以及所在省的排名。如果你所在的省有 50 万考生，如何通过成绩快速排序得出名次呢？考生的满分是 900 分，最小是 0 分，这个数据的范围很小，所以我们可以分成 901 个桶，对应分数从 0 分到 900 分。根据考生的成绩，我们将这 50 万考生划分到这 901 个桶里。桶内的数据都是分数相同的考生，所以并不需要再进行排序。我们只需要依次扫描每个桶，将桶内的考生依次输出到一个数组中，就实现了 50 万考生的排序。因为只涉及扫描遍历操作，所以时间复杂度是 $O(n)$。

// 计数排序，a 是数组，n 是数组大小。假设数组中存储的都是非负整数。
public static void counting_sort(int[] a, int n) {
  if (n <= 1)
    return;

  // 查找数组中数据的范围
  int max = a[0];
  int min = a[0];
  for (int i = 1; i < n; ++i) {
    if (max < a[i]) {
      max = a[i];
    } else if (min > a[i]) {
      min = a[i];
    }
  }

  // 申请一个计数数组 c
  int[] c = new int[max - min + 1];
  for (int i = 0; i < max - min + 1; i++) {
    c[i] = 0;
  }

  // 计算每个元素的个数，放入c中
  for (int i = 0; i < n; i++) {
    c[a[i] - min]++;
  }

  // 临时数组，存储排序之后的结果
  int[] temp = new int[n];

  int sortedIndex = 0;
  for (int i = 0; i < max - min + 1; i++) {
    int count = c[i];
    for (int j = 0; j < count; j++) {
      temp[sortedIndex] = i + min;
      sortedIndex++;
    }
  }

  // 将结果拷贝给 a 数组
  for (int i = 0; i < n; ++i) {
    a[i] = temp[i];
  }
}

# 基数排序

基数排序是一种线性排序，它的时间复杂度是 $O(n)$

💡 思路：

• 将所有元素统一为同样的数位长度，数位较短的数前面补零；
• 从最低位开始，依次进行排序；
• 从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列；

🌰 如果我们想给 10 万个手机号码排序，因为手机号有 11 位，范围太大，不适合计数排序和桶排序。通过基数排序，我们先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过 11 次排序之后，手机号码就都有序了。

# 基数排序时间复杂度分析

根据数字的每一位来排序，可以用桶排序或者计数排序，它们的时间复杂度可以做到 $O(n)$。如果要排序的数据有 $k$ 位，那我们就需要 $k$ 次桶排序或者计数排序，总的时间复杂度是 $O(k*n)$。