解码数据有序之道——常见排序算法总结

本文整理了常见的排序算法，采用c++编码，并对其时间复杂度作以了分析。

1. 冒泡排序（Bubble Sort）

实现思路：

• 从数组的第一个元素开始，依次比较相邻的两个元素。
• 如果当前元素大于下一个元素，则交换它们的位置。
• 经过一轮比较，最大的元素会“浮”到数组的末尾。
• 重复这个过程，每一轮都把未排序部分的最大元素移到正确位置，总共需要进行 n - 1 轮（n 为数组元素个数）。

代码实现：

#include <iostream>
#include <vector>
using namespace std;void bubbleSort(vector<int>& arr) {int n = arr.size();for (int i = 0; i < n - 1; ++i) {for (int j = 0; j < n - i - 1; ++j) {if (arr[j] > arr[j + 1]) {swap(arr[j], arr[j + 1]);}}}
}

时间复杂度：

• 最好情况：数组已经有序，只需进行一轮比较，没有元素交换，时间复杂度为 $O(n)$。
• 最坏情况：数组完全逆序，需要进行 n - 1 轮比较，每轮比较 n - i - 1 次（i 为当前轮数），时间复杂度为 $O(n^2)$。
• 平均情况：时间复杂度也是 $O(n^2)$。

2. 选择排序（Selection Sort）

实现思路：

• 首先在未排序的序列中找到最小（大）元素，存放到排序序列的起始位置。
• 然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。
• 重复这个过程，直到所有元素均排序完毕，一共需要进行 n - 1 次选择操作（n 为数组元素个数）。

代码实现：

#include <iostream>
#include <vector>
using namespace std;void selectionSort(vector<int>& arr) {int n = arr.size();for (int i = 0; i < n - 1; ++i) {int minIndex = i;for (int j = i + 1; j < n; ++j) {if (arr[j] < arr[minIndex]) {minIndex = j;}}swap(arr[i], arr[minIndex]);}
}

时间复杂度：

• 无论数组初始状态如何，都需要进行 n - 1 轮选择操作，每轮都要遍历剩余未排序元素，所以最好、最坏、平均情况的时间复杂度都是 $O(n^2)$。

3. 插入排序（Insertion Sort）

实现思路：

• 将数组分为已排序和未排序两部分，初始时已排序部分只有第一个元素。
• 取未排序部分的第一个元素，将其插入到已排序部分的合适位置，使得已排序部分依然有序。
• 重复这个过程，直到未排序部分为空。

代码实现：

#include <iostream>
#include <vector>
using namespace std;void insertionSort(vector<int>& arr) {int n = arr.size();for (int i = 1; i < n; ++i) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}

时间复杂度：

• 最好情况：数组已经有序，每次插入操作只需比较一次，时间复杂度为 $O(n)$。
• 最坏情况：数组完全逆序，每次插入都要和已排序部分的所有元素比较并移动，时间复杂度为 $O(n^2)$。
• 平均情况：时间复杂度为 $O(n^2)$。

4.希尔排序（Shell Sort）

实现思路

• 希尔排序是对插入排序的改进，它的基本思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序。
• 首先选择一个合适的间隔（称为“步长”或“增量”，通常初始化为数组长度的一半，然后每次缩小一半，直到步长为1）。
• 按照选定的步长，对相隔该步长的元素组成的子序列进行插入排序，例如步长为 gap 时，会把数组分成多个子序列，分别是 arr[0], arr[gap], arr[2 * gap],... 、arr[1], arr[1 + gap], arr[1 + 2 * gap],... 等这些子序列，对每个子序列进行插入排序操作。
• 随着步长逐渐减小，子序列的元素个数逐渐增多，当步长最终减为1时，整个数组就相当于进行了一次普通的插入排序，但此时由于前面以较大步长进行了预排序，元素已经相对更接近最终位置，所以最后一次插入排序会比直接对原始数组进行插入排序效率更高。

代码实现

#include <iostream>
#include <vector>
using namespace std;void shellSort(vector<int>& arr) {int n = arr.size();for (int gap = n / 2; gap > 0; gap /= 2) {for (int i = gap; i < n; i++) {int temp = arr[i];int j;for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}
}

时间复杂度

• 希尔排序的时间复杂度与所选取的步长序列有关，它的时间复杂度分析比较复杂。
• 最好情况：当数组已经有序时，时间复杂度接近 $O(n)$，因为每个子序列在插入排序时几乎不需要移动元素。
• 最坏情况：时间复杂度依赖于步长序列，不同的步长序列会导致不同的最坏情况时间复杂度，不过通常认为其最坏情况时间复杂度在 $O(n^2)$ 左右，例如使用 Hibbard 序列作为步长时最坏情况为 $O(n^{3/2})$ 等。
• 平均情况：平均时间复杂度介于 $O(n)$ 和 $O(n^2)$ 之间，常见的分析结果大约是 $O(n^{1.3})$ 左右。

5. 快速排序（Quick Sort）

实现思路：

• 选择一个基准元素（通常是数组的最后一个元素）。
• 通过一趟排序将数组分为两部分，左边部分的元素都小于等于基准元素，右边部分的元素都大于基准元素。
• 对左右两部分分别递归地进行快速排序，直到子数组的长度为1或者0。

代码实现：

#include <iostream>
#include <vector>
using namespace std;int partition(vector<int>& arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; ++j) {if (arr[j] <= pivot) {++i;swap(arr[i], arr[j]);}}swap(arr[i + 1], arr[high]);return i + 1;
}void quickSort(vector<int>& arr, int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}

时间复杂度：

• 最好情况：每次划分都能把数组均匀地分成两部分，时间复杂度为 $O(n\log n)$。
• 最坏情况：数组已经有序或者逆序，每次划分只得到一个元素和剩余元素的子数组，时间复杂度为 $O(n^2)$。
• 平均情况：时间复杂度为 $O(n\log n)$。

6. 归并排序（Merge Sort）

实现思路：

• 采用分治思想，先将数组不断地分成两半，直到每个子数组只有一个元素（这是递归分解的过程）。
• 然后将相邻的子数组合并成有序的数组，合并时比较两个子数组的元素，依次放入新的临时数组中，再将临时数组的元素复制回原数组对应位置（这是合并的过程）。
• 重复合并过程，直到整个数组有序。

代码实现：

#include <iostream>
#include <vector>
using namespace std;void merge(vector<int>& arr, int l, int m, int r) {int n1 = m - l + 1;int n2 = r - m;vector<int> L(n1), R(n2);for (int i = 0; i < n1; ++i) {L[i] = arr[l + i];}for (int j = 0; j < n2; ++j) {R[j] = arr[m + 1 + j];}int i = 0, j = 0, k = l;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k++] = L[i++];} else {arr[k++] = R[j++];}}while (i < n1) {arr[k++] = L[i++];}while (j < n2) {arr[k++] = R[j++];}
}void mergeSort(vector<int>& arr, int l, int r) {if (l < r) {int m = l + (r - l) / 2;mergeSort(arr, l, m);mergeSort(arr, m + 1, r);merge(arr, l, m, r);}
}

时间复杂度：

• 无论数组初始状态如何，每次划分都是 $O(1)$ 的时间复杂度，合并操作总的时间复杂度为 $O(n)$，一共要进行 $\log n$ 层划分与合并，所以时间复杂度始终为 $O(n\log n)$。

7. 堆排序（Heap Sort）

实现思路：

• 首先将数组构建成一个最大堆（从最后一个非叶子节点开始，对每个节点进行堆化操作，保证父节点大于等于子节点）。
• 然后把堆顶元素（最大值）与堆的最后一个元素交换，此时最大值就在正确的排序位置了，接着对剩下的元素重新进行堆化，使其再次成为最大堆。
• 重复这个过程，直到整个数组有序。

代码实现：

#include <iostream>
#include <vector>
using namespace std;void heapify(vector<int>& arr, int n, int i) {int largest = i;int l = 2 * i + 1;int r = 2 * i + 2;if (l < n && arr[l] > arr[largest]) {largest = l;}if (r < n && arr[r] > arr[largest]) {largest = r;}if (largest!= i) {swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}void heapSort(vector<int>& arr) {int n = arr.size();for (int i = n / 2 - 1; i >= 0; --i) {heapify(arr, n, i);}for (int i = n - 1; i > 0; --i) {swap(arr[0], arr[i]);heapify(arr, i, 0);}
}

时间复杂度：

• 建堆过程时间复杂度为 $O(n)$，每次调整堆的时间复杂度为 $O(\log n)$，总共需要进行 n - 1 次调整堆操作，所以时间复杂度为 $O(n\log n)$。

8.基数排序

实现思路

1. 基数计数与分配
   • 基数排序的核心思想是根据数字的每一位来进行排序。对于一个整数数组，首先确定数字的最大位数(d)（例如对于十进制数，最大位数可能是数组中最大数的位数）。
   • 从最低位（个位）开始，依次对每一位进行排序。对于每一位，创建(r)个桶（对于十进制数(r = 10)，即0 - 9号桶）。
   • 遍历数组中的每个元素，根据当前位的数字值将元素放入相应的桶中。例如，如果当前位是个位，数字(123)的个位是(3)，则将(123)放入(3)号桶中。
2. 收集与重复
   • 按照桶的顺序（从(0)号桶到(r - 1)号桶）依次收集元素，将桶中的元素放回原数组，此时原数组就按照当前位进行了排序。
   • 然后处理下一位，重复上述分配和收集的过程，直到处理完最高位。这样，经过(d)轮处理后，数组就完成了排序。

时间复杂度

1. 平均情况
   • 时间复杂度为(O(d(r + n)))，其中(d)是数字的最大位数，(r)是基数（例如十进制数(r = 10)），(n)是待排序元素的个数。
   • 分析如下：对于每一位（共(d)位），需要遍历(n)个元素来分配到®个桶中，这一步的时间复杂度是(O(n))。然后需要遍历®个桶来收集元素，时间复杂度是(O®)。所以每一位的处理时间复杂度是(O(n + r))，总共(d)位，所以平均时间复杂度是(O(d(n + r)))。
2. 最好情况
   • 当所有元素的位数都相同时，时间复杂度为(O(d(n + r)))，这与平均情况相同。因为即使元素已经有序，基数排序仍然需要按照每一位进行处理。
3. 最坏情况
   • 时间复杂度为(O(d(n + r^{d)))。这种情况可能发生在所有元素的最高位都不同，并且每一位的取值范围很大（接近(r)）。在这种情况下，对于每一位，都需要处理所有的桶，而桶的数量最多可以达到(r}d)（例如，当所有元素的每一位都不同时）。

代码实现（对十进制整数数组进行排序）

#include <iostream>
#include <vector>
#include <algorithm>// 基数排序函数
void radixSort(std::vector<int>& arr) {// 找到数组中的最大值，确定最大位数int maxVal = *std::max_element(arr.begin(), arr.end());for (int exp = 1; maxVal / exp > 0; exp *= 10) {// 创建计数数组，用于统计每个桶中的元素个数std::vector<int> count(10, 0);// 计算每个元素在当前位上的数字，统计每个桶中的元素个数for (int i = 0; i < arr.size(); i++) {count[(arr[i] / exp) % 10]++;}// 计算计数数组的前缀和，确定每个桶中元素在输出数组中的位置for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 创建输出数组，用于存储排序后的结果std::vector<int> output(arr.size());// 将元素放入相应的桶中，并按照顺序放入输出数组for (int i = arr.size() - 1; i >= 0; i--) {output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}// 将排序后的结果复制回原数组for (int i = 0; i < arr.size(); i++) {arr[i] = output[i];}}
}

测试程序

可用以下代码测试这些排序算法（将所要测试的代码取消注释即可，此时为测试堆排序）：

int main() {vector<int> arr = { 5, 4, 3, 2, 1 };// bubbleSort(arr);// selectionSort(arr);//shellSort(arr);// insertionSort(arr);// quickSort(arr, 0, arr.size() - 1);// mergeSort(arr, 0, arr.size() - 1);// radixSort(arr);heapSort(arr);for (int num : arr) {cout << num << " ";}cout << endl;return 0;
}

各排序算法总结与比较：

类别	排序方法	时间复杂度			空间复杂度	稳定性	备注
		平均情况	最好情况	最坏情况	辅助存储
插入排序	直接插入	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定	数据量小时较好
	Shell排序	$O(n^{1.3})$	$O(n)$	$O(n^2)$	$O(1)$	不稳定
选择排序	直接选择	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定	数据量小时较好
	堆排序	$O(n{\log }_{2}n)$	$O(n{\log }_{2}n)$	$O(n{\log }_{2}n)$	$O(1)$	不稳定	数据量大时较好
交换排序	冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定	数据量小时较好
	快速排序	$O(n{\log }_{2}n)$	$O(n{\log }_{2}n)$	$O(n^2)$	$O({\log }_{2}n)$	不稳定	数据量大时较好
归并排序		$O(n{\log }_{2}n)$	$O(n{\log }_{2}n)$	$O(n{\log }_{2}n)$	$O(n)$	稳定	数据量大时较好
基数排序		$O(d(r+n))$	$O(d(n+r^d))$	$O(d(r+n))$	$O(r^d+n)$	稳定

注：基数排序的复杂度中，$r$代表关键字的基数，$d$代表长度，$n$代表关键字的个数

总结

不同的排序算法在不同场景下有不同的性能表现。插入排序在数据量小且基本有序时效率较高；选择排序简单但效率相对较低；交换排序中的冒泡排序适用于数据量小的情况，快速排序在平均情况下性能很好但最坏情况较差；堆排序适用于数据量大且不需要稳定排序的情况；归并排序性能稳定但需要额外空间；基数排序适用于对整数等有特定结构数据的排序，且在数据范围有限时效率较高。在实际使用时，根据数据特点和需求选择合适的排序算法。