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

Question

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

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

Answer 1

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

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

#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