你的代码太乱,根本不能运行,我把分区的代码重新写了一下
作为程序员,我们只讨论可以运行的代码,不讨论书本上根本不通的东西。
#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