简介
本文实现以下七种排序算法：
插入排序
选择排序
冒泡排序
希尔排序
堆排序
快速排序
归并排序
使用 C++ 完成，并测试运行时间。
算法说明
以下针对每种算法，从网络摘取简介，并附实现代码。
所有实现以对 int 数组排序，目标为从小到大为例。感兴趣的读者可以自行编写更通用的写法。
插入排序
插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
void insertSort(int* first, int* last) {
for (int* p = first + 1; p < last; p++) {
int* curr = p;
for (int* q = p - 1; q >= first; q--) {
if (*q > *curr) {
swap(*q, *curr);
curr--;
}
else {
break;
}
}
}
}
选择排序
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
void selectSort(int* first, int* last) {
for (int* p = first; p < last; p++) {
int* tar = p;
for (int* q = p + 1; q < last; q++) {
if (*q < *tar) {
tar = q;
}
}
swap(*tar, *p);
}
}
冒泡排序
重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
void bubbleSort(int* first, int* last) {
for (int* i = first; i < last; i++) {
for (int* j = i; j < last; j++) {
if (*i > *j) {
swap(*i, *j);
}
}
}
}
希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
void shellSort(int* first, int* last) {
int step = last - first;
int*& arr = first;
while (step > 1) {
step /= 2;
for (int i = 0; i < step; i++) {
for (int j = i + step; j < last - first; j += step) {
for (int k = j - step; k >= 0; k -= step) {
if (arr [k] > arr [k + step]) {
swap(arr [k], arr [k + step]);
}
else {
break;
}
}
}
}
}
}
堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。
void heapSort(int* first, int* last) {
int*& arr = first;
int len = last - first;
auto lc = [](int x) { return 2 * x + 1; };
auto rc = [](int x) { return 2 * x + 2; };
auto adjust = [&](int tar, int borderIdx) {
int curIdx = tar;
while (true) {
int curMaxIdx = curIdx;
if (lc(curIdx) < borderIdx && arr[lc(curIdx)] > arr[curMaxIdx]) {
curMaxIdx = lc(curIdx);
}
if (rc(curIdx) < borderIdx && arr[rc(curIdx)] > arr[curMaxIdx]) {
curMaxIdx = rc(curIdx);
}
if (curMaxIdx != curIdx) {
swap(arr[curIdx], arr[curMaxIdx]);
curIdx = curMaxIdx;
}
else {
break;
}
}
};
for (int i = len / 2 - 1; i >= 0; i--) {
adjust(i, len);
}
for (int i = len - 1; i > 0; i--) {
swap(arr[0], arr[i]);
adjust(0, i);
}
}
快速排序
在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
注意：不可使用递归形式完成。否则当数据量较大的时候，会导致栈溢出。
void quickSort(int* first, int* last) {
vector<pair<int*, int*>> q;
q.push_back(make_pair(first, last));
while (!q.empty()) {
pair<int*, int*> currPair = q.back();
q.pop_back();
int* currFirst = currPair.first;
int* currLast = currPair.second;
if (currFirst + 1 >= last) {
return;
}
int* lp = currFirst;
int* rp = currLast - 1;
while (lp < rp) {
while (lp < rp && *lp <= *rp) { // 右边界收缩。
rp--;
}
swap(*lp, *rp);
while (lp < rp && *lp <= *rp) { // 左边界收缩。
lp++;
}
swap(*lp, *rp);
}
if (lp - 1 > currFirst) {
q.push_back(make_pair(currFirst, lp));
}
if (rp + 1 < currLast - 1) {
q.push_back(make_pair(rp + 1, currLast));
}
}
}
归并排序
归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
void mergeSort(int* first, int* last) {
// 迭代法。
int* arrA = first;
int size = last - first;
int* arrB = new int[size];
int* currSource = arrA;
int* currTarget = arrB;
for (int seqLen = 1; seqLen < size; seqLen *= 2) {
for (int i = 0; i < size; i += seqLen * 2) {
if (i + seqLen >= size) {
memcpy(currTarget + i, currSource + i, (size - i) * sizeof(int));
break;
}
int crA = i;
int crB = i + seqLen;
int tailA = i + seqLen;
int tailB = min(i + 2 * seqLen, size);
for (int j = i; j < i + 2 * seqLen && j < size; j++) {
if (crA == tailA) {
currTarget[j] = currSource[crB];
crB += 1;
}
else if (crB == tailB) {
currTarget[j] = currSource[crA];
crA += 1;
}
else if (currSource[crA] < currSource[crB]) {
currTarget[j] = currSource[crA];
crA += 1;
}
else {
currTarget[j] = currSource[crB];
crB += 1;
}
}
}
swap(currSource, currTarget);
}
if (currSource == arrB) {
memcpy(arrA, arrB, size * sizeof(int));
}
delete[] arrB;
}
包装
为方便测试，对程序加入命令行选择能力，并加入计时和结果检查。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <chrono>
#include <string>
#include <cmath>
#include <vector>
#include <conio.h>
using namespace std;
#undef swap
#undef sort
int getTimeMillisec() {
return chrono::duration_cast<chrono::milliseconds>
(chrono::system_clock::now().time_since_epoch()).count();
}
void swap(int& a, int& b) {
int t = a;
a = b;
b = t;
}
void bubbleSort(int* first, int* last) {...}
void quickSort(int* first, int* last) {...}
void selectSort(int* first, int* last) {...}
void insertSort(int* first, int* last) {...}
void mergeSort(int* first, int* last) {...}
void shellSort(int* first, int* last) {...}
void heapSort(int* first, int* last) {...}
enum class Algo {
QUICK, BUBBLE, SELECT, MERGE, INSERT, SHELL, HEAP
};
int sort(int* first, int* last, Algo algo = Algo::QUICK) {
auto beg = getTimeMillisec();
if (algo == Algo::QUICK) {
quickSort(first, last);
} else if (algo == Algo::BUBBLE) {
bubbleSort(first, last);
} else if (algo == Algo::SELECT) {
selectSort(first, last);
} else if (algo == Algo::MERGE) {
mergeSort(first, last);
} else if (algo == Algo::INSERT) {
insertSort(first, last);
} else if (algo == Algo::SHELL) {
shellSort(first, last);
} else if (algo == Algo::HEAP) {
heapSort(first, last);
}
auto now = getTimeMillisec();
return now - beg;
}
int main(int argc, const char* argv[]) {
ios::sync_with_stdio(false);
srand(time(0));
string algoStr = "quick";
if (argc >= 2) {
algoStr = argv[1];
} else {
cout << "Usage: [Algorithm] [optional: qsop]" << endl;
cout << endl;
cout << "Available algorithms are:" << endl;
cout << " quick, bubble, merge, heap, insert, shell, select." << endl;
cout << endl;
cout << "if quicksort-optimization is required, add \"qsop\" to the arguments." << endl;
cout << endl;
cout << "Example:" << endl;
cout << argv[0] << " quick op : optimized quick sort." << endl;
return 0;
}
bool isOpRequired = false;
if (argc >= 3 && strcmp(argv[2], "qsop") == 0) {
isOpRequired = true;
}
Algo algo = Algo::QUICK;
if (algoStr == "quick") {
algo = Algo::QUICK;
cout << "algo set: quick sort." << endl;
} else if (algoStr == "bubble") {
algo = Algo::BUBBLE;
cout << "algo set: bubble sort." << endl;
} else if (algoStr == "merge") {
algo = Algo::MERGE;
cout << "algo set: merge sort." << endl;
} else if (algoStr == "heap") {
algo = Algo::HEAP;
cout << "algo set: heap sort." << endl;
} else if (algoStr == "insert") {
algo = Algo::INSERT;
cout << "algo set: insert sort." << endl;
} else if (algoStr == "shell") {
algo = Algo::SHELL;
cout << "algo set: shell sort." << endl;
} else if (algoStr == "select") {
algo = Algo::SELECT;
cout << "algo set: select sort." << endl;
}
int n;
cin >> n;
int* arr = new int[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
if (isOpRequired) {
// 随机打乱
for (int i = 0; i < n / 33; i++) {
swap(arr[rand() % n], arr[rand() % n]);
}
}
time_t timeUsage = sort(arr, arr + n, algo);
for (int i = 0; i < n; i++) {
if (i < 6 || n - i < 6) {
cout << arr[i] << ' ';
}
else if (i == 10) {
cout << "... ";
}
if (i > 0 && arr[i - 1] > arr[i]) {
cout << endl;
cout << "Seq Error: at arr[" << i << "]." << endl;
cout << "exit? [y/n]: ";
while (true) {
char c = _getch();
if (c == 'Y' || c == 'y') {
cout << c << endl;
i = n; // break the outer loop.
break;
} else if (c == 'N' || c == 'n') {
cout << c << endl;
break;
}
}
}
}
cout << endl;
cout << "time usage: " << timeUsage << " ms." << endl;
delete[] arr;
return 0;
}
测试文件生成程序
使用简短的 Kotlin 程序生成测试文件。通过命令行方式控制生成数据的规模等。
随机
import java.io.File
fun main(args: Array<String>) {
if (args.size < 2) {
println("Usage: [data size] [outfile dir]")
println("Example: name 1000 ./out1000.txt")
return
}
val s = args[0].toInt()
val file = File(args[1])
file.printWriter().use { out ->
out.println(s)
for (i in 0 until s) {
out.print("${(0..s).random()} ")
}
out.println()
}
}
有序
import java.io.File
enum class Order {
ASC, DES
}
fun main(args: Array<String>) {
if (args.size < 2) {
println("Usage: [order: \"ass\" or \"rev\"] [outfile] [optional: data size]")
return
}
val size = if (args.size >= 3) args[2].toInt() else 10000
val order = if (args[0].lowercase() == "des") Order.DES else Order.ASC
val file = File(args[1])
file.printWriter().use { out ->
out.println(size)
var curr = if (order == Order.ASC) 0 else size
for (i in 0 until size) {
out.print("$curr ")
if ((0..100).random() < 70) {
curr += if (order == Order.ASC) 1 else -1
}
}
out.println()
}
}
测试结果
测试分别运行于笔记本电脑和 arm64 服务器。采用自动测试并输出结果的模式，各完成64种组合的排序并计时。
最终，得到以下测试结果。
其中，快速排序（优化）在快速排序的基础上，随机打乱 3% 的数据，从而避免极端情况使快速排序算法复杂度退化。
计时单位：毫秒 (ms)
笔记本
| 插入 | 选择 | 冒泡 | 希尔 | 堆 | 快速 | 快速（优化） | 归并 | |
|---|---|---|---|---|---|---|---|---|
| 10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 100 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1K | 0 | 1 | 2 | 0 | 0 | 0 | 0 | 0 |
| 10K | 30 | 75 | 105 | 1 | 0 | 1 | 0 | 1 |
| 100K | 2811 | 7613 | 10950 | 9 | 7 | 5 | 6 | 6 |
| 1M | 279138 (279s) | 783016 (13min) | 1226214 (20min) | 150 | 103 | 64 | 69 | 79 |
| 10K 正序 | 0 | 79 | 11 | 0 | 0 | 11 | 1 | 0 |
| 10K 逆序 | 56 | 81 | 35 | 0 | 1 | 11 | 0 | 0 |
服务器
| 插入 | 选择 | 冒泡 | 希尔 | 堆 | 快速 | 快速（优化） | 归并 | |
|---|---|---|---|---|---|---|---|---|
| 10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 100 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1K | 1 | 2 | 5 | 0 | 0 | 0 | 0 | 1 |
| 10K | 150 | 187 | 434 | 3 | 3 | 2 | 3 | 1 |
| 100K | 15163 | 18739 | 43051 | 46 | 46 | 25 | 25 | 20 |
| 1M | 1579726 (26min) | 1904198 (32min) | 4480618 (75min) | 738 | 630 | 290 | 286 | 243 |
| 10K 正序 | 0 | 186 | 186 | 1 | 3 | 162 | 7 | 0 |
| 10K 逆序 | 298 | 254 | 526 | 1 | 3 | 175 | 4 | 1 |
排序算法比较
下表为各种排序算法的性能指标。
| 排序算法 | 时间复杂度（平均） | 时间复杂度（最坏） | 空间复杂度 | 稳定 | 备注 |
|---|---|---|---|---|---|
| 插入 | O(n2) | O(n2) | O(1) | 是 | |
| 希尔 | O(n1.3) | O(n2) | O(1) | 否 | |
| 选择 | O(n2) | O(n2) | O(1) | 否 | |
| 堆 | O(nlogn) | O(nlogn) | O(1) | 否 | |
| 冒泡 | O(n2) | O(n2) | O(1) | 是 | |
| 快速 | O(nlogn) | O(n2) | O(nlogn) | 否 | 数列有序时，快速排序严重退化 |
| 快速（优化） | O(nlogn) | O(nlogn) | O(1) | 否 | 排序前随机打乱数列 |
| 归并 | O(nlogn) | O(nlogn) | O(n) | 是 | 需要一个辅助数组 |
从前方实验中可以看出，O(n2) 的复杂度在数据量较大的时候耗时严重。
当数列有序时，快速排序和冒泡的效率几乎一致。将数列进行小幅度随机打乱可以规避此问题。
优缺点分析
| 算法 | 优点 | 缺点 |
|---|---|---|
| 插入 | 无额外内存开销。稳定。 | 效率低下。 |
| 希尔 | 比选择效率高。无额外内存开销。 | 效率依旧低下。 |
| 选择 | 无额外内存开销。 | 效率低下。 |
| 堆 | 效率高。无额外内存开销。 | |
| 冒泡 | 稳定。 | 数据移动次数过多。效率低下。 |
| 快速 | 时间复杂度低。 | 计算过程空间复杂度较高。不稳定。数列有序时，效率退化。 |
| 快速（优化） | 不论数列是否有序，都有较高效率。 | 计算过程空间复杂度较高。不稳定。 |
| 归并 | 效率高。额外空间开销较小。 | 存在额外空间开销。 |
数据生成环境
软件
Kotlinc: 1.6.10 (JRE 17.0.1+12)
Java: 17 (64 bit)
测试环境：笔记本电脑
硬件
CPU型号：i7-11370H
内存频率：LPDDR4X 4266MHz
软件
操作系统：Windows 11 Pro 21H1 (22000.527) x86_64
C++编译器：MSVC v143 （以 release x64 模式编译）
测试环境：服务器
硬件
CPU: 鲲鹏920 arm64 2.6GHz
软件
操作系统：Ubuntu 20.04 focal (aarch64 Linux 5.4.0-100-generic)
C++编译器：gcc 9.3.0
