paixu1.txt

来自「已知记录序列a[1..n] 中的关键字各不相同」· 文本 代码 · 共 40 行

已知记录序列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                     */
{int i,j,count,c[30],temp;
 if(L.length)
   {for(i=1;i<=L.length;i++)
      {count=0;
       for(j=1;j<i;j++)
         if(L.r[i].key>L.r[j].key) ++count;
       for(j=i+1;j<=L.length;j++)
         if(L.r[i].key>L.r[j].key) ++count;
       c[i-1]=count;
      }
    for(i=0;i<L.length;i++)
      {temp=c[c[i]];
       L.r[0]=L.r[c[i]+1];
       c[c[i]]=c[i];
       L.r[c[i]+1]=L.r[i+1];
       c[i]=temp;
       L.r[i+1]=L.r[0];         
      }
    for(i=L.length-1;i>=0;i--)
      {if(c[i]!=i)
        {temp=c[c[i]];
         L.r[0]=L.r[c[i]+1];
         c[c[i]]=c[i];
         L.r[c[i]+1]=L.r[i+1];
         c[i]=temp;
         L.r[i+1]=L.r[0];
        }          
      }
   }
}