c++的基础排序算法

一、快速排序

1. 选择基准值（Pivot）

• 作用 ：从数组中选择一个元素作为基准（Pivot），用于划分数组。
• 常见选择方式 ：
  • 固定选择最后一个元素（如示例代码）。
  • 随机选择（优化最坏情况）。
  • 选择中间元素或“三数取中”（避免极端情况）。
• 示例 ：对数组 [10, 7, 8, 9, 1, 5]，选择最后一个元素 5 作为基准。

2. 分区操作（Partition）

• 目标 ：将数组分为两部分，使得：
  • 左半部分所有元素 ≤ 基准值。
  • 右半部分所有元素 > 基准值。
• 具体步骤 ：
  1. 初始化两个指针：
     • i：标记小于基准的边界（初始为 low-1）。
     • j：遍历数组的指针（从 low 到 high-1）。
  2. 遍历数组：
     • 如果 arr[j] ≤ pivot，则 i++，并交换 arr[i] 和 arr[j]。
     • 否则，不做操作，继续移动 j。
  3. 最后，将基准值交换到正确位置（i+1）。
• 示例 ：
  • 初始数组：[10, 7, 8, 9, 1, 5]（基准为 5）。
  • 分区后：[1, 5, 8, 9, 7, 10]（基准位置为索引 1）。

3. 递归排序子数组

• 分治策略 ：
  1. 对左半部分（low 到 pivotIndex-1）递归调用快速排序。
  2. 对右半部分（pivotIndex+1 到 high）递归调用快速排序。
• 终止条件 ：当子数组长度 ≤1 时，无需排序（递归结束）。
• 示例 ：
  • 左子数组 [1]（已有序）。
  • 右子数组 [8, 9, 7, 10]，继续递归分区。

4. 代码实现

#include <algorithm>  // 提供 std::swap 函数
#include <cstdlib>    // 提供 rand() 和 srand()
#include <ctime>      // 提供 time() 函数用于初始化随机数种子
#include <iostream>   // 提供输入输出功能
#include <vector>     // 提供动态数组 vectorusing namespace std;// 分区函数：将数组划分为两部分，并返回基准值的最终位置
int partition(vector<int>& nums, int low, int high)
{// 随机选择一个索引作为基准值，并将其与最后一个元素交换int index = low + (rand() % (high - low + 1)); // 随机选择 [low, high] 范围内的索引swap(nums[index], nums[high]);                 // 将基准值放到末尾int pivot = nums[high];                        // 基准值为当前区间最后一个元素int i = low - 1;                               // i 表示小于基准值的边界// 遍历区间 [low, high-1]，将小于基准值的元素放到左边for (int j = low; j < high; j++) {if (nums[j] < pivot) {                     // 如果当前元素小于基准值++i;                                   // 扩展小于基准值的区域swap(nums[j], nums[i]);                // 将当前元素与边界后的元素交换}}// 将基准值放到正确的位置（即小于基准值区域的后一个位置）swap(nums[++i], nums[high]);return i;                                      // 返回基准值的最终位置
}// 快速排序主函数：递归地对数组进行排序
void quick_sort(vector<int>& nums, int low, int high)
{// 如果区间有效（low < high），则继续分区和递归排序if (low < high) {int index = partition(nums, low, high);    // 对当前区间进行分区，获取基准值位置quick_sort(nums, low, index - 1);          // 递归排序左分段（小于基准值的部分）quick_sort(nums, index + 1, high);         // 递归排序右分段（大于基准值的部分）}
}int main()
{srand(time(0));                                // 初始化随机数种子，确保每次运行生成不同的随机数// 定义测试用例vector<int> nums1 = {10, 7, 8, 9, 1, 5};        // 普通数组vector<int> nums2 = {1};                       // 单元素数组vector<int> nums3 = {};                        // 空数组vector<int> nums4 = {5, 5, 5, 5};              // 全部相等的数组// 对每个数组进行快速排序quick_sort(nums1, 0, nums1.size() - 1);quick_sort(nums2, 0, nums2.size() - 1);quick_sort(nums3, 0, nums3.size() - 1);quick_sort(nums4, 0, nums4.size() - 1);// 输出排序结果cout << "nums1: ";for (auto& x : nums1)cout << x << " ";                          // 输出普通数组的排序结果cout << endl;cout << "nums2: ";for (auto& x : nums2)cout << x << " ";                          // 输出单元素数组的排序结果cout << endl;cout << "nums3: ";for (auto& x : nums3)cout << x << " ";                          // 输出空数组的排序结果cout << endl;cout << "nums4: ";for (auto& x : nums4)cout << x << " ";                          // 输出全部相等数组的排序结果cout << endl;return 0;
}

运行结果： 

以数组 [10, 7, 8, 9, 1, 5] 为例：

1. 第一次分区 ：
   • 基准值为 5。
   • 分区后数组变为 [1, 5, 8, 9, 7, 10]，基准位置为索引 1。
2. 递归处理左子数组 [1]（无需操作）。
3. 递归处理右子数组 [8, 9, 7, 10]：
   • 选择基准 10，分区后数组变为 [8, 9, 7, 10]，基准位置为索引 3。
   • 递归处理左子数组 [8, 9, 7]：
     • 选择基准 7，分区后 [7, 9, 8]，基准位置为索引 0。
     • 递归处理右子数组 [9, 8]，最终排序为 [8, 9]。
   • 合并结果得到 [7, 8, 9, 10]。
4. 最终排序结果 ：[1, 5, 7, 8, 9, 10]。

---

二、归并排序

1. 分治策略 

1. 分解 ：将数组不断对半分割，直到每个子数组长度为1（天然有序）
2. 解决 ：递归地对左右子数组进行排序
3. 合并 ：将两个有序子数组合并成一个更大的有序数组

2. 归并排序的分解过程

1、初始数组

索引：0   1   2   3   4   5
值： 10  7   8   9   1   5

2、 第一层分解 （整个数组）

[10, 7, 8, 9, 1, 5] → 左半部分 [10, 7, 8] 和 右半部分 [9, 1, 5]

 3、第二层分解 （左半部分 [10,7,8]）

[10,7,8] → 左半部分 [10] 和 右半部分 [7,8]

 4、第三层分解 （右半部分 [7,8]）

[7,8] → 左半部分 [7] 和 右半部分 [8]

 5、第二层分解 （右半部分 [9,1,5]）

[9,1,5] → 左半部分 [9] 和 右半部分 [1,5]

6、第三层分解 （右半部分 [1,5]）

[1,5] → 左半部分 [1] 和 右半部分 [5]

 3. 归并排序的合并过程

1)、合并层级 1

1. 合并 [7] 和 [8] → [7,8]

2. 合并 [1] 和 [5] → [1,5]

2)、合并层级 2

• 合并 [10] 和 [7,8] → [7,8,10]

10 vs 7 → 取7 → 新数组[7]
10 vs 8 → 取8 → 新数组[7,8]
剩余10 → 追加 → [7,8,10]

•  合并 [9] 和 [1,5] → [1,5,9]

9 vs 1 → 取1 → 新数组[1]
9 vs 5 → 取5 → 新数组[1,5]
剩余9 → 追加 → [1,5,9]

3)、 合并层级 3（最终合并）

左数组：7,8,10
右数组：1,5,9
初始指针：i=0（左）, j=0（右）

1. 比较 7 vs 1 → 取1 → 新数组[1]
2. 比较 7 vs 5 → 取5 → 新数组[1,5]
3. 比较 7 vs 9 → 取7 → 新数组[1,5,7]
4. 比较 8 vs 9 → 取8 → 新数组[1,5,7,8]
5. 比较 10 vs 9 → 取9 → 新数组[1,5,7,8,9]
6. 右数组耗尽，追加剩余左数组元素 → [1,5,7,8,9,10]

 4、代码实现

#include <iostream>
#include <vector>
using namespace std;/*** 合并两个有序子数组* @param nums 原始数组* @param l 左边界索引（包含）* @param r 右边界索引（包含）* @param mid 中间分割点索引*/
void merge(vector<int>& nums, int l, int r, int mid)
{// 创建左右子数组（左闭右开区间）vector<int> left(nums.begin() + l,nums.begin() + mid + 1); // 左子数组 [l, mid]vector<int> right(nums.begin() + mid + 1,nums.begin() + r + 1); // 右子数组 [mid+1, r]int i = 0, j = 0, k = l; // i:左数组指针，j:右数组指针，k:原数组指针// 合并两个有序数组while (i < left.size() && j < right.size()) {// 使用 <= 保持稳定性：相等元素保留原始顺序if (left[i] <= right[j]) {nums[k++] = left[i++];}else {nums[k++] = right[j++];}}// 处理剩余元素（如果有的话）while (i < left.size())nums[k++] = left[i++];while (j < right.size())nums[k++] = right[j++];
}/*** 归并排序递归函数* @param nums 待排序数组* @param l 当前处理范围的左边界（包含）* @param r 当前处理范围的右边界（包含）*/
void merge_sort(vector<int>& nums, int l, int r)
{if (l >= r)return;                   // 递归终止条件：子数组长度≤1int mid = l + (r - l) / 2;    // 防溢出的中间点计算merge_sort(nums, l, mid);     // 递归排序左半部分merge_sort(nums, mid + 1, r); // 递归排序右半部分merge(nums, l, r, mid);       // 合并有序子数组
}/*** 归并排序辅助函数（对外接口）* @param nums 待排序数组*/
void merge_sort(vector<int>& nums)
{if (!nums.empty()) { // 非空时才执行排序merge_sort(nums, 0, nums.size() - 1);}
}/*** 测试用例执行函数* @param nums 测试数组* @param testName 测试用例名称*/
void runTest(vector<int>& nums, const string& testName)
{cout << "========== " << testName << " ==========\n";cout << "原始数组: ";if (nums.empty()) {cout << "（空数组）";}else {for (int num : nums)cout << num << " ";}cout << endl;merge_sort(nums); // 执行排序cout << "排序结果: ";if (nums.empty()) {cout << "（空数组）";}else {for (int num : nums)cout << num << " ";}cout << "\n\n";
}int main()
{// 测试用例定义vector<int> nums1 = {10, 7, 8, 9, 1, 5}; // 普通无序数组vector<int> nums2 = {1};                 // 单元素数组vector<int> nums3 = {};                  // 空数组vector<int> nums4 = {5, 5, 5, 5};        // 全相等元素数组vector<int> nums5 = {3, 1, 2, 4, 5};     // 部分有序数组vector<int> nums6 = {5, 4, 3, 2, 1};     // 完全逆序数组// 执行测试runTest(nums1, "普通数组");runTest(nums2, "单元素数组");runTest(nums3, "空数组");runTest(nums4, "全部相等的数组");runTest(nums5, "部分有序数组");runTest(nums6, "完全逆序数组");return 0;
}

运行结果 

---

三、插入排序

1、算法步骤 

1. 初始状态 ：默认第一个元素是已排序的。
2. 迭代过程 ：
   • 从第二个元素开始，依次取出每个元素（称为“当前元素”）。
   • 将当前元素与已排序序列中的元素从后向前 依次比较。
   • 如果已排序的元素大于当前元素，则将其后移一位，为当前元素腾出位置。
   • 直到找到已排序元素小于或等于当前元素的位置，将当前元素插入此处。
3. 终止条件 ：所有元素均被插入到已排序序列中。

2、代码实现

#include <iostream>
#include <vector>
using namespace std;/*** @brief 插入排序算法实现** 通过逐步构建有序序列，将未排序元素插入到已排序序列的正确位置。* 时间复杂度：O(n²) 最坏/平均情况，O(n) 最好情况（已有序）* 空间复杂度：O(1) 原地排序* 稳定性：稳定排序算法** @param nums 待排序的整型向量（引用传递，直接修改原数组）*/
void insert_sort(vector<int>& nums)
{if(nums.empty() && nums.size() == 1) return;for (int i = 1; i < nums.size(); i++) {int temp = nums[i]; // 保存当前待插入元素int j = i - 1;// 将大于temp的已排序元素后移，腾出插入空间while (j >= 0 && nums[j] > temp) {nums[j + 1] = nums[j];--j;}// 因为内层循环结束后，j 必定在待插入元素的前一位// 比如：插入位置为0，那么j 必定等于 -1nums[j + 1] = temp; // 插入到正确位置}
}/*** 测试用例执行函数* @param nums 测试数组* @param testName 测试用例名称*/
void runTest(vector<int>& nums, const string& testName)
{cout << "========== " << testName << " ==========\n";cout << "原始数组: ";if (nums.empty()) {cout << "（空数组）";}else {for (int num : nums)cout << num << " ";}cout << endl;insert_sort(nums); // 执行排序cout << "排序结果: ";if (nums.empty()) {cout << "（空数组）";}else {for (int num : nums)cout << num << " ";}cout << "\n\n";
}int main()
{// 测试用例定义vector<int> nums1 = {10, 7, 8, 9, 1, 5}; // 普通无序数组vector<int> nums2 = {1};                 // 单元素数组vector<int> nums3 = {};                  // 空数组vector<int> nums4 = {5, 5, 5, 5};        // 全相等元素数组vector<int> nums5 = {3, 1, 2, 4, 5};     // 部分有序数组vector<int> nums6 = {5, 4, 3, 2, 1};     // 完全逆序数组// 执行测试runTest(nums1, "普通数组");runTest(nums2, "单元素数组");runTest(nums3, "空数组");runTest(nums4, "全部相等的数组");runTest(nums5, "部分有序数组");runTest(nums6, "完全逆序数组");return 0;
}

运行结果

---

  四、冒泡排序

1、算法步骤

1. 遍历数组 ：从头开始，比较相邻元素。
2. 交换操作 ：如果前一个元素 > 后一个元素，交换两者。
3. 重复遍历 ：每一轮遍历后，最大的元素会被移动到末尾，下一轮可减少一次比较。
4. 提前终止 ：如果某次遍历没有发生交换，说明已有序，可提前结束排序。

2、代码实现

#include <iostream>
#include <vector>using namespace std;/*** @brief 冒泡排序算法实现** 通过重复遍历数组，比较相邻元素并在顺序错误时交换它们。* 每轮遍历将最大的元素"浮"到数组末尾，并通过优化标志提前终止有序数组的排序。** 时间复杂度：*   - 最坏/平均情况：O(n²)（完全逆序时）*   - 最好情况：O(n)（已有序时）* 空间复杂度：O(1)（原地排序）* 稳定性：稳定排序（相同元素相对位置不变）** @param nums 待排序的整型向量（引用传递，直接修改原数组）*/
void bubble_sort(vector<int>& nums)
{if (nums.empty() || nums.size() == 1)return;// 用与检查该次循环是否发生交换bool isSwap;for (int i = 0; i < nums.size() - 1; i++) {isSwap = false;// 每轮结束后都会将该轮最大的值排到最后// 那么，就没必要再比较最后 i 个元素for (int j = 0; j < nums.size() - i - 1; j++) {if (nums[j] > nums[j + 1]) {swap(nums[j], nums[j + 1]);isSwap = true;}}// 如果该轮循环没有交换// 代表数组已经有序，可以提前结束了if (!isSwap) {break;}}
}/*** 测试用例执行函数* @param nums 测试数组* @param testName 测试用例名称*/
void runTest(vector<int>& nums, const string& testName)
{cout << "========== " << testName << " ==========\n";cout << "原始数组: ";if (nums.empty()) {cout << "（空数组）";}else {for (int num : nums)cout << num << " ";}cout << endl;bubble_sort(nums); // 执行排序cout << "排序结果: ";if (nums.empty()) {cout << "（空数组）";}else {for (int num : nums)cout << num << " ";}cout << "\n\n";
}int main()
{// 测试用例定义vector<int> nums1 = {10, 7, 8, 9, 1, 5}; // 普通无序数组vector<int> nums2 = {1};                 // 单元素数组vector<int> nums3 = {};                  // 空数组vector<int> nums4 = {5, 5, 5, 5};        // 全相等元素数组vector<int> nums5 = {3, 1, 2, 4, 5};     // 部分有序数组vector<int> nums6 = {5, 4, 3, 2, 1};     // 完全逆序数组// 执行测试runTest(nums1, "普通数组");runTest(nums2, "单元素数组");runTest(nums3, "空数组");runTest(nums4, "全部相等的数组");runTest(nums5, "部分有序数组");runTest(nums6, "完全逆序数组");return 0;
}

运行结果 

---

 五、选择排序

1、算法步骤

1. 初始化 ：将数组视为未排序部分 。
2. 选择最小元素 ：从未排序部分中找到最小值。
3. 交换位置 ：将最小值与未排序部分的第一个元素交换，将其加入已排序部分。
4. 重复 ：缩小未排序范围，直到所有元素有序。

2、代码实现

#include <iostream>
#include <vector>using namespace std;/*** @brief 选择排序算法实现** 核心思想：每次从未排序部分选择最小元素，放到已排序序列的末尾。** 时间复杂度：O(n²)（所有情况下均为 O(n²)）* 空间复杂度：O(1)（原地排序）* 稳定性：不稳定（可能改变相等元素的相对位置）** @param nums 待排序的整型向量（引用传递，直接修改原数组）*/
void selection_sort(vector<int>& nums)
{// 处理空数组或单元素数组（无需排序）if (nums.empty() || nums.size() == 1) {return;}int n = nums.size();for (int i = 0; i < n - 1; i++) {int minIndex = i; // 初始化最小值索引为当前未排序部分的起始位置// 在未排序部分 [i+1, n-1] 寻找最小值的索引for (int j = i + 1; j < n; j++) {if (nums[j] < nums[minIndex]) {minIndex = j;}}// 将最小值交换到已排序部分的末尾（i 位置）swap(nums[i], nums[minIndex]);}
}/*** 测试用例执行函数* @param nums 测试数组* @param testName 测试用例名称*/
void runTest(vector<int>& nums, const string& testName)
{cout << "========== " << testName << " ==========\n";cout << "原始数组: ";if (nums.empty()) {cout << "（空数组）";}else {for (int num : nums)cout << num << " ";}cout << endl;selection_sort(nums); // 执行排序cout << "排序结果: ";if (nums.empty()) {cout << "（空数组）";}else {for (int num : nums)cout << num << " ";}cout << "\n\n";
}int main()
{// 测试用例定义vector<int> nums1 = {10, 7, 8, 9, 1, 5}; // 普通无序数组vector<int> nums2 = {1};                 // 单元素数组vector<int> nums3 = {};                  // 空数组vector<int> nums4 = {5, 5, 5, 5};        // 全相等元素数组vector<int> nums5 = {3, 1, 2, 4, 5};     // 部分有序数组vector<int> nums6 = {5, 4, 3, 2, 1};     // 完全逆序数组// 执行测试runTest(nums1, "普通数组");runTest(nums2, "单元素数组");runTest(nums3, "空数组");runTest(nums4, "全部相等的数组");runTest(nums5, "部分有序数组");runTest(nums6, "完全逆序数组");return 0;
}

运行结果