算法刷题打卡（1）—— 快速排序

算法刷题打卡（1）—— 快速排序

1.1 题目描述

给定你一个长度为 $n$ 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

1.1.1 输入格式

输入共两行，第一行包含整数 $n$。

第二行包含 $n$ 个整数（所有整数均在 $1\sim 10^9$ 范围内），表示整个数列。

1.1.2 输出格式

输出共一行，包含 $n$ 个整数，表示排好序的数列。

1.1.3 数据范围

$1\le n\le 100000$

1.1.4 输入样例：

5
3 1 2 4 5

1.1.5 输出样例：

1 2 3 4 5

1.2 分析过程

1.2.1 快速排序基本思想

快速排序是一种基于分治思想的高效排序算法，由Tony Hoare在1960年提出。它的核心思想可以概括为以下三步：

1. 分解（Partition）：从数组中选择一个元素作为"基准"（pivot），将数组分为两个子数组，使得左边子数组的元素都小于等于基准，右边子数组的元素都大于等于基准。
2. 递归排序：递归地对左右两个子数组进行快速排序。
3. 合并：由于是原地排序，不需要显式的合并操作。

1.2.2 三路快速排序优化

传统的快速排序是二路划分（小于pivot和大于pivot），而本题采用了更优的三路快速排序，将数组划分为三部分：

1. 小于pivot的部分
2. 等于pivot的部分
3. 大于pivot的部分

这种优化在处理包含大量重复元素的数组时特别有效，可以避免对相同元素的重复比较和交换。

当然可以，下面为你图解 partition 函数的核心流程，帮助你直观理解三路快排的执行过程。

三路快排 partition 图解

初始状态

假设有数组：

nums = [4, 5, 2, 4, 3, 4, 1],  left = 0, right = 6

我们随机选择一个 pivot（如 index = 3, pivot 值为 4），交换 nums[3] 和 nums[0]：

[4, 5, 2, 4, 3, 4, 1]
 ^                 ^ 
start           right

设：

• key = 4
• left 追踪 < key 的区域末端
• mid 当前正在访问的元素
• right 追踪 > key 的区域起始端

处理过程（每一步都基于当前 mid 所指向的值）

Step 1

• mid = 1, nums[1] = 5 > 4
  → 把 5 和 nums[right]（1）交换，然后 right--

[4, 1, 2, 4, 3, 4, 5]
    ^           ^ 
   mid         right

Step 2

• nums[1] = 1 < 4
  → left++ 然后与 mid 交换，同时 mid++

[4, 1, 2, 4, 3, 4, 5]
       ^        ^
     left      right

swap nums[1] 和 nums[1] （自己交换）

Step 3

• nums[2] = 2 < 4
  → left++, swap with mid（自己交换），mid++

[4, 1, 2, 4, 3, 4, 5]
          ^     ^
        left   right

Step 4

• nums[3] = 4 == 4
  → mid++ 无需处理

[4, 1, 2, 4, 3, 4, 5]
             ^  ^
           mid right

Step 5

• nums[4] = 3 < 4
  → left++, swap nums[4] with nums[4]（自己交换），mid++

[4, 1, 2, 4, 3, 4, 5]
                ^
               mid

Step 6

• nums[5] = 4 == 4
  → mid++

循环结束后（mid > right）

当前数组：

[4, 1, 2, 3, 4, 4, 5]
         ↑     ↑
       left   right

最后一步，把 pivot（nums[0]）与 nums[left] 交换：

swap(nums[left], nums[start])

得到：

[3, 1, 2, 4, 4, 4, 5]
         ↑     ↑
       left   right

返回的结果是 {left, right}：即 [3, 5] 是等于 key=4 的区间。

   < key           == key           > key
+----------+-------------------+------------+
|          |                   |            |
| nums[0..left-1]  nums[left..right]  nums[right+1..end]

每次递归只对 < key 和 > key 的部分进行处理，避免重复比较。

如果你需要动图或者在某一步打断点跟踪调试，我也可以继续帮你构建测试用例和打印调试点。

1.2.3 算法实现细节分析

1. 随机化pivot选择

const int index = (int) random() % (right - left + 1) + left;
swap(nums[index], nums[left]);
const int key = nums[left];

• 随机选择pivot可以避免在已排序或接近排序的数组上出现最坏情况O(n²)的时间复杂度
• 将选中的pivot交换到数组最左端，便于后续处理

2. 三路划分过程

while (mid <= right) {
    if (nums[mid] < key) {
        swap(nums[++left], nums[mid++]);
    } else if (nums[mid] > key) {
        swap(nums[mid], nums[right--]);
    } else {
        mid++;
    }
}

• left指针：标记小于key的区域的右边界
• right指针：标记大于key的区域的左边界
• mid指针：当前正在检查的元素

处理逻辑：

1. 当前元素小于key：交换到左区域，left和mid都右移
2. 当前元素大于key：交换到右区域，right左移
3. 当前元素等于key：不做交换，mid右移

3. 最终调整

swap(nums[left], nums[start]);

• 将最初放在最左端的pivot元素交换到等于key区域的起始位置

4. 递归处理

quick_sort(nums, left, p.first - 1);  // 处理小于key的部分
quick_sort(nums, p.second + 1, right); // 处理大于key的部分

• 跳过等于key的部分（p.first到p.second），因为它们已经在正确位置

1.2.4 复杂度分析

时间复杂度：

• 最佳/平均情况：O(nlogn)
• 最坏情况：O(n²)（通过随机化pivot选择几乎可以避免）

空间复杂度：

• 最佳情况：O(logn)（递归调用栈）
• 最坏情况：O(n)

1.2.5 为什么选择三路快排？

对于本题的输入特点：

1. 数据规模大（n ≤ 100000）需要高效算法
2. 元素范围广（1∼10⁹）但可能有重复元素
3. 三路快排能高效处理重复元素，减少不必要的递归调用

1.3 解题代码（终极最优回答 ）

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

// 三路快速排序的 partition 函数
// 将 nums[left..right] 区间划分为 <key、==key、>key 三部分
pair<int, int> partition(vector<int>& nums, int left, int right) {
   // 随机选择一个 pivot，避免最坏情况（退化为 O(n^2)）
   const int index = (int) random() % (right - left + 1) + left;
   swap(nums[index], nums[left]);  // 将 pivot 元素交换到最左边
   const int key = nums[left];     // 选定的划分值
   const int start = left;         // 保存最初的 left 位置
   int mid = start + 1;            // 当前遍历位置

   // left 用于追踪 < key 的边界
   // right 用于追踪 > key 的边界
   while (mid <= right) {
       if (nums[mid] < key) {
           // 小于 key，放到左边区域
           swap(nums[++left], nums[mid++]);
       } else if (nums[mid] > key) {
           // 大于 key，放到右边区域（注意 right-- 不移动 mid）
           swap(nums[mid], nums[right--]);
       } else {
           // 等于 key，不处理，mid 向右移动
           mid++;
       }
   }

   // 把 pivot 元素放到等于 key 的区间最左端
   swap(nums[left], nums[start]);

   // 返回等于 key 的区间起止位置：{left, right}
   return {left, right};
}

// 快速排序主函数：递归调用三路快排
void quick_sort(vector<int>& nums, int left, int right) {
   if (left < right) {
       auto p = partition(nums, left, right); // 划分
       quick_sort(nums, left, p.first - 1);   // 递归处理 < key 区间
       quick_sort(nums, p.second + 1, right); // 递归处理 > key 区间
   }
}

int main() {
   int n;
   scanf("%d", &n); // 输入数组大小
   vector<int> nums(n);

   // 输入数组元素
   for (int i = 0; i < n; i++) {
       scanf("%d", &nums[i]);
   }

   // 快速排序
   quick_sort(nums, 0, n - 1);

   // 输出排序结果
   for (const int num : nums) {
       printf("%d ", num);
   }
   return 0;
}

1.4 总结与思考

1.4.1 快速排序的核心要点

通过本题的实现，我们可以总结出快速排序的几个关键点：

1. 分治思想：快速排序完美体现了"分而治之"的算法思想，通过不断将问题分解为更小的子问题来解决。

2. 原地排序：快速排序只需要O(1)的额外空间（不考虑递归栈），是一种空间效率很高的排序算法。

3. 不稳定排序：由于元素的交换可能改变相同元素的相对位置，快速排序是不稳定的排序算法。

1.4.2 三路快排的优势

相比传统快速排序，三路快排具有以下优势：

1. 处理重复元素高效：当数组中存在大量重复元素时，三路快排能将这些元素集中处理，避免重复比较和交换。

2. 减少递归深度：通过将等于pivot的元素单独处理，减少了需要递归处理的子数组规模。

3. 实际性能更优：在大多数实际应用场景下，三路快排比传统快排表现更好。

1.4.3 算法选择思考

在实际工程应用中，一般我们就直接选择使用快速排序即可，一般情况下无需纠结。

但是在回答面试官的提问时，选择排序算法时需要综合考虑：

1. 数据规模：小规模数据可能更适合简单排序（如插入排序）
2. 数据特性：是否基本有序、是否有大量重复元素等
3. 稳定性要求：是否需要保持相同元素的相对顺序
4. 空间限制：是否有严格的空间复杂度要求

部分内容已经借助大模型进行整理，若存在疑问欢迎评论 ~

Smileyan
2025.07.03 23:46