C++計數排序詳解

C++計數排序詳解。本站提示廣大學習愛好者：（C++計數排序詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是C++計數排序詳解正文

計數排序分歧於比擬排序，是基於計數的方法，關於計數排序，假定每個輸出都是介於0~k之間的整數。關於每個輸出元素x，肯定出小於x的元素的個數。假設有17個元素小於x，則x就屬於第18個輸入地位。
計數排序觸及到三個數組A[0…..length-1],length為數組A的長度；數組B與數組A長度相等，寄存終究排序的成果；C[0…..K]寄存A中每一個元素的個數，k為數組A中的最年夜值。

int count_k(int A[],int length)，此函數為了肯定數組A中最年夜的元素，用來肯定C數組的長度。

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;
}

計數排序的完成：

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++)//初始化數組C
    C[i]=0;

  for(j=0;j<=length-1;j++)//盤算A中元素的個數
    C[A[j]] = C[A[j]]+1;
  for(i=1;i<=k;i++)//盤算小於等於C[i]的元素的個數
    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++)//盤算A中元素的個數    
C[A[j]] = C[A[j]]+1;

表現數組A中有2個0、0個1、2個2、3個3、0個4、1個5

  for(i=1;i<=k;i++)//盤算小於等於C[i]的元素的個數    
C[i] = C[i] + C[i-1];

小於等於0的數有兩個，小於等於1的數有兩個、小於等於2的數有4個、小於等於3的有7個、小於等於4的有7個、小於等於5的有8個

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輪回剖析以下

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=length-1;j>=0;j–此處為倒序，是為了包管排序的穩固性，這個在基數排序中有主要的感化。