排序算法 - 选择、冒泡、插入、快排、希尔、归并、堆
2019-02-23
[算法]
更新日志
2021-06-11
更新分类、标签
在编码过程中肯定少不了对数据进行排序，通常做法是使用标准库的实现、使用熟悉的排序算法或直接网上扒一个排序算法，然而却对排序算法的特点和适应场景了解得非常少。本文将从代码实现和不同量级数据的测试两个角度来说说各个排序算法。
选择排序
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 《选择排序 - Wikipedia》
主要逻辑: 找到数组中最值（小、大）的数，依次交换位置
实现
public static void sort(Comparable[] arr) {
if (arr != null && arr.length > 1) {
for (int i = 0; i < arr.length; i++) {
// 记录下当前遍历的最小值
int minIndex = i;
// 依次从当前元素向后比较，如果有比该元素小的值，则更新最小值的索引
for (int j = i + 1; j < arr.length; j++) {
// 如果当前元素比后面的某一个元素大，则当前元素不是最小值，记录下目前找到的最小值
if (arr[minIndex].compareTo(arr[j]) > 0) {
minIndex = j;
}
}
// 如果minIndex发生了变化，代表当前元素不是最小的，则交换当前元素和minIndex所在值的位置
if (i != minIndex) {
Comparable temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
}
冒泡排序
冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。《冒泡排序》- Wikipedia
实现
public static void sort(Comparable[] arr) {
if (arr != null && arr.length > 0) {
// 依次比较每一个元素
for (int i = 0; i < arr.length; i++) {
// 依次比较当前元素后面的每一个元素
for (int j = i + 1; j < arr.length; j++) {
// 如果当前元素大于后面的元素，则交换位置
if (arr[i].compareTo(arr[j]) > 0) {
Comparable temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
}
插入排序
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（原地排序：即只需用到$O(1)$的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
版本1
每次都与前面的所有元素比较，遇到比当前元素大的元素就交换双方位置，直到找到第一个元素
public static void sort(Comparable[] arr) {
if (arr != null && arr.length > 0) {
// 因为默认第一个元素（下标为0的元素）是已经排序的，所以直接从第二个元素（下标为1的元素）开始进行比较
for (int i = 1; i < arr.length; i++) {
// 当前元素与已经排序的元素（前面的元素）进行比较，如果当前元素小于前面的元素，则交换两个元素的位置
// 因为交换了位置，此时 j-1 的值依旧等于原来j的值，
// 所以内层遍历一直都是在用j的值进行比较，只是在比较过程中，下标变化了
// 只有在j的值比前一个值小的时候，才会进行多次循环比较，否则只是一个if判断的作用
for (int j = i; j > 0 && arr[j].compareTo(arr[j - 1]) < 0; j--) {
Comparable temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
}
版本2
该版本算是比较有意思的一种，主要做两件事：
- 将比当前元素大的元素全部往后移
- 找到该元素符合的位置
public static void sort(Comparable[] arr) {
int j;
// 每次实际的比较元素
Comparable temp;
for (int i = 1; i < arr.length; i++) {
// 数组中的每一个元素
temp = arr[i];
// 使用当前元素（下标i的元素）与前一个元素（下标j-1的元素）进行比较
// 如果当前元素小于前一个元素，那么将前一个元素往后移一位（也就是放到当前元素现处的位置上）
// 继续遍历前面的元素，如果比前一个元素小，重复上一步操作（也就是说，只要比当前元素大的元素，都将往后移）。
// 如果当前元素大于等于前一个元素，代表该元素已经找到合适的位置了，
// 那么循环的条件不成立，执行 arr[j] = temp 设置当前元素到合适的索引
for (j = i; j > 0 && temp.compareTo(arr[j - 1]) < 0; j--) {
// 将比当前元素小的元素向后移
arr[j] = arr[j - 1];
}
arr[j] = temp;
}
}
希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
希尔排序的实现是将一个数组以递减长度（步长）来分为多个子数组，对这多个子数组进行插入排序。当步长为1时，该数据已经大致保持顺序了，只需要较少得调整顺序就能保持有序。
实际上，可以把希尔排序理解为在插入排序的外层再套了一个实现递减步长的循环。
在希尔排序中最重要的部分就是确定步长值，步长值将影响算法执行的时间。步长值每次的变化形成了一个步长序列，例如步长定义为n/2，则步长序列为[ n/2, (n/2)/2, ((n/2)/2)/2 ]。步长序列的相关定义和说明可以看《希尔排序 - 步长序列》- Wikipedia
实现
/**
* 希尔排序 - 版本1
* 版本说明：每次都对比较的两个元素交互位置
*
* @param arr 需要排序的数组
*/
public static void sort(Comparable[] arr) {
if (arr != null && arr.length > 1) {
// 定义步长值为41
int step = 41;
// 每次循环递减步长值
for (int len = arr.length / step; len > 0; len /= step) {
// 对通过步长值计算出来的子数组进行插入排序
for (int i = len; i < arr.length; i++) {
for (int j = i; j > 0 && arr[j].compareTo(arr[j - 1]) < 0; j--) {
Comparable temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
}
}
/**
* 希尔排序 - 版本2
* 版本说明：比较时，将较大的值一直往前移，减少交换次数
*
* @param arr 需要排序的数组
*/
public static void sort1(Comparable[] arr) {
if (arr != null && arr.length > 1) {
int step = 41;
int j;
for (int len = arr.length / step; len > 0; len /= step) {
for (int i = len; i < arr.length; i++) {
Comparable temp = arr[i];
for (j = i; j > 0 && arr[j].compareTo(arr[j - 1]) < 0; j--) {
arr[j - 1] = arr[j];
}
arr[j] = temp;
}
}
}
}
快速排序
快速排序采用分支法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：
- 从数列中挑出一个元素，称为“基准”（pivot）。
- 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为**分割（partition）**操作。
- **递归地（recursively）**把小于基准值元素的子数列和大于基准值元素的子数列排序。
快速排序有三个核心，分别是：
- 找基准
- 从基准分割
- 递归处理分割的子序列
实现
/**
* 快速排序
*
* @param arr 要排序的数据
* @param head 前部分的索引值，初次传入应该为0
* @param tail 后部分的索引值，初次传入应该为arr.length
*/
public static void sort(Comparable[] arr, int head, int tail) {
// 判断执行后续步骤的先决条件。
// 其中判断条件并不是随意写的：因为该方法是一个递归方法，所以 head >= tail 放到前面是一个优化措施
if (head >= tail || arr == null || arr.length <= 1) {
return;
}
// 用i,j分别记录head和tail的值，因为后面需要继续使用传入的head和tail，所以要有个备份
int i = head, j = tail;
// 选出本次排序需要的基准（中间值）：pivot，计算方式为 (head + tail)/2
Comparable pivot = arr[(head + tail) / 2];
// 如果i <= j，表示还有子序列没有被排序，因为还存在 j - i 个元素没有被排序
while (i <= j) {
// 如果索引i的元素小于选出来的基准，那么表示应该继续使用后面的值与基准比较
// 直到找到 >= 基准的值
while (arr[i].compareTo(pivot) < 0) {
++i;
}
// 如果索引j的元素还大于选出来的基准，那么表示应该继续使用前面的值与基准比较
// 直到直到 <= 基准的值
while (arr[j].compareTo(pivot) > 0) {
--j;
}
// 走到这里，代表i，j的索引已经是 >= 基准的值和 <= 基准的值
// 既然i，j都找到了符合条件的值，那么这个情况下，只有两种可能：
// 1. i < j 表示i对应的值（>=基准的值）在基准的后面，j对应的值（<=基准的值）在基准的前面
// 那么交换i和j元素的位置，并向后移动i，向前移动j
// 2. i == j 表示i和j对应的索引是一致的，都等于 (head + tail) / 2，也就是找到了基准自己
// 那么i往后移动一位，表示使外层while条件不成立，跳出循环，接下来处理两个子序列
if (i < j) {
Comparable temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
++i;
--j;
} else if (i == j) {
++i;
}
}
// 递归部分，处理以本次确定i，j拆分的前后两个子序列
// 处理head -> j的子序列
sort(arr, head, j);
// 处理i-> tail的子序列
sort(arr, i, tail);
}
归并排序
归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为 $O(n log n)$ 。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
采用分治法:
- 分割（分）：递归地把当前序列平均分割成两半。
- 集成（治）：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。
实现
/**
* 归并排序
*
* @param arr 要排序的数据
*/
public static void sort(Comparable[] arr) {
// 创建一个临时数组，长度为目标数组的长度（因为最后的一次排序+合并会将所有数据暂存在该数据，所以需要以最大的长度来创建）
Comparable[] temp = new Comparable[arr.length];
sort(arr, 0, arr.length - 1, temp);
}
/**
* 归并排序
* 支持递归部分，不对外提供访问
*
* @param arr 要排序的数组
* @param head 分割为子数组的起始索引
* @param tail 分割为子数组的结束索引
* @param temp 临时数组，用于存储子数组排序后的结果
*/
private static void sort(Comparable[] arr, int head, int tail, Comparable[] temp) {
if (head < tail) {
// 从中间分割：基准
int pivot = (head + tail) / 2;
// 递归：对分割的前部分进行分割并排序
sort(arr, head, pivot, temp);
// 对分割的后部分进行分割并排序
sort(arr, pivot + 1, tail, temp);
// 排序并合并两个数组
merge(arr, head, tail, pivot, temp);
}
}
/**
* 主要的排序+合并逻辑
*
* @param arr 原始数组
* @param head 分割为子数组的起始索引
* @param tail 分割为子数组的结束索引
* @param pivot 每次确定下来的基准索引
* @param temp 临时数组，用于存储子数组排序后的结果
*/
private static void merge(Comparable[] arr, int head, int tail, int pivot, Comparable[] temp) {
// i 表示基准左边数组的起始下标，左边数组最后一个元素的索引是pivot
// j 表示基准右边数组的起始下标（也就是基准的下标+1)，右边数组最后一个元素的索引是tail
// ti 表示在临时数组中的索引
int i = head, j = pivot + 1, ti = 0;
// 将左边与右边的所有值进行遍历
while (i <= pivot && j <= tail) {
// 判断左右两边元素的大小，把小的元素放入临时数据中
// 并且需要自增双方的索引（自增ti表示下个元素放入到后面，自增i/j表示开始计算下一个元素）
if (arr[i].compareTo(arr[j]) < 0) {
temp[ti++] = arr[i++];
} else {
temp[ti++] = arr[j++];
}
// 将左边剩余的元素依次添加到临时数组的后面
while (i <= pivot) {
temp[ti++] = arr[i++];
}
// 将右边剩余的元素依次添加到临时数组的后面
while (j <= tail) {
temp[ti++] = arr[j++];
}
// 此时，temp中元素是左边和右边元素的有序排列
// 则需要将temp排列好的元素放回原数组中
// ti已经使用完毕，可以将ti重置为0，后面使用ti的索引变化来取对应临时数组中的元素
// head 和 tail 对应着原数组中的左右两个子数组的起始和结束索引
ti = 0;
// 将head -> tail的所有元素覆盖为排序好的元素
while (head <= tail) {
arr[head++] = temp[ti++];
}
}
}
堆排序
堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。 堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。 通常堆是通过一维数组来实现的。 《堆排序》- Wikipedia
在数组起始位置为0的情形中，父子节点的关系如下：
- 父节点i的左子节点在位置: $(2i+1)$
- 父节点i的右子节点在位置: $(2i+2)$
- 子节点i的父节点在位置: $floor((i-1)/2)$
- 最后一个非叶子节点在位置: $(n / 2 - 1)$
堆排序的基本思想是《图解排序算法(三)之堆排序》- dreamcatcher-cx ：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
/**
* 堆排序
*
* @param arr 需要排序的数据
*/
public static void sort(Comparable[] arr) {
// 从当前堆中取出最后一个非叶子节点，从下往上构建一个大顶堆
for (int i = arr.length / 2 - 1; i > 0; i--) {
buildMaxHeap(arr, i, arr.length);
}
// 初次构建完大顶堆之后，交换堆顶和最后一个叶子节点的值，也就是将最大的值放到后面
// 交换完成后，继续使用剩余节点构建一个大顶堆并再次交换
for (int i = arr.length - 1; i > 0; i--) {
Comparable temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
buildMaxHeap(arr, 0, i);
}
}
/**
* 构建一个大顶堆
*
* @param arr 数据
* @param i 当前的父节点
* @param len 构建的元素范围
*/
private static void buildMaxHeap(Comparable[] arr, int i, int len) {
// 循环从传入节点的左子节点开始：int j = 2 * i + 1;（取出i的左子节点）
// 循环后，以左子节点为父节点继续往下处理：j = 2 * j + 1;（取出j的左子节点）
for (int j = 2 * i + 1; j < len; j = 2 * j + 1) {
// 找出大的子节点
// 如果右节点大于左节点，则将右节点索引记录下来
if (j + 1 < len && arr[j].compareTo(arr[j + 1]) < 0) {
j++;
}
// 使用大的子节点与父节点比较，如果子节点大于父节点，则交换位置
if (arr[j].compareTo(arr[i]) > 0) {
Comparable temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
} else {
// 因为是从下向上进行交换位置的，如果父节点大于子节点，那么表示该节点和该节点的所有子孙节点已经构成了一个大顶堆
break;
}
}
}
测试
测试说明
- 使用Java随机数(0-999999999)生成的测试数据
- 每个数据量级都对所有算法测试一遍
- 只测试了不同量级各个排序算法的耗时
- 运行在4核8G服务器上（GCP）
- 本想测试到500W数据的，但部分算法耗时太长，所以只测试到50W
- 由于冒泡排序太耗时，数据量 > 10W 则直接跳过冒泡排序
参考资料
希尔排序
归并排序
堆排序