如何在快排算法中实现medianOf3

Question

我正在尝试用快速排序算法实现这个 medianOf3 方法；但是，我所做的一切都没有用。我知道我的快速排序方法正在运行，但是我的分区方法无法正确分区，如果有人对使用我的快速排序算法实施此 medianOf3 方法有任何建议，那将非常有帮助。此外，我确实包含了 、, 和 include 。我添加了 using std::swap;并使用命名空间标准；以及。

template<typename T> inline
int medianOf3(T A[], int l, int r){
        //this is overcommented... also, try and avoid using pointers
        T* a = A + l;//array name is just pointer to 1st (0 index) elem., + l shifts l*(T size)
        T* b = A + l + (r-l)/2;//middle item... int division rounds down
        T* c = A + r;

        //when a is a pointer, *a is the dereference operator (gives value a points to)
        T* m;
        if(*a < *b){
                if(*b < *c) m=b;
                else if(*c < *a) m=a;
                else m=c;
        } else{ //b <=a8
                if(*a < *c) m=a;
                else if(*c < *b) m=b;
                else m=c;
        }
        return m-A; //m-A is the number of elements from A[0]

}
int partition(int a[], int l, int r){
    int s = medianOf3(a, l, r);
    swap(a[l], s);
    int p = a[l];
    int i = l; 
    int j = r;
    while(i<j){
        do{
            i=i+1;
        }while(a[i]<=p);
        do{
            j=j-1;
        }while(a[j]>p);
        if (i<j)
            swap(a[i], a[j]);
    }
    swap(a[l], a[j]);
    return j;
}
void quickSort(int arr[], int l, int r){
    if (l < r){
        int p = partition(arr, l, r);
        quickSort(arr, l, p - 1);
        quickSort(arr, p + 1, r);
    }
}

Answer 1

partition()

是实现Hoare分区方案的尝试，但也存在一些问题。这是一个工作示例：

void QuickSort(int a[], int lo, int hi)
{
    if(lo >= hi)                        // return if nothing to do
        return;
    int md = lo+(hi-lo)/2;              // median of 3
    if(a[lo] > a[hi])
        std::swap(a[lo], a[hi]);
    if(a[lo] > a[md])
        std::swap(a[lo], a[md]);
    if(a[md] > a[hi])
        std::swap(a[md], a[hi]);
    int p = a[md];                      // Hoare partition
    int i = lo - 1;
    int j = hi + 1;
    while (1){
        while (a[++i] < p);
        while (a[--j] > p);
        if (i >= j)
            break;
        std::swap(a[i], a[j]);
    }
    QuickSort(a, lo, j);                // recurse
    QuickSort(a, j+1, hi);
}