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

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

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

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

#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

sinat_35988648
dpqb 这是得到的排序结果:1 1 1 1 1 1 1 3 1 19 34
6 个月之前 回复
sinat_35988648
dpqb 你好,你的算法不能通过下面的数据,RecType arr[] = { {1}, {1}, {34}, {1}, {1}, {1}, {1}, {3}, {19}, {1} ,{1}}
6 个月之前 回复
sinat_35988648
dpqb 谢谢回答,懂了
6 个月之前 回复

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的判断都不加等于。
这段代码还能帮你输出排序过程,可以试试。

sinat_35988648
dpqb 回复JonathanYan: 好的,谢谢,麻烦了
6 个月之前 回复
JonathanYan
JonathanYan 回复dpqb: 修改了回答,看看有没什么问题
6 个月之前 回复
JonathanYan
JonathanYan 回复dpqb: 会出什么问题,能描述下么
6 个月之前 回复
sinat_35988648
dpqb 回复: 23,23,23,23这样序列怎么交换,交换和不交换都会出问题,如果平均数取整,像23,22,23,23这样的也会出问题
6 个月之前 回复
sinat_35988648
dpqb 你的方法对于一些情况下可行,但好像也有问题
6 个月之前 回复
sinat_35988648
dpqb 回复: 全是一样的序列根本没法排
6 个月之前 回复
sinat_35988648
dpqb 你好,谢谢你的回答,我试过了,对于23,22,23,23这样序列的会出bug
6 个月之前 回复
JonathanYan
JonathanYan 回复dpqb: 更新了回答,看下
6 个月之前 回复
JonathanYan
JonathanYan 回复dpqb: 而且这个右半部左半部只是相对的,函数返回的是中间值得下标,只要保证最后的i是分水岭就行。
6 个月之前 回复
JonathanYan
JonathanYan 回复dpqb: 那样i那边会找到比平均值大的再交换,否则“错误”地放到右半部的值左边都是小于平均值的,就变“正确”了
6 个月之前 回复
sinat_35988648
dpqb 如果交换后比平均值小的也移到右半部分怎么办。。。
6 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

1
这是一个快速排序的算法,基本情况是对的,有特殊情况没考虑到,有大哥能帮忙吗?
1
tensorflow中神经网络优化器问题
2
这是一个C++的排序算法,运行结果总是不正确,求大神帮帮忙改一下
2
在初始数据表已经有序时,在排序过程中仍要改变数据表内容的排序算法是?
0
如何用DSP实现遗传算法?
1
如何将数组按某值的差值用冒泡排序算法进行排序?
1
根据离散概率返回int值的算法的疑惑
0
请问如何使用nodejs实现hash算法和签名算法,然后使用golang语言验证hash值和签名
0
数组差异值的比较的算法问题,怎么采用C程序的语言的代码编写过程去实现的?
0
输出二维矩阵的值的算法,利用C语言的程序代码编写的思路是什么实现?
0
按照绝对值从大到小排序后输出,这个排序的算法用 C 语言的程序的设计的思想方式怎么实现的?
1
求一个代码c语言实现图的深度遍历(递归)、非递归算法以及实现图的广度遍历(队列)
0
请编程实现(a) 快速排序(quicksort)算法 和 (b) 二路归井排序(mergesort)算法。
1
选择排序算法不知道出什么问题了
2
Java算法设计:迭代器实现排序(求各位大佬各抒己见)
0
判断一下该排序算法是否正确
3
请问该算法如何实现?
2
跪求smotebagging和smoteboosting算法的python实现~
1
阿里在线评:实现一个邮件查找算法,可以根据主题,时间,收件人等等查找
1
我写的快速排序算法,大佬们帮我看看有啥问题吗,感谢