快速排序 几种划分方法讨论

发表于 分类于 阅读次数： Waline： 本文字数： 2.1k

最近在复习数据结构与算法，聊聊快速排序的几种划分算法。

快速排序思路

快速排序是一种基于分治策略的排序算法。

对于待排序数组，其核心操作是：

  1. 选取一个基准数pivot
  2. 将数组分为两块，一块小于等于基准数，另一块大于等于基准数（注意 基准数作为分界点）
  3. 递归地对于分出来的两个数字再次进行快速排序

不断地进行划分，递归，最后能保证整个数组有序。

基准数的选取

一般来说，基准数有几种选取方法：

  1. 选取第一个数或者最后一个数：这样做，如果数组已经排好序，则每次划分都是基准数和剩余数，时间复杂度升至O(n^2)
  2. 随机选择一个数
  3. 选取中位数：这样做始终能对原数组进行等分，寻找中位数是线性时间的。

下面以最无脑的方法1为例。

几种划分方法

主要的划分方法有：

  1. 朴素划分
  2. Lomuto 划分
  3. Hoare 划分

中国大陆教材中经常出现的是第三种，即 Hoare 划分，也叫哨兵划分。

朴素划分

思路很无脑。直接开一个新数组，把比 pivot 小的放左边，比 pivot 大的放右边，最后把数组拷贝回到原数组。需要 O(n) 的额外空间。

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
const int N; // 数组长度
int A[N];
int tmp[N];
int Native_Partition(int left, int right) {
    int pivot = A[left];

    int idx = left;

    for (int i = left; i <= right; i++) {
        if (A[i] < pivot)
            tmp[idx++] = A[i];
    }  // 先将小于等于 pivot 的复制进入

    int pid = idx;
    tmp[idx++] = pivot;

    for (int i = left; i <= right; i++) {
        if (A[i] > pivot)
            tmp[idx++] = A[i];
    }  // 再将大于 pivot 的复制进入

    for (int i = left; i <= right; i++) {
        A[i] = tmp[i];
    } // 复制回到 A

    return pid;
}

Lomuto 划分

Lomuto 划分即使用单个指针，从左到右扫描数组，交换，维持划分顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int Lomuto_Partition(int left, int right) {
    int pivot = A[right];
  
    int i = left - 1; // 维护的划分中最右侧的比 pivot 小的元素的下标

    // 遍历数组，把所有比 pivot 小的元素全部移动到左边
    for (int j = left; j <= right - 1; j++) {  // 遍历到 right - 1 可以对 pivot 进行保护，使得 pivot 不与自己对比，使逻辑更清晰，但或许没必要
        if (A[j] < pivot) {
            i++;
            swap(A[i], A[j]);
        } // j 维护的是遍历时下标，当发现一个比 pivot 小的数时，如果 i + 1 == j 则不动，否则说明之前存在一个数比 `pivot` 大需要交换，则及时进行交换
    }
    
    // 把 pivot 移回来
    swap(A[i + 1], A[right]);  
    return i + 1;
}

Hoare 划分

Hoare 划分采用双指针，进行交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Hoare_Partition(int left, int right) {
    int pivot = A[left];
    int pid = left;
    while (left < right) {
        while (left < right && A[right] >= pivot) {
            right--;
        } // 先从右往左扫描，保护 pivot
        while (left < right && A[left] <= pivot) {
            left++;
        } // 再从左往右扫描
        swap(A[left], A[right]); // 交换不正确的数
    }
    // 跳出循环时，left = right 说明找到了 pivot 的位置
    swap(A[pid], A[left]);
    return pid;
}

扫描顺序对于结果有影响。pivot 在最左边时，应该先从右往左扫描。

如果先从左往右扫，找第一个大于 pivot 的数 a，而第一个小于 pivot 的数在 a 左侧，此时进行 pivot 和 A[left] 的交换，会导致交换错误。故应该优先保证 pivot 左侧都小于等于 pivot，即先寻找第一个小于 pivot 的数，这样交换是安全的。

快速排序算法

对于某划分函数 partition(int st, int end) -> pivot: int 有

1
2
3
4
5
6
7
8
9
10
11
12
const int N; // 数组长度
int A[N]; // 待排序数组

void qsort(int st, int end){
    if(st >= end) return; // 递归终止条件

    int pivot = partition(st, end);

    // 递归
    qsort(st, pivot-1);
    qsort(pivot+1, end);
}