sinat_35988648
dpwqb
采纳率33.3%
2019-10-07 17:29

如何实现以平均值为界值的快速排序算法?

5
已采纳

【问题】快速排序算法中,如何选取一个界值(又称为轴元素),影响着快速排序的效率,而且界值也并不一定是被排序列中的一个元素。例如,我们可以用被排序列中所有元素的平均值作为界值。编写算法**_实现以平均值为界值的快速排序方法_**。 【石油大学 1998 五 (18 分)】

下面附带有书本及网络所流传的一种解答:

int partition (RecType r[],int l,h)
{ int i=l,j=h,avg=0;
for(;i<=h;i++) avg+=R[i].key;
i=l; avg=avg/(h-l+1);
while (i<j)
{ while (i<j &&R[j].key>=avg) j--;
if (i<j) R[i]=R[j];**//注意这里可能会把第一个R[i]覆盖掉**
while (i<j &&R[i].key<=avg) i++;
if (i<j) R[j]=R[i];
}
if(R[i].key<=avg) return i; else return i-1;
}
void quicksort (RecType R[],int S,T);
{if (S<T)
{k=partition (R,S,T);
quicksart (R,S,k);
quicksart (R,k+1,T);}
}

我实现了该算法,但很明显有错误,因为在排序过程存在数据丢失,**最后应该需要确定一个最终位置,但这个最终位置应该是那个第一个被覆盖掉的元素**,所以正确的解决办法应该是什么呢?

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

2条回答

  • caozhy 回答这么多问题就耍赖把我的积分一笔勾销了 2年前

    你的代码太乱,根本不能运行,我把分区的代码重新写了一下

    作为程序员,我们只讨论可以运行的代码,不讨论书本上根本不通的东西。

    #include <stdio.h>
    
    typedef union
    { int key; } RecType;
    
    /*
    int partition (RecType R[],int l,int h)
    { int i=l,j=h,avg=0;
    for(;i<=h;i++) avg+=R[i].key;
    i=l; avg=avg/(h-l+1);
    while (i<j)
    { while (i<j &&R[j].key>=avg) j--;
    if (i<j) { int t = R[i].key; R[i].key = R[j].key; R[j].key = t; }//注意这里可能会把第一个R[i]覆盖掉**
    while (i<j &&R[i].key<=avg) i++;
    if (i<j){ int t = R[i].key; R[i].key = R[j].key; R[j].key = t; }
    }
    if(R[i].key<=avg) return i; else return i-1;
    }
    
    */
    
    int partition (RecType R[],int l,int h)
    {
        int i=l,avg=0;
        for(;i<=h;i++) 
            avg+=R[i].key;
        avg=avg/(h-l+1);
        int pivot = R[h].key;
        i = l - 1;
        for (int j = l; j <= h- 1; j++)
        {
            if (R[j].key <= pivot)
            {
                i++;
                int t = R[i].key; R[i].key = R[j].key; R[j].key = t;
            }
        }
        int t = R[i+1].key; R[i+1].key = R[h].key; R[h].key = t;
        return (i + 1);
    }
    
    void quicksort (RecType R[],int S,int T)
    {
        if (S<T)
        {
            int k=partition (R,S,T);
            quicksort (R,S,k-1);
            quicksort (R,k+1,T);
        }
    }
    
    int main()
    {
        RecType arr[] = { {14}, {7}, {8}, {12}, {5}, {3}, {9}, {3}, {19}, {1} };
        int i;
        quicksort(arr, 0, sizeof(arr) / 4 - 1);
        for (i = 0; i < sizeof(arr) / 4 - 1; i++)
            printf("%d ", arr[i].key);
        return 0;
    }
    

    之前的程序有点问题,修改下

    #include <stdio.h>
    
    typedef union
    { int key; } RecType;
    
    int partition (RecType R[],int l,int h)
    {
        int i=l,avg=0;
        int j = h;
        for(;i<=h;i++) 
            avg+=R[i].key;
        avg=avg/(h-l+1);
        i = l;
        j = h;
        while(i<j){
            while(R[i].key<avg&&i<=j)  ++i;
            while(R[j].key>avg&&i<=j)  --j;
            if(i<j)
            { 
                int t = R[i].key; R[i].key = R[j].key; R[j].key = t;
                i++;
                j--;
            }
    
        }
        return j;
    }
    
    void quicksort (RecType R[],int S,int T)
    {
        if (S<T)
        {
            int k=partition (R,S,T);
            quicksort (R,S,k);
            quicksort (R,k+1,T);
        }
    }
    
    int main()
    {
        RecType arr[] = { {14}, {7}, {8}, {12}, {5}, {3}, {9}, {3}, {19}, {1} };
        int i;
        quicksort(arr, 0, sizeof(arr) / 4 - 1);
        for (i = 0; i < sizeof(arr) / 4; i++)
            printf("%d ", arr[i].key);
        return 0;
    }
    

    1 3 3 5 7 8 9 12 14 19

    点赞 3 评论 复制链接分享
  • JonathanYan JonathanYan 2年前

    R[i]=R[j] 替换成 swap(R[i], R[j]) 交换函数自己实现
    比如
    1 2 3 4 5 6 7 8 9, Avg=5
    的一个乱序
    1 4 3 6 5 7 2 8 9
    ^----------^
    i-----------j
    第一次替换发生在这个情况,结果是
    2 4 3 6 5 7 1 8 9
    -------^----^
    -------i------j
    那么在运行到这个情况后1还会再换回来,变成
    2 4 3 1 5 7 6 8 9
    ------^
    ------ij
    最终变成这个情况,而下面这种情况就是"错误"的变成了“正确”的
    1 5 3 4 2 6 7 8 9
    ^------^
    i-------j
    i和j互换后虽然操作看似错误,但剩下的数已经有序,就反而是正确的了。
    这个程序一左一右的方法就是避免额外的处理"错误"情况的代码。

    #include <iostream>
    
    using namespace std;
    
    struct RecType{
        int key;
    };
    
    int swap( int &a, int &b ){
        int c = a;
        a = b;
        b = c;
    }
    
    int partition (RecType R[],int l, int h, int n) { 
        int avg = 0;
        for( int i = l; i < h; i++ ) 
            avg += R[i].key;
    
        int i = l, j = h - 1;
        avg = avg/(h - l);
    
        while ( i < j ) { 
            while ( i < j && R[j].key > avg ) 
                j--;
            if ( i < j ) {
                cout << "   Lower : ";
                for( int t = 0; t < n; t++ )
                    cout << (t==l?"(":(t==h?")":" ")) << R[t].key << ((t==i||t==j) ? "<" : " ");
                cout << (h==n?")":"") << endl;
    
                swap(R[i], R[j]);
                i++;
            }
    
            while ( i < j && R[i].key < avg ) 
                i++;
            if ( i < j ) {
                cout << "   Higher: ";
                for( int t = 0; t < n; t++ )
                    cout << (t==l?"(":(t==h?")":" ")) << R[t].key << ((t==i||t==j) ? "<" : " ");
                cout << (h==n?")":"") << endl;
    
                swap(R[i], R[j]);
                j--;
            }
        }
    
        return R[i].key >= avg ? i : i+1;
    }
    
    void quicksort (RecType R[],int S, int T, int n) {
        if ( S < T - 1 ){
            int k = partition (R,S,T,n);
            quicksort (R,S,k,n);
            quicksort (R,k,T,n);
        }
    }
    
    int main(){
        RecType *list;
        int n;
    
        cin >> n;
        list = new RecType[n];
        for( int i = 0; i < n; i++)
            cin >> list[i].key; 
    
        quicksort(list, 0, n, n);
    
        for( int i = 0; i < n; i++)
            cout << list[i].key << " "; 
    } 
    

    需要改成这样,两个while的判断都不加等于。
    这段代码还能帮你输出排序过程,可以试试。

    点赞 1 评论 复制链接分享