【C++ | 数据结构】八大常用排序算法详解

1. 排序的稳定性

排序是我们生活中经常会面对的问题，小朋友站队的时候会按照从矮到高的顺序排列；老师查看上课出勤情况时，会按照学生的学号点名；高考录取时，会按照成绩总分降序依次录取等等。那么对于排序它是如何定义的呢？

排序是将一批无序的记录（数据）根据关键字重新排列成有序的记录序列的过程。在工作和编程过程中我们经常接触的有八种经典的算法>排序算法分别是：

冒泡排序：冒泡排序在排序过程中，通过相邻元素的交换将较大的元素逐步“冒泡”到序列的末尾。在相等元素的情况下，冒泡排序不会改变它们的相对顺序，因此是稳定的。
选择排序：选择排序在每一轮选择最小（或最大）元素并将其与当前未排序部分的首元素交换。在相等元素的情况下，这种交换可能会改变它们的相对顺序，因此选择排序是不稳定的。
插入排序：插入排序通过将每个元素插入到已排序部分的正确位置来完成排序。在处理相等元素时，新元素总是插入到已有元素之后，因此相等元素的相对顺序不会改变，插入排序是稳定的。
希尔排序：希尔排序是插入排序的改进版，通过逐步减少增量来排序子序列，最后使用增量为1的插入排序。然而，在排序过程中，元素的位置会发生变化，可能会改变相等元素的相对顺序，因此希尔排序是不稳定的。
快速排序：快速排序通过选择一个基准元素，将数组分成两部分，分别对两部分进行递归排序。在分区过程中，相等元素的相对顺序可能会被改变，因此快速排序是不稳定的。
归并排序：归并排序通过将数组分割成两个子数组，分别排序后再合并。在合并阶段，归并排序会确保相等元素的相对顺序保持不变，因此归并排序是稳定的。
堆排序：堆排序通过构建堆并反复提取堆顶元素来排序。由于在堆构建和排序过程中可能会对相等元素的相对顺序进行重新排列，因此堆排序是不稳定的。
基数排序：基数排序是一种非比较排序方法，通过对数字的每一位进行排序来实现整体排序。在每一位的排序过程中，基数排序会保持相等元素的相对顺序，因此是稳定的。

关于排序还有另一个大家需要掌握的概念就是排序的稳定性。排序的稳定性指的是在算法>排序算法中，如果两个元素的键值相等，排序后它们的相对顺序是否会保持不变。

如果算法>排序算法是稳定的，那么在排序之前和之后，相同键值元素的相对顺序是相同的；
如果算法>排序算法是不稳定的，那么相同键值元素的相对顺序可能会发生变化。

在选择算法>排序算法时，了解排序的稳定性有助于根据具体需求选择合适的算法。如果稳定性很重要，应该选择稳定的算法>排序算法；如果稳定性不重要，可以选择更高效但不稳定的算法>排序算法。

总结：

稳定的算法>排序算法：冒泡排序、插入排序、归并排序、基数排序
不稳定的算法>排序算法：选择排序、希尔排序、快速排序、堆排序

2. 冒泡排序

冒泡排序（Bubble Sort）是一种简单且直观的算法>排序算法。它通过重复地遍历要排序的列表，一次比较两个相邻的元素并交换它们的位置来排序列表。这个过程会一直重复，直到列表变得有序为止。由于每次遍历列表时最大的元素会“冒泡”到列表的末端，故称为冒泡排序。

关于冒泡排序的详细过程如下（按照升序描述）：

从列表的第一个元素开始，依次比较相邻的两个元素。
如果前一个元素比后一个元素大，则交换它们的位置。
继续向后比较，直到列表的末尾。这时，最大的元素被放置到列表的末尾。
重新从列表的第一个元素开始，重复上述过程，但不再处理已排序的最后一个元素。
持续重复步骤 1-4，直到没有需要交换的元素，表示列表已完成排序。

在下图中为大家展示冒泡排序的整个过程，整形数组中有6个元素int array[6] = { 6, 5, 4, 3, 2, 1 };，对其进行了升序排列：

#include <iostream>
#include <vector>
using namespace std;// 升序
void bubbleSort(vector<int>& vec)
{int size = vec.size();bool swapped = false;for (int i = 0; i < size - 1; ++i){swapped = false;for (int j = 0; j < size - i - 1; ++j){if (vec[j] > vec[j + 1]){swap(vec[j], vec[j + 1]);   // 交换swapped = true;}}if (!swapped){break;  // 提前结束排序}}
}int main()
{srand(time(NULL));vector<int> data;cout << "排序前的原始数据: ";for (int i = 0; i < 10; ++i){data.push_back(rand() % 100);cout << data.back() << " ";}cout << endl;bubbleSort(data);cout << "排序之后的数据: ";for (const auto& item : data){cout << item << " ";}cout << endl;return 0;
}

冒泡排序的时间复杂度取决于输入数组的初始状态：

最坏情况下：每次遍历都需要进行比较和交换操作，因此时间复杂度为 O(n2)。
最优情况下：如果输入数组已经有序，只需进行一次遍历，时间复杂度为 O(n)。
平均情况下：每次遍历都需要进行部分比较和交换操作，时间复杂度为 O(n2)。

冒泡排序是一种稳定的算法>排序算法。即相等的元素在排序后不会改变相对顺序。原因在于，当两个相邻的元素相等时，冒泡排序不会交换它们的位置，从而保持了相对顺序的稳定性。

3. 选择排序

选择排序（Selection Sort）是一种简单直观的算法>排序算法。其基本思想是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。虽然选择排序的时间复杂度较高，但其实现简单，适用于小规模数据的排序。

关于选择排序的具体步骤如下（按照升序描述）:

初始状态：将整个序列分为已排序区间和未排序区间。初始时已排序区间为空，未排序区间为整个序列。
选择最小值：在未排序区间中找到最小的元素。
交换位置：将这个最小元素和未排序区间的第一个元素交换位置，使其成为已排序区间的最后一个元素。
重复步骤：重复步骤2和步骤3，直到未排序区间为空。

在下图中为大家展示了整个选择排序的过程：

#include <iostream>
#include <vector>
using namespace std;void selectionSort(vector<int>& vec)
{int size = vec.size();for (int i = 0; i < size - 1; ++i){int minPos = i; for (int j = i + 1; j < size; ++j){if (vec[j] < vec[minPos]) {minPos = j; }}if (minPos != i){swap(vec[i], vec[minPos]);}}
}int main()
{srand(time(NULL));vector<int> data;cout << "排序前的原始数据: ";for (int i = 0; i < 10; ++i){data.push_back(rand() % 100);cout << data.back() << " ";}cout << endl;selectionSort(data);cout << "排序之后的数据: ";for (const auto& item : data){cout << item << " ";}cout << endl;return 0;
}

选择排序的时间复杂度不受输入数据的初始状态影响，始终为 O(n2)。具体分析如下：

最坏情况下：每次选择最小元素都需要遍历未排序部分的所有元素，因此时间复杂度为 O(n2)。
最优情况下：即使输入数据已经有序，选择排序仍需遍历所有元素，因此时间复杂度依旧为 O(n2)。
平均情况下：每次选择最小元素的操作与最坏情况类似，时间复杂度为 O(n2)。

选择排序是一种不稳定的算法>排序算法。即相等的元素在排序后可能改变相对顺序。原因在于，当选择最小元素并进行交换时，可能会将相等元素的相对位置改变。例如，数组 [5, 3, 5, 2] 经过第一次选择后变为 [2, 3, 5, 5]，两个 5 的相对顺序发生了改变。

4. 插入排序

插入排序（Insertion Sort）是一种简单直观的算法>排序算法。它的基本思想是将未排序部分的元素插入到已排序部分的适当位置，从而逐步构建有序列表。插入排序在小规模数据集和部分有序数据集上的表现较好，具有稳定性和简单性。

关于插入排序的具体步骤如下（按照升序描述）:

初始化：从第二个元素（索引为1）开始，将其视为待插入元素。默认第一个元素是已经排好序的有序序列。
遍历：从未排序部分的第一个元素开始，逐一将每个元素插入到已排序部分的适当位置。
插入操作：

将当前元素（称为“待插入元素”）与已排序部分的元素从后向前进行比较。
如果已排序的元素大于待插入元素，则将该已排序元素向右移动一位。
重复上述比较和移动操作，直到找到一个已排序元素小于或等于待插入元素的位置。
将待插入元素插入到这个位置。

4.重复步骤2和步骤3，直到所有元素都排序完成。

为了便于理解，下图为大家展示是插入排序的过程：

#include <iostream>
#include <vector>
using namespace std;void insertionSort(vector<int>& vec)
{int size = vec.size();for (int i = 1; i < size; ++i){int key = vec[i];int j = i - 1;  while (j >= 0 && vec[j] > key){vec[j + 1] = vec[j];j--;}vec[j + 1] = key;}
}int main()
{srand(time(NULL));vector<int> data;cout << "排序前的原始数据: ";for (int i = 0; i < 10; ++i){data.push_back(rand() % 100);cout << data.back() << " ";}cout << endl;insertionSort(data);cout << "排序之后的数据: ";for (const auto& item : data){cout << item << " ";}cout << endl;return 0;
}

插入排序的时间复杂度取决于输入数组的初始状态：

最坏情况下：数组是反向排序的，需要进行最大次数的比较和移动操作，时间复杂度为 O(n2)。
最优情况下：数组已经有序，只需进行 n-1 次比较，时间复杂度为 O(n)。
平均情况下：需要进行部分比较和移动操作，时间复杂度为 O(n2)。

插入排序是一种稳定的算法>排序算法。即相等的元素在排序后不会改变相对顺序。原因在于，当插入相等的元素时，只需插入到相等元素之后即可，不会改变其相对位置。

5. 希尔排序

希尔排序（Shell Sort）是插入排序的一种改进版本，旨在提高插入排序在大规模数据集上的效率。它通过将数据集分割成多个子序列分别进行插入排序，逐步减少子序列的间隔，最终在整个序列上进行插入排序，从而减少数据移动的次数，提升排序效率。

关于希尔排序的具体步骤如下（按照升序描述）:

选择间隔序列：选择一个逐步减小的间隔序列 h，例如：n/2, n/4, ..., 1，直到 h=1。最常见的间隔序列是希尔原始提出的 h = h / 2。
对每个间隔执行插入排序：
- 对于每个间隔 h，将数组分成若干个子数组，每个子数组中的元素之间的间隔为 h。
- 对这些子数组应用插入排序，使得所有的元素在当前间隔 h 下部分有序。
最终的插入排序：
- 当间隔减小到 1 时，整个数组基本有序，此时的插入排序效率更高。

下图为大家展示的是希尔排序的过程：

#include <iostream>
using namespace std;// 希尔排序函数
void shellSort(int arr[], int n) {// 选择间隔序列：初始间隔为 n/2for (int gap = n / 2; gap > 0; gap /= 2) {// 对每个间隔进行插入排序for (int i = gap; i < n; ++i) {int temp = arr[i];int j = i;// 将当前元素插入到已排序的部分while (j >= gap && arr[j - gap] > temp) {arr[j] = arr[j - gap];j -= gap;}arr[j] = temp;}}
}// 打印数组的函数
void printArray(int arr[], int size) {for (int i = 0; i < size; ++i) {cout << arr[i] << " ";}cout << endl;
}int main() {int arr[] = {12, 34, 54, 2, 3};int n = sizeof(arr) / sizeof(arr[0]);shellSort(arr, n);cout << "Sorted array: ";printArray(arr, n);return 0;
}

希尔排序的时间复杂度依赖于间隔序列的选择：

最坏情况下：时间复杂度O(n2)。
最优情况下：时间复杂度为 O(n)。
平均情况下：时间复杂 O(n1.3)。

希尔排序是一种不稳定的算法>排序算法。即相等的元素在排序后可能改变相对顺序。原因在于当使用较大间隔进行交换时，相等元素的相对顺序可能会被打乱。

6.快速排序

快速排序是一种高效的算法>排序算法，采用分治策略来排序数组。它通过选择一个“基准”元素，将数组分成两个子数组，分别对这两个子数组进行递归排序，从而实现整体排序。快速排序在大多数情况下具有良好的性能，是实际应用中常用的算法>排序算法。

关于快速排序的具体步骤如下（按照升序描述）

选择基准：从数组中选择一个基准元素（通常选择第一个元素、最后一个元素、或中间元素）。基准元素的选择方法可以影响排序的效率。
分区操作：
- 遍历数组，将比基准元素小的元素移到基准元素的左边，比基准元素大的元素移到右边。
- 分区完成后，基准元素位于其最终位置。
递归排序：
- 对基准元素左边的子数组和右边的子数组分别递归调用快速排序。
终止条件：当子数组的大小小于等于1时，递归结束，数组已排序完成。

为了便于理解，下图描述了快速排序的全过程

#include <iostream>
using namespace std;// 分区操作函数，选择基准元素，并对数组进行分区
int partition(int arr[], int low, int high) {int pivot = arr[high]; // 选择最后一个元素作为基准int i = low - 1; // i 是已排序部分的最后一个元素的索引// 遍历未排序部分，将小于基准的元素移到左边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(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);}
}// 打印数组的函数
void printArray(int arr[], int size) {for (int i = 0; i < size; ++i) {cout << arr[i] << " ";}cout << endl;
}int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1); // 调用快速排序函数cout << "Sorted array: ";printArray(arr, n); // 打印排序后的数组return 0;
}

快速排序的时间复杂度受基准选择的影响：

最坏情况下：如果每次选择的基准都是当前数组中的最小或最大值，则每次只能将一个元素放在正确的位置，时间复杂度为 O(n2)。这种情况在数组已经有序或逆序时可能出现。
最优情况下：每次选择的基准都能将数组平分，时间复杂度为 O(n log n)。
平均情况下：在多数情况下，快速排序的时间复杂度为 O(n log n)。

快速排序是一种不稳定的算法>排序算法。即相等的元素在排序后可能改变相对顺序。原因在于分区操作中，可能会交换相等的元素，从而改变它们的相对位置。

7.归并排序

归并排序（Merge Sort）是一种基于分治法的高效算法>排序算法。它的基本思想是将数组分成两个子数组，分别进行排序，然后合并这两个有序子数组。归并排序的时间复杂度为 O(n log n)，且具有稳定性，因此在实际应用中广泛使用。

关于归并排序的具体步骤如下（按照升序描述）:

分割数组：

如果数组的长度大于1，将数组从中间分割成两部分。
对每一部分再递归进行分割，直到每个子数组的长度为1。

合并排序：

合并两个有序的子数组成一个有序的数组。
具体做法是比较两个子数组的第一个元素，将较小的元素放入合并结果中，并移到下一个元素，重复这个过程直到一个子数组为空，然后将另一个子数组剩下的元素全部放入合并结果中。

递归合并：

对每个子数组重复上述步骤，直到所有子数组合并为一个完整的有序数组。

为了便于理解，下图展示了归并排序的过程：

#include <iostream>
using namespace std;// 合并两个已排序的子数组的函数
void merge(int arr[], int left, int mid, int right) {int n1 = mid - left + 1; // 左子数组的大小int n2 = right - mid;    // 右子数组的大小// 创建临时数组int* L = new int[n1];int* R = new int[n2];// 复制数据到临时数组for (int i = 0; i < n1; ++i)L[i] = arr[left + i];for (int j = 0; j < n2; ++j)R[j] = arr[mid + 1 + j];// 合并临时数组int i = 0, j = 0, k = left;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++];}// 释放临时数组的内存delete[] L;delete[] R;
}// 归并排序函数
void mergeSort(int arr[], int left, int right) {if (left < right) {int mid = left + (right - left) / 2; // 计算中点// 递归排序两个子数组mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);// 合并两个已排序的子数组merge(arr, left, mid, right);}
}// 打印数组的函数
void printArray(int arr[], int size) {for (int i = 0; i < size; ++i) {cout << arr[i] << " ";}cout << endl;
}int main() {int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr) / sizeof(arr[0]);mergeSort(arr, 0, n - 1); // 调用归并排序函数cout << "Sorted array: ";printArray(arr, n); // 打印排序后的数组return 0;
}

归并排序的时间复杂度可以通过递归方程来分析：

最坏情况下：归并排序的时间复杂度为 O(n log n)，因为每次分割数组的操作都是对半分，递归深度为 log n，每层的合并操作时间复杂度为 O(n)。
最优情况下：时间复杂度同样为 O(n log n)，因为归并排序的过程与数组的初始顺序无关，始终需要进行分割和合并操作。
平均情况下：归并排序的时间复杂度也是 O(n log n)，因为它在任何情况下都需要进行相同数量的分割和合并操作。

8. 堆排序

堆排序（Heap Sort）是一种基于二叉堆数据结构的比较算法>排序算法。堆排序利用堆这种数据结构的性质来实现排序，分为构建初始堆和反复从堆中取出最大元素（对于升序排序）两个主要步骤。堆排序的时间复杂度为 O(n log n)，且不需要额外的内存空间，因此在实际应用中非常有效。

在进行堆排序的时候使用的二叉堆有两种，分别是：最大堆和最小堆，它们有以下特性需要大家掌握：

最大堆（Max Heap）：对于每个节点 i，其父节点 parent(i) 的值都不小于节点 i 的值。换句话说，堆中任意节点的值都大于或等于其子节点的值。
最小堆（Min Heap）：对于每个节点 i，其父节点 parent(i) 的值都不大于节点 i 的值。也就是说，堆中任意节点的值都小于或等于其子节点的值。

关于堆排序的具体步骤如下（按照升序描述）:

堆化（Heapify）操作

最大堆的堆化操作的目的是在子树中选择一个最大元素，并让父节点的值大于或等于其子节点的值。具体步骤如下：

初始化最大值：假设当前节点 i 是最大值。
比较左子节点：如果左子节点存在且其值大于当前节点的值，将左子节点的值更新为最大值。
比较右子节点：如果右子节点存在且其值大于当前最大值，将右子节点的值更新为最大值。
交换值并递归：如果最大值不是当前节点，将当前节点与最大值节点交换位置，并对新的子树进行堆化。

构建最大堆

步骤 1：从最后一个非叶子节点开始
我们需要找到数组中最后一个非叶子节点的位置。
对于一个长度为 n 的数组，最后一个非叶子节点的位置是 n/2 - 1（向下取整）。
步骤 2：自下而上调整
从最后一个非叶子节点开始，向前遍历整个数组，对每个节点进行堆化操作，确保该节点及其子树满足最大堆的性质。

堆排序过程

交换根节点与最后一个节点：
将堆顶元素（即最大元素）与堆的最后一个元素交换位置，这样最大元素就被移到数组末尾。
缩小堆的范围：
将堆的有效范围缩小（忽略末尾已排序的部分），对新的根节点进行堆化，重新调整成最大堆。
重复以上步骤：
重复交换和堆化过程，直到堆的有效范围缩小到1。

#include <iostream>
using namespace std;// 堆化函数，维护最大堆性质
void heapify(int arr[], int n, int i) {int largest = i; // 将当前节点设为最大int left = 2 * i + 1; // 左子节点int right = 2 * i + 2; // 右子节点// 检查左子节点是否大于当前最大if (left < n && arr[left] > arr[largest])largest = left;// 检查右子节点是否大于当前最大if (right < n && arr[right] > arr[largest])largest = right;// 如果最大不是当前节点，交换并递归堆化if (largest != i) {swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}// 堆排序函数
void heapSort(int arr[], int n) {// 构建最大堆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);}
}// 打印数组的函数
void printArray(int arr[], int size) {for (int i = 0; i < size; ++i) {cout << arr[i] << " ";}cout << endl;
}int main() {int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr) / sizeof(arr[0]);heapSort(arr, n); // 调用堆排序函数cout << "Sorted array: ";printArray(arr, n); // 打印排序后的数组return 0;
}

堆排序的时间复杂度可以通过以下分析得出：

最坏情况下：构建最大堆的时间复杂度为 O(n)，每次调整堆的时间复杂度为 O(log n)，因此总时间复杂度为 O(n log n)。
最优情况下：时间复杂度同样为 O(n log n)，因为无论数组初始状态如何，都需要进行构建堆和调整堆的操作。
平均情况下：堆排序的时间复杂度也是 O(n log n)，与数组初始状态无关。

堆排序是一种不稳定的算法>排序算法。即相等的元素在排序后可能改变相对顺序。原因在于堆的调整过程中，可能会交换相等元素的位置，从而改变它们的相对顺序。

9. 基数排序

基数排序（Radix Sort）是一种非比较算法>排序算法，通过逐位处理数字来排序数组。它利用桶排序的思想，对数字的每一位进行排序，从最低有效位到最高有效位。基数排序特别适用于处理大量的整数或字符串数据。其时间复杂度为 O(d*(n+k))，其中 d 是数字的位数，n 是数组的长度，k 是基数【使用十进制，基数 ( k = 10 )】。

关于基数排序的具体步骤如下（按照升序描述）:

确定最大位数：
- 找到数组中最大数字的位数。
按位排序：
- 从最低位到最高位进行排序，每次按当前位的值将数字分配到桶中，并使用稳定的算法>排序算法（如计数排序）对这些桶中的数字进行排序。
合并桶：
- 根据每位的排序结果，将所有桶中的数字按顺序重新合并到数组中。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;// 使用计数排序对数组的特定位进行排序
void countSort(vector<int>& arr, int exp) {int n = arr.size();vector<int> output(n); // 输出数组vector<int> count(10, 0); // 计数数组// 计算每个数字在当前位的出现次数for (int i = 0; i < n; ++i)count[(arr[i] / exp) % 10]++;// 计算计数数组中每个元素的累计值for (int i = 1; i < 10; ++i)count[i] += count[i - 1];// 从后往前遍历输入数组，按当前位的值填充输出数组for (int i = n - 1; i >= 0; --i) {output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}// 将排序后的结果复制回原数组for (int i = 0; i < n; ++i)arr[i] = output[i];
}// 基数排序函数
void radixSort(vector<int>& arr) {int maxVal = *max_element(arr.begin(), arr.end()); // 找到最大值for (int exp = 1; maxVal / exp > 0; exp *= 10) {countSort(arr, exp); // 按当前位进行计数排序}
}// 打印数组的函数
void printArray(const vector<int>& arr) {for (int num : arr) {cout << num << " ";}cout << endl;
}int main() {vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};radixSort(arr); // 调用基数排序函数cout << "Sorted array: ";printArray(arr); // 打印排序后的数组return 0;
}

基数排序的时间复杂度可以通过以下分析得出：