Hoare 分区如何在 QuickSort 中工作？

Question

这是直接来自书本 (CORMEN) 的伪代码：

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
                SWAP A[i] <=> A[j]
            else return j

这是 C++ 中的代码：

#include<bits/stdc++.h>
using namespace std;


int partition(int a[], int low, int high)
{
    int pivot = a[low];
    int i = low - 1;
    int j = high + 1;
    while (1)
    {
        do {
            i++;
        } while (a[i] < pivot);

        do {
            j--;
        } while (a[j] > pivot);

        if (i >= j) {
            cout<<j<<endl;
            return j;

        }

        swap(a[i], a[j]);
    }
}


/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
        at right place*/
        int pi = partition(arr, low, high);

        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver program to test above functions
int main()
{
    int arr[] = {7,3,2,6,4,1,3,5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"partition:\n";
    partition(arr,0,7);
    printArray(arr, n);

    quickSort(arr, 0, n-1);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

如果我在输入中使用这个数组：

[5,3,2,6,4,1,3,7]

逻辑上一切正常，因为分区 return 数组将是：

[3,3,2,1,4,6,5,7]

终止 i=5 和 j=4 所以我的主元是 4。4 左边的所有元素都是次要的，右边的都是主要的

现在如果我在输入中使用这个数组：

[7,3,2,6,4,1,3,5]

我在分区的最后会有这种情况

[5,3,2,6,4,1,3,7]

这对我来说 return 是枢轴 j = 6，即 3。现在 3 左边的元素并不都是次要的，右边的元素都是主要的。 但这怎么可能有效呢？我不应该把元素放在主次要的左边和主要的右边吗？

Answer 1

使用 Hoare 分区，主元和等于主元的值可以在任何地方结束。返回的索引不是枢轴的索引，而只是一个分隔符。对于上面的代码，当分区完成后，elements <= pivot 将在 j 或左侧，而 elements >= pivot 将在 j 右侧。做一个分割步骤后，C++代码应该是：

        quickSort(arr, low, pi);           // not pi - 1
        quickSort(arr, pi + 1, high);

包含快速排序测试的示例代码：

uint32_t Rnd32()
{
static uint32_t r = 0;
    r = r*1664525 + 1013904223;
    return r;
}

int Partition(int ar[], int lo, int hi)
{
    int pv = ar[lo+(hi-lo)/2];
    int i = lo - 1;
    int j = hi + 1;
    while(1){
        while(ar[++i] < pv);
        while(ar[--j] > pv);
        if(i >= j)
            return j;
        std::swap(ar[i], ar[j]);
    }
}

void QuickSort(int ar[], int lo, int hi)
{
    while (lo < hi){
        int pi = Partition(ar, lo, hi);
        if((pi - lo) < (pi - hi)){
            QuickSort(ar, lo, pi);
            lo = pi + 1;
        } else {
            QuickSort(ar, pi + 1, hi);
            hi = pi;
        }
    }
}

#define COUNT (16*1024*1024)

int main(int argc, char**argv)
{
    size_t i;
    int * ar = new int [COUNT];
    for(i = 0; i < COUNT; i++){
        ar[i] = Rnd32();
    }

    QuickSort(ar, 0, COUNT-1);

    for(i = 1; i < COUNT; i++)
        if(ar[i-1] > ar[i])
            break;
    if(i == COUNT)
        std::cout << "passed" << std::endl;
    else
        std::cout << "failed" << std::endl;

    delete[] ar;

    return(0);
}

Hoare 分区如何在 QuickSort 中工作？

How does Hoare partitioning work in QuickSort?

c++

sorting

quicksort

partitioning