C ++快速排序枢纽优化 [英] C++ QuickSort Pivot Optimization

问题描述

目前，我有一个准系统实现快速排序算法的一些随机生成的数字排序。排序是有效率的，比归并排序。然而，对于特定数量的集（例如逆转需要被排序的其他方式的数字），我需要优化枢轴

Currently, I have a barebones implementation of the quicksort algorithm to sort some randomly generated numbers. The sort is efficient, more so than merge sort. However, for specific number sets (e.g. reversed numbers that need to be sorted the other way around), I need to optimized the pivot.

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

因此​​，对于这个code，我不是想用一个随机数作为支点的分区步骤，或使用的第一，中位数，和最后一个元素作为支点。

So for this code, I either want to use a random number as the pivot for the partitioning step, or use the median of the first, middle, and last elements as the pivot.

我将如何做到这一点？

我是新的排序算法，以及我对他们的了解是不完整的，只是还没有。

I'm new to sorting algorithms, and my understanding of them is not complete just yet.

推荐答案

只要改变这些行：

    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个指针，并返回一个指针的意思。

where mean_of_three take 3 pointers and returns a pointer to the mean.

这篇关于C ++快速排序枢纽优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！