0

目前，我有一个快速排序算法的准系统实现来对一些随机生成的数字进行排序。排序是有效的，比归并排序更有效。但是，对于特定的数字集（例如需要反向排序的反转数字），我需要优化枢轴。

int* partition (int* first, int* last);
void quickSort(int* first, int* last) {
    if (last - first <= 1) return;

    int* pivot = partition(first, last);
    quickSort(first, pivot);
    quickSort(pivot + 1, last);
}

int* partition (int* first, int* last) {
    int pivot = *(last - 1);
    int* i = first;
    int* j = last - 1;

    for (;;) {
        while (*i < pivot && i < last) i++;
        while (*j >= pivot && j > first) j--;
        if (i >= j) break;
        swap (*i, *j);
    }

    swap (*(last - 1), *i);

    return i;
}

因此，对于这段代码，我要么使用随机数作为分区步骤的基准，要么使用第一个、中间和最后一个元素的中值作为基准。

我该怎么做？

我是排序算法的新手，我对它们的理解还不完整。

4

3 回答 3

2

只需更改以下几行：

    int pivot = *(last - 1);
    …
    swap ((last - 1), i);

类似于：

    int* pos = (first + rand(last - first));
    int pivot = *pos;
    …
    swap (pos, i);

或者

    int* pos = mean_of_three((last - 1), (first), ((first + last) / 2));
    int pivot = *pos;
    …
    swap (pos, i);

其中mean_of_three取 3 个指针并返回一个指向平均值的指针。

于 2012-05-23T06:03:32.073 回答
2

正如您已经提到的，选择数组的第一个或最后一个元素作为枢轴不是最佳做法，并且会导致算法陷入 O(n^2)。枢轴选择算法的最佳选择取决于您的程序可能遇到的数据。如果数据有可能被排序或接近排序，那么随机枢轴是一个非常好的选择（并且非常容易实现）以避免 O(n^2) 行为。另一方面，选择中间元素而不是第一个元素的开销是最小的，并且提供了非常有效的针对排序数据的保护。

再说一次，如果您确信您的数据不会被排序或接近排序，那么中位数的三个分区策略似乎是最好的。

int PickPivotUsingMedian(int a[], int first, int last)
{
int mid = (first+ right)/2;
if (a[mid ] < a[first]) 
    swap(&a[first],&a[mid ]);
if (a[last] < a[first])
    swap(&a[first],&a[last]);
if (a[last]< a[mid ])
    swap(&a[mid ],&a[last]);

swap(&a[mid], &a[last - 1]);//since the largest is already in the right.
return a[last - 1];
}
于 2012-05-23T06:03:47.550 回答
1

在数组范围内选择一个随机索引并将该元素用作枢轴。

于 2012-05-23T05:58:59.177 回答