如何在快速排序算法中实现 medianOf3-解网

问：

我正在尝试使用快速排序算法实现此 medianOf3 方法;但是，我所做的一切都不起作用。我知道我的快速排序方法正在工作，但是我的分区方法无法正确分区，如果有人对使用我的快速排序算法实现此 medianOf3 方法有任何建议，那将是非常有帮助的。此外，我还包含了 <bits/stdc++.h>、、和包括 .我使用 std：：swap 添加;并使用命名空间 std;也。

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

C++ Linux 函数模板快速排序

当您使用调试器运行此代码时，您看到了什么？这就是调试器的用途，如果您不知道如何使用它，这是一个很好的机会，可以学习在调试器中一次运行一行程序，监视所有变量及其值的变化，并分析程序的逻辑和执行。您应该可以使用调试器来查找您编写的这个程序和所有未来程序中的所有简单问题，所有这些都是自己完成的。你知道如何使用调试器吗？了解如何有效地使用调试器是每个 C++ 开发人员的必备技能。

0赞 teapot418 3/21/2023

那么什么是回报呢？它是一个索引还是正在排序的数字之一？选择一个。medianOf3return m-Aswap(a[l], s);

答：

0赞 rcgldr 3/21/2023 #1

partition()是实现 Hoare 分区方案的尝试，但存在一些问题。下面是一个工作示例：

int medianof3(int a[], int lo, int hi)
{
    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]);
    return md;
}

int partition(int a[], int lo, int hi)
{
    int md = medianof3(a, lo, hi);      // median of 3
    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]);
    }
    return j;                           // return index to split point
}

void quicksort(int a[], int lo, int hi)
{
    if(lo >= hi)                        // return if nothing to do
        return;
    int s = partition(a, lo, hi);       // partition
    quicksort(a, lo, s);                // recurse
    quicksort(a, s+1, hi);
}

所有这些都可以包含在快速排序功能中

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

上一个：当专用化位于不同的标头中时出现 C++ 模板函数专用化错误

下一个：似乎没有任何参数时参数不匹配

如何在快速排序算法中实现 medianOf3

How to implement medianOf3 in quicksort algorithm

评论