1. 排序的稳定性 {#1-排序的稳定性} =====================

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

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

1. 冒泡排序
2. 选择排序
3. 插入排序
4. 希尔排序
5. 快速排序
6. 归并排序
7. 堆排序
8. 基数排序

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

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

假设我们有一组待排序的对象，其中每个对象有两个属性：键值和姓名。并要求根据键值对每组数据进行排序：

| 键值 | 姓名 | |:--:|:---:| | 4 | 令狐冲 | | 3 | 任盈盈 | | 4 | 岳不群 | | 1 | 杨过 | | 3 | 小龙女 |

• 使用稳定的排序算法（例如插入排序、归并排序、冒泡排序），结果会是：

  | 键值 | 姓名 | |:--:|:---:| | 1 | 杨过 | | 3 | 任盈盈 | | 3 | 小龙女 | | 4 | 令狐冲 | | 4 | 岳不群 |

  • 键值为3的元素 (3, "任盈盈") 和 (3, "小龙女") 在排序前的相对顺序在排序后仍然保持不变
  • 键值为4的元素 (4, "令狐冲") 和 (4, "岳不群") 的相对顺序也保持不变

• 使用不稳定的排序算法（例如快速排序、选择排序、堆排序），可能的结果是：

  | 键值 | 姓名 | |:--:|:---:| | 1 | 杨过 | | 3 | 小龙女 | | 3 | 任盈盈 | | 4 | 岳不群 | | 4 | 令狐冲 |

  • 键值为3的元素 (3, "小龙女") 和 (3, "任盈盈") 的相对顺序在排序后发生了变化
  • 键值为4的元素 (4, "岳不群") 和 (4, "令狐冲") 的相对顺序也发生了变化。

排序的稳定性在某些情况下非常重要，特别是在需要多次排序的情况下。例如，当我们需要先按照某个属性排序，再按照另一个属性排序时，稳定性可以确保第一次排序的结果不会被第二次排序打乱。

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

2. 冒泡排序 {#2-冒泡排序} =================

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

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

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

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

下面是使用C++编写的冒泡排序的示例代码:

|---------------------------------------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | #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(n^2^)。
• 最优情况下：如果输入数组已经有序，只需进行一次遍历，时间复杂度为 O(n)。
• 平均情况下 ：每次遍历都需要进行部分比较和交换操作，时间复杂度为 O(n^2^)。

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

3. 选择排序 {#3-选择排序} =================

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

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

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

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

下面是使用C++编写的选择排序的示例代码:

|------------------------------------------------------------------------------------------------------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #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(n^2^)。具体分析如下：

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

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

4. 插入排序 {#4-插入排序} =================

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

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

1. 初始化：从第二个元素（索引为1）开始，将其视为待插入元素。默认第一个元素是已经排好序的有序序列。
2. 遍历：从未排序部分的第一个元素开始，逐一将每个元素插入到已排序部分的适当位置。
3. 插入操作 ：
   • 将当前元素（称为"待插入元素"）与已排序部分的元素从后向前进行比较。
   • 如果已排序的元素大于待插入元素，则将该已排序元素向右移动一位。
   • 重复上述比较和移动操作，直到找到一个已排序元素小于或等于待插入元素的位置。
   • 将待插入元素插入到这个位置。
4. 重复步骤2和步骤3，直到所有元素都排序完成。

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

下面是使用C++编写的插入排序的示例代码:

|------------------------------------------------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #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(n^2^)。
• 最优情况下：数组已经有序，只需进行 n-1 次比较，时间复杂度为 O(n)。
• 平均情况下 ：需要进行部分比较和移动操作，时间复杂度为 O(n^2^)。

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

5. 希尔排序 {#5-希尔排序} =================

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

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

1. 选择初始增量序列 ：设置一个增量gap，常见的选择是初始增量为数组长度的一半，然后逐步减半，直到增量为1。也可以根据实际情况使用其他的增量（增量不同，排序的效率也不同）。
2. 对每个增量进行排序 ：
   • 分组 ：将数组分成多个子序列，子序列中的元素间隔为gap。
   • 对子序列进行插入排序 ：对每个子序列进行插入排序。由于gap较大，子序列的长度较短，插入排序效率较高。
3. 重复步骤2：减小增量，继续对每个减小后的增量进行排序，直到增量为1。增量为1时，整个数组就是一个整体，进行一次标准的插入排序。

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

下面是使用C++编写的希尔排序的示例代码:

|---------------------------------------------------------------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include <iostream> #include <vector> using namespace std; void shellSort(vector<int>& vec) { int size = vec.size(); for (int gap = size / 2; gap > 0; gap /= 2) { for (int i = gap; i < size; ++i) { int temp = vec[i]; int j = i - gap; while (j >= 0 && vec[j] > temp) { vec[j + gap] = vec[j]; j -= gap; } vec[j + gap] = temp; } } } 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; shellSort(data); cout << "排序之后的数据: "; for (const auto& item : data) { cout << item << " "; } cout << endl; return 0; } |

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

• 最坏情况下 ：时间复杂度O(n^2^)。
• 最优情况下：时间复杂度为 O(n)。
• 平均情况下 ：时间复杂 O(n^1.3^)。

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

6. 快速排序 {#6-快速排序} =================

快速排序（Quick Sort）是一种高效的比较排序算法，由C.A.R. Hoare在1960年提出。快速排序采用分治策略，通过递归地将数组分割成子数组来实现排序。其平均时间复杂度为 O(n log n)，在大多数情况下表现良好，因此在实际应用中广泛使用。

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

1. 选择基准：从数组中选择一个元素作为基准（pivot）。常见的选择方式是选择第一个元素、最后一个元素或者中间元素。
2. 分区操作：将数组中小于基准的元素移到基准的左边，大于基准的元素移到基准的右边。
3. 递归排序：递归地对基准左边和右边的子数组进行步骤1和步骤2的操作。
4. 合并结果：当递归完成时，数组就变成了有序的。

为了便于理解，下图描述了快速排序的全过程【点击图片放大更清晰】：

下面是使用C++编写的快速排序的示例代码:

|------------------------------------------------------------------------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include <iostream> #include <vector> using namespace std; void quickSort(vector<int>& vec, int left, int right) { // 递归结束的条件 if (left >= right) { return; } int pivot = vec[(left + right) / 2]; int begin = left - 1, end = right + 1; while (begin < end) { // 先移动再判断 do { begin++; } while (vec[begin] < pivot); do { end--; } while (vec[end] > pivot); if (begin < end) { swap(vec[begin], vec[end]); } } quickSort(vec, left, end); quickSort(vec, end + 1, right); } 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; quickSort(data, 0, data.size() - 1); cout << "排序之后的数据: "; for (const auto& item : data) { cout << item << " "; } cout << endl; return 0; } |

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

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

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

7. 归并排序 {#7-归并排序} =================

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

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

1. 分割数组 ：
   • 如果数组的长度大于1，将数组从中间分割成两部分。
   • 对每一部分再递归进行分割，直到每个子数组的长度为1。
2. 合并排序 ：
   • 合并两个有序的子数组成一个有序的数组。
   • 具体做法是比较两个子数组的第一个元素，将较小的元素放入合并结果中，并移到下一个元素，重复这个过程直到一个子数组为空，然后将另一个子数组剩下的元素全部放入合并结果中。
3. 递归合并 ：
   • 对每个子数组重复上述步骤，直到所有子数组合并为一个完整的有序数组。

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

下面是使用C++编写的归并排序的示例代码:

|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | #include <iostream> #include <vector> using namespace std; void mergeSort(vector<int>& vec, int left, int right) { if (left >= right) { return; } int mid = (left + right) / 2; mergeSort(vec, left, mid); mergeSort(vec, mid + 1, right); int k = 0; int i = left, j = mid + 1; vector<int> tmp; while (i <= mid && j <= right) { if (vec[i] <= vec[j]) { tmp.push_back(vec[i++]); } else { tmp.push_back(vec[j++]); } } while (i <= mid) { tmp.push_back(vec[i++]); } while (j <= right) { tmp.push_back(vec[j++]); } for (i = left, k = 0; i <= right; ++i) { vec[i] = tmp[k++]; } } 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; mergeSort(data, 0, data.size() - 1); cout << "排序之后的数据: "; for (const auto& item : data) { cout << item << " "; } cout << endl; return 0; } |

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

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

8. 堆排序 {#8-堆排序} ===============

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

二叉堆其实就是一棵完全二叉树，有不懂的小伙伴可以来这里补课

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

• 最大堆（Max Heap）

  对于每个节点 i，其父节点 parent(i) 的值都不小于节点 i 的值。换句话说，堆中任意节点的值都大于或等于其子节点的值。

• 最小堆（Min Heap）

  对于每个节点 i，其父节点 parent(i) 的值都不大于节点 i 的值。也就是说，堆中任意节点的值都小于或等于其子节点的值。

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

1. 堆化（Heapify）操作

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

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

2. 构建最大堆

   • 步骤 1：从最后一个非叶子节点开始

     • 我们需要找到数组中最后一个非叶子节点的位置。
     • 对于一个长度为 n 的数组，最后一个非叶子节点的位置是 n/2 - 1（向下取整）。

   • 步骤 2：自下而上调整

     从最后一个非叶子节点开始，向前遍历整个数组，对每个节点进行堆化操作，确保该节点及其子树满足最大堆的性质。

3. 堆排序过程

   • 交换根节点与最后一个节点：

     将堆顶元素（即最大元素）与堆的最后一个元素交换位置，这样最大元素就被移到数组末尾。

   • 缩小堆的范围：

     将堆的有效范围缩小（忽略末尾已排序的部分），对新的根节点进行堆化，重新调整成最大堆。

   • 重复以上步骤：

     重复交换和堆化过程，直到堆的有效范围缩小到1。

下面是使用C++编写的堆排序的示例代码:

|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | #include <iostream> #include <vector> using namespace std; void heapAdjust(vector<int>& vec, int len, int parent) { int largest = parent; int left = 2 * parent + 1; int right = 2 * parent + 2; if (left < len && vec[left] > vec[largest]) { largest = left; } if (right < len && vec[right] > vec[largest]) { largest = right; } if (largest != parent) { swap(vec[parent], vec[largest]); heapAdjust(vec, len, largest); } } void heapSort(vector<int>& vec) { int size = vec.size(); for (int i = size / 2 - 1; i >= 0; --i) { heapAdjust(vec, vec.size(), i); } for (int i = size - 1; i > 0; --i) { swap(vec[0], vec[i]); heapAdjust(vec, i, 0); } } int main() { srand(time(NULL)); vector<int> data; cout << "排序前的原始数据: "; for (int i = 0; i < 11; ++i) { data.push_back(rand() % 100); cout << data.back() << " "; } cout << endl; heapSort(data); cout << "排序之后的数据: "; for (const auto& item : data) { cout << item << " "; } cout << endl; return 0; } |

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

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

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

9. 基数排序 {#9-基数排序} =================

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

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

1. 确定排序的最大位数 ：
   • 找出数组中最大数的位数 k，作为基数排序的迭代次数。
2. 按每一位进行计数排序 ：
   • 从最低位到最高位（从个位到最高位），对数组进行排序。
   • 使用桶排序作为子过程，根据当前位的数值对元素进行排序。
     • 根据数据的范围和分布创建若干个桶，每个桶负责一定范围内的数值。
     • 根据每个元素的值，将其分配到对应的桶中
     • 依次遍历每个桶，即完成了基于当前数字位的排序，并使用它覆盖原来的数据序列
   • 使用新的数据序列进行下一轮的桶排序。

下面的动态图片为大家演示了基数排序的整个过程:

下面是使用C++编写的基数排序的示例代码:

|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | #include <iostream> #include <vector> #include <string> using namespace std; void radixSort(vector<int>& vec) { int max = 0; for (int i = 0; i < vec.size(); ++i) { if (max < vec[i]) { max = vec[i]; } } int len = to_string(max).length(); vector<vector<int>> bucket; int mod = 10, dev = 1; for (int i = 0; i < len; ++i, mod *= 10, dev *= 10) { bucket.resize(10); // 有10个桶: 0~9 for (int j = 0; j < vec.size(); ++j) { int num = vec[j] % mod / dev; bucket[num].push_back(vec[j]); } int index = 0; for (const auto& item : bucket) { for (const auto& it : item) { vec[index++] = it; } } bucket.clear(); } } 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; radixSort(data); cout << "排序之后的数据: "; for (const auto& item : data) { cout << item << " "; } cout << endl; return 0; } |

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

• 最坏情况下 ：时间复杂度为 O(d*(n+k))，其中 d 是最大数的位数，n 是数组的大小，k 是基数。
• 最优情况下 ：时间复杂度同样为 O(d*(n+k))，因为无论数组初始状态如何，都需要对每一位进行排序。
• 平均情况下 ：基数排序的时间复杂度也是 O(d*(n+k))。

10. 总结 {#10-总结} ===============

对于以上讲解的八种排序算法，最后我们把它们的空间复杂度和时间复杂度全部罗列出来，做一个对比：

| 算法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | |:----:|:-----------:|:-----------:|:-----------:|:--------:|:---:| | 冒泡排序 | O(n^2^) | O(n) | O(n^2^) | O(1) | 稳定 | | 选择排序 | O(n^2^) | O(n^2^) | O(n^2^) | O(1) | 不稳定 | | 插入排序 | O(n^2^) | O(n) | O(n^2^) | O(1) | 稳定 | | 希尔排序 | O(n^1.3^) | O(n) | O(n^2^) | O(1) | 不稳定 | | 快速排序 | O(n log n) | O(n log n) | O(n^2^) | O(log n) | 不稳定 | | 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 | | 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 | | 基数排序 | O(d*(n+k)) | O(d*(n+k)) | O(d*(n+k)) | O(n+k) | 稳定 |