快速排序 - Biscuitの赛博小窝

Biscuit

哈基米，你要大步大步地走下去啊，不行，要悠哒悠哒才能欣赏到沿途的风景。

公告

欢迎来到我的博客喵。

了解更多

483 字

2 分钟

快速排序

2025-12-05

数据结构与算法

排序

【数据结构合集 - 快速排序(算法过程, 效率分析, 稳定性分析)】 https://www.bilibili.com/video/BV1y4421Z7hK/?share_source=copy_web&vd_source=508f9008633ddcfb01e9adad004516c4

快速排序算法原理#

分治。

选一个基准值pivot，把数组分成两部分，一部分比pivot小，另一部分比pivot大，然后递归排序这两部分，最后合并。

算法步骤#

从数组中选择一个基准值 pivot。
left指针从左向右扫描，right指针从右向左扫描。如果 left 指向的元素小于等于 pivot，则left,right元素交换， left 右移；如果 right 指向的元素大于等于 pivot，则left,right元素交换， right 左移。
重复上述过程，直到 left 和 right 指针相遇。此时，pivot 放到 left 指针位置，完成一次划分。

注意，此时pivot位置的元素已经归位，不再参与后续排序。
递归地对 pivot 左右两部分进行快速排序，直到子数组长度为1或0。

代码实现#

1
int partition(array<int, 5>& arr, int low, int high) {
2
    int pivot = arr[low]; // 选择基准值
3
    int left = low;
4
    int right = high;
5
    while (left < right) {
6
        // 从右向左找第一个小于 pivot 的元素
7
        while (left < right && arr[right] >= pivot) {
8
            right--;
9
        }
10
        // 从左向右找第一个大于等于 pivot 的元素
11
        while (left < right && arr[left] <= pivot) {
12
            left++;
13
        }
14
        if (left < right) {
15
            swap(arr[left], arr[right]); // 交换
16
        }
17
    }
18
    // 将 pivot 放到正确位置
19
    swap(arr[low], arr[left]);
20
    return left; // 返回 pivot 的位置
21
}
22

23
void quickSort(array<int, 5>& arr, int low, int high) {
24
    if (low < high) {
25
        int pivotIndex = partition(arr, low, high); // 划分
26
        quickSort(arr, low, pivotIndex - 1);  // 递归排序左半部分
27
        quickSort(arr, pivotIndex + 1, high); // 递归排序右半部分
28
    }
29
}