10.43.c

数据结构习题及答案

10.43③ 已知记录序列a[1..n] 中的关键字各不相同，
可按如下所述实现计数排序：另设数组c[1..n]，对每
个记录a[i]， 统计序列中关键字比它小的记录个数存
于c[i]， 则c[i]=0的记录必为关键字最小的记录，然
后依c[i]值的大小对a中记录进行重新排列，试编写算
法实现上述排序方法。

实现下列函数：
void CountSort(SqList &L);
/* 采用顺序表存储结构，L.r存储序列a，L.length为n */
/* 在函数内自行定义计数数组c                     */

顺序表的类型SqList定义如下：
typedef struct {
   KeyType key; 
   ... 
} RedType;

typedef struct {
   RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元
   int     length;
} SqList;
void CountSort(SqList &L)
/* 采用顺序表存储结构，L.r存储序列a，L.length为n */
/* 在函数内自行定义计数数组c                     */
{
 int c[MAXSIZE+1];
 int count,i,j,min;
 for(i=1;i<=L.length;i++)
   {
    for(j=1,count=0;j<=L.length;j++)
       if(L.r[i].key>L.r[j].key) count++;
    c[i]=count;
    }
 for(i=1;i<=L.length;i++)
   {
    min=1;
    for(j=1;j<=L.length;j++)
      if(c[j]<c[min]) min=j;
    L.r[0]=L.r[i];
    L.r[i]=L.r[min];
    L.r[min]=L.r[0];
    c[min]=c[i];
    c[i]=MAXSIZE;
     }
}