計(jì)數(shù)排序不同于比較排序，是基于計(jì)數(shù)的方式，對(duì)于計(jì)數(shù)排序，假設(shè)每一個(gè)輸入都是介于0~k之間的整數(shù)。對(duì)于每一個(gè)輸入元素x，確定出小于x的元素的個(gè)數(shù)。假如有17個(gè)元素小于x，則x就屬于第18個(gè)輸出位置。
計(jì)數(shù)排序涉及到三個(gè)數(shù)組A[0…..length-1],length為數(shù)組A的長(zhǎng)度；數(shù)組B與數(shù)組A長(zhǎng)度相等，存放最終排序的結(jié)果；C[0…..K]存放A中每個(gè)元素的個(gè)數(shù)，k為數(shù)組A中的最大值。

int count_k(int A[],int length)，此函數(shù)為了確定數(shù)組A中最大的元素，用來(lái)確定C數(shù)組的長(zhǎng)度。

int count_k(int A[],int length)
{
  int j,max;
  max = A[0];

  for(j=1;j<=length-1;j++)
  {
    if(A[j]>=max)
      max = A[j];
  }

  return max;
}

計(jì)數(shù)排序的實(shí)現(xiàn)：

void count_sort(int A[],int B[],int k)
{
  int *C = (int *)malloc((k+1) * sizeof(int));
  int i,j;
  for(i=0;i<=k;i++)//初始化數(shù)組C
    C[i]=0;

  for(j=0;j<=length-1;j++)//計(jì)算A中元素的個(gè)數(shù)
    C[A[j]] = C[A[j]]+1;
  for(i=1;i<=k;i++)//計(jì)算小于等于C[i]的元素的個(gè)數(shù)
    C[i] = C[i] + C[i-1];
  for(j=length-1;j>=0;j--)
  {
    int k=C[A[j]]-1;
    B[k] = A[j];
    C[A[j]] = C[A[j]] - 1;

  }

  free(C);

}

count_sort(A,B,k);

k=5

for(j=0;j<=length-1;j++)//計(jì)算A中元素的個(gè)數(shù)    
C[A[j]] = C[A[j]]+1;

表示數(shù)組A中有2個(gè)0、0個(gè)1、2個(gè)2、3個(gè)3、0個(gè)4、1個(gè)5

  for(i=1;i<=k;i++)//計(jì)算小于等于C[i]的元素的個(gè)數(shù)    
C[i] = C[i] + C[i-1];

小于等于0的數(shù)有兩個(gè)，小于等于1的數(shù)有兩個(gè)、小于等于2的數(shù)有4個(gè)、小于等于3的有7個(gè)、小于等于4的有7個(gè)、小于等于5的有8個(gè)

for(j=length-1;j>=0;j--)
  {
    int k=C[A[j]]-1;
    B[k] = A[j];
    C[A[j]] = C[A[j]] - 1;

  }

for循環(huán)分析如下

j=7;A[j]=A[7]=3;C[A[j]]=C[3]=7;C[A[j]]-1=6;B[C[A[j]]-1]=B[6]=A[j]=3;C[A[j]]=C[A[j]]-1=6

j=6;A[j]=A[6]=0;C[A[j]]=C[0]=2;C[A[j]]-1=1;B[C[A[j]]-1]=B[1]=A[j]=0;C[A[j]]=C[A[j]]-1=1

j=5;A[j]=A[5]=3;C[A[j]]=C[3]=6;C[A[j]]-1=5;B[C[A[j]]-1]=B[5]=A[j]=3;C[A[j]]=C[A[j]]-1=5;

j=4;A[j]=A[4]=2;C[A[j]]=C[2]=4;C[A[j]]-1=3;B[C[A[j]]-1]=B[3]=A[j]=2;C[A[j]]=C[A[j]]-1=3;

j=3;A[j]=A[3]=0;C[A[j]]=C[0]=1;C[A[j]]-1=0;B[C[A[j]]-1]=B[0]=A[j]=0;C[A[j]]=C[A[j]]-1=0;

j=2;A[j]=A[2]=3;C[A[j]]=C[3]=5;C[A[j]]-1=4;B[C[A[j]]-1]=B[4]=A[j]=3;C[A[j]]=C[A[j]]-1=4;

j=1;A[j]=A[1]=5;C[A[j]]=C[5]=8;C[A[j]]-1=7;B[C[A[j]]-1]=B[7]=A[j]=5;C[A[j]]=C[A[j]]-1=7;

j=0;A[j]=A[0]=2;C[A[j]]=C[2]=3;C[A[j]]-1=2;B[C[A[j]]-1]=B[2]=A[j]=2;C[A[j]]=C[A[j]]-1=2;

計(jì)數(shù)排序的最后運(yùn)行截圖

計(jì)數(shù)排序分析：j=length-1;j>=0;j–此處為倒序，是為了保證排序的穩(wěn)定性，這個(gè)在基數(shù)排序中有重要的作用。

最新評(píng)論