C随机主元快速排序（改进配分函数）

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++;
        }
    }
}

Answer 1

这是《算法导论》partition()中的伪代码，被称为 Lomuto 的分区算法，书中下面有很好的解释。

\n\n

PARTITION(A, p, r)\n1 x \xe2\x86\x90 A[r]\n2 i \xe2\x86\x90 p - 1\n3 for j \xe2\x86\x90 p to r - 1\n4   do if A[j] \xe2\x89\xa4 x\n5       then i \xe2\x86\x90i + 1\n6           exchange A[i] \xe2\x86\x94 A[j]\n7 exchange A[i + 1] \xe2\x86\x94 A[r]\n8 return i +1\n

\n\n

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

\n\n

// srand(time(NULL));\nint partition(int* arr, int start, int end)\n{\n    int pivot_index = start + rand() % (end - start + 1);\n    int pivot = arr[pivot_index ];\n\n    swap(&arr[pivot_index ], &arr[end]); // swap random pivot to end.\n    pivot_index = end;\n    int i = start -1;\n\n    for(int j = start; j <= end - 1; j++)\n    {\n        if(arr[j] <= pivot)\n        {\n            i++;\n            swap(&arr[i], &arr[j]);\n        }\n    }\n    swap(&arr[i + 1], &arr[pivot_index]); // place the pivot to right place\n\n    return i + 1;\n}\n

\n\n

书中还提到了另一种划分方法，称为Hoare's Partitioning Algorithm，伪代码如下：

\n\n

Hoare-Partition(A, p, r)\nx = A[p]\ni = p - 1\nj = r + 1\nwhile true\n    repeat\n        j = j - 1\n    until A[j] <= x\n    repeat\n        i = i + 1\n    until A[i] >= x\n    if i < j\n        swap( A[i], A[j] )\n    else\n        return j\n

\n\n

分区后，A[p...j] \xe2\x89\xa4 中的每个元素 A[j+1...r] 中的每个元素。所以快速排序是：

\n\n

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

\n