快速排序的最早划分方法：Hoare划分

116 阅读 0 评论 77 点赞

我是靠谱客的博主奋斗乌龟，这篇文章主要介绍快速排序的最早划分方法：Hoare划分，现在分享给大家，希望可以做个参考。

快速排序的划分过程最早由C.R.Hoare设计，伪代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
HOARE-PARTITION(A,p,r)
x=A[p]
i=p-1
j=r+1
while TRUE
    repeat
        j=j-1
    until A[j]<=x
    repeat
        i=i+1
    until A[i]>=x
    if i < j
        exchange A[i] with A[j]
    else
        return j

易知，
1. 下标i和j不会访问超出数组以外的元素。
2. 当HOARE-PATITION结束时，返回的j的值满足 $ple j lt r$ 。
3. 当HOARE-PATITION结束时，A[p..j]中每一个元素都小于或等于A[j+1..r]中的元素。

算法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
int hoare_partition(int *source, int head, int tail) {
    int x = source[head];
    int i = head - 1;
    int j = tail + 1;
    while (1) {
        do {
            j--;
        } while (source[j] > x);
        do {
            i++;
        } while (source[i] < x);
        if (i < j) {
            swap(source + i, source + j);
        } else return j;
    }
}

void hoare_quick_sort(int *source, int head, int tail) {
    if (head >= tail)
        return;
    int mid = hoare_partition(source, head, tail);
    hoare_quick_sort(source, head, mid);
    hoare_quick_sort(source, mid + 1, tail);
}