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

dpqb 这是得到的排序结果：1 1 1 1 1 1 1 3 1 19 34
6 个月之前 回复
dpqb 你好，你的算法不能通过下面的数据，RecType arr[] = { {1}, {1}, {34}, {1}, {1}, {1}, {1}, {3}, {19}, {1} ,{1}}
6 个月之前 回复
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

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

dpqb 回复JonathanYan: 好的，谢谢，麻烦了
6 个月之前 回复
JonathanYan 回复dpqb: 修改了回答，看看有没什么问题
6 个月之前 回复
JonathanYan 回复dpqb: 会出什么问题，能描述下么
6 个月之前 回复
dpqb 回复: 23,23,23,23这样序列怎么交换，交换和不交换都会出问题，如果平均数取整，像23,22,23,23这样的也会出问题
6 个月之前 回复
dpqb 你的方法对于一些情况下可行，但好像也有问题
6 个月之前 回复
dpqb 回复: 全是一样的序列根本没法排
6 个月之前 回复
dpqb 你好，谢谢你的回答，我试过了，对于23,22,23,23这样序列的会出bug
6 个月之前 回复
JonathanYan 回复dpqb: 更新了回答，看下
6 个月之前 回复
JonathanYan 回复dpqb: 而且这个右半部左半部只是相对的，函数返回的是中间值得下标，只要保证最后的i是分水岭就行。
6 个月之前 回复
JonathanYan 回复dpqb: 那样i那边会找到比平均值大的再交换，否则“错误”地放到右半部的值左边都是小于平均值的，就变“正确”了
6 个月之前 回复
dpqb 如果交换后比平均值小的也移到右半部分怎么办。。。
6 个月之前 回复