C随机化pivot快速排序（改进分区函数）

Question

我是一名计算机科学专业的学生（刚开始学习），我正在尝试将伪代码转换为快速排序的随机枢轴版本。我已经编写并测试了它，一切都运行得非常完美，但是...

分区部分看起来有点复杂，感觉可能漏掉了什么或者想得太多了。我无法确定它是否正确或者是否犯了可避免的错误。

长话短说：它可以工作，但如何更好地实现呢？

非常感谢您提供的所有帮助。

void partition(int a[],int start,int end)
{
    srand (time(NULL));
    int pivotpos = 3;   //start + rand() % (end-start);
    int i = start;    // index 1
    int j = end;      // index 2
    int flag = 1;
    int pivot = a[pivotpos];   // sets the pivot's value
    while(i<j && flag)      // main loop
    {
        flag = 0;
        while (a[i]<pivot)
        {
            i++;
        }
        while (a[j]>pivot)
        {
            j--;
        }
        if(a[i]>a[j]) // swap && sets new pivot, and restores the flag
        {
            swap(&a[i],&a[j]);
            if(pivotpos == i)
                pivotpos = j;
            else if(pivotpos == j)
                pivotpos = i;
            flag++;
        }
        else if(a[i] == a[j])       // avoids getting suck on a mirror of values (fx pivot on pos 3 of : 1-0-0-1-1)
        {
            if(pivotpos == i) 
                j--;
            else if(pivotpos == j)
                i++;
            else
            {
                i++;
                j--;
            }
            flag++;
        }
    }
}

- user3236524

---

随机选择枢轴的代码在哪里？ - jfly

@jfly int pivotpos = 3;（由公平的骰子掷出选择） - user2864740

请查看此链接：http://p2p.wrox.com/visual-c/66347-quick-sort-c-code.html - user2864740

为什么不使用样本的中位数，例如中位数法（取第一个、中间和最后一个；将它们排序，选择新的中间值作为枢轴。具有为分区提供自然哨兵的优点）？请查看Bentely和McIllroy的“工程排序函数”，Software：Practice and Experience 23:11（1993年11月），pp.1249-1265。 - vonbrand

Answer 1

这是《算法导论》中称为 Lomuto 分区算法的 partition() 伪代码，书中对它有很好的解释。 Introduction to Algorithms

PARTITION(A, p, r)
1 x ← A[r]
2 i ← p - 1
3 for j ← p to r - 1
4   do if A[j] ≤ x
5       then i ←i + 1
6           exchange A[i] ↔ A[j]
7 exchange A[i + 1] ↔ A[r]
8 return i +1

您可以根据上面的伪代码轻松实现基于随机分区的实现。正如评论所指出的那样，将srand()移出partition函数。

// srand(time(NULL));
int partition(int* arr, int start, int end)
{
    int pivot_index = start + rand() % (end - start + 1);
    int pivot = arr[pivot_index ];

    swap(&arr[pivot_index ], &arr[end]); // swap random pivot to end.
    pivot_index = end;
    int i = start -1;

    for(int j = start; j <= end - 1; j++)
    {
        if(arr[j] <= pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[pivot_index]); // place the pivot to right place

    return i + 1;
}

这本书中还提到了另一种分区方法，称为Hoare的分区算法，其伪代码如下：

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
        swap( A[i], A[j] )
    else
        return j

在分区后，A[p...j] 中的每个元素都 ≤ A[j+1...r] 中的每个元素。因此，快速排序应该是这样的：

QUICKSORT (A, p, r)
if p < r then
 q = Hoare-Partition(A, p, r)
 QUICKSORT(A, p, q)
 QUICKSORT(A, q+1, r)

- jfly

---

在快速排序算法中使用的分区函数中，不应包含srand()。原句已经是否定了srand()的使用。 - WhozCraig

Hoare的分区更高效（数据移动更少）。 - vonbrand

@RestlessC0bra 在交换之后，我将 end 赋值给 pivot_index，所以现在 a[pivot_index] 是随机的。 - jfly

Answer 2

有多种方法可以对快速排序进行分区，以下是我能想到的最简单的方法。通常有两种分区方式：

1. 挤压法：将序列的两端都压缩，直到找到适当的交换对，然后将两个元素交换到分区的正确位置。实现起来并不容易，但比另一种方法更高效（交换次数更少）……

2. 扫描法：使用从左到右（或从右到左）的单向扫描值，将值交换到一个递增的枢轴索引中，该索引随着算法运行而移动。非常容易实现，如下所示。

我更喜欢扫描法，因为它对于学习快速排序和分区的人来说非常简单。两种方法都可以实现原地分区，在下面的实现中也是如此。除了在swap()函数中，您不会看到任何时候存储在临时存储器中的值。

随机选择枢轴只是其中的一部分。以下显示了如何初始化随机数生成器，并演示了可能是您要找到的最简单的分区算法和快速排序使用方法。

它还显示，C/C++中不需要分区的两端，因为可以使用简单的指针算术来调整分区的“顶部”半部分。请参见quicksort()函数，了解如何实现此功能。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int *lhs, int *rhs)
{
    if (lhs == rhs)
        return;

    int tmp = *lhs;
    *lhs = *rhs;
    *rhs = tmp;
}

int partition(int ar[], int len)
{
    int i, pvt=0;

    // swap random slot selection to end.
    //  ar[len-1] will hold the pivot value.
    swap(ar + (rand() % len), ar+(len-1));
    for (i=0; i<len; ++i)
    {
        if (ar[i] < ar[len-1])
            swap(ar + i, ar + pvt++);
    }

    // swap the pivot value into position
    swap(ar+pvt, ar+(len-1));
    return pvt;
}

void quicksort(int ar[], int len)
{
    if (len < 2)
        return;

    int pvt = partition(ar, len);
    quicksort(ar, pvt++); // note increment. skips pivot slot
    quicksort(ar+pvt, len-pvt);
}


int main()
{
    srand((unsigned int)time(NULL));

    const int N = 20;
    int data[N];

    for (int i=0; i<N; ++i)
    {
        data[i] = rand() % 50 + 1;
        printf("%d ", data[i]);
    }
    puts("");

    quicksort(data, N);

    for (int i=0; i<N; ++i)
        printf("%d ", data[i]);

    puts("");

    return 0;
}

输出（显然会有所不同）

32 49 42 49 5 18 41 48 22 33 40 27 12 47 41 6 50 27 8 7 
5 6 7 8 12 18 22 27 27 32 33 40 41 41 42 47 48 49 49 50 

注意：这不考虑使用 rand() % len 时可能存在的取模偏差，但对于此示例来说，这实际上是过度处理了。如果它很关键，我会完全使用另一个生成器。有一个 杰出的 讨论关于如何选择快速排序分区的随机枢轴位置的方法，可以在此站点的这篇文章中找到 （链接），其中包含许多不同方法的链接。建议先阅读一下。

- WhozCraig