C++計數排序詳解

2020-05-23 14:05:54

字體：大中小

來源：轉載

供稿：網友

計數排序的思想我們之前接觸過的例如：插入排序，歸并排序，快速排序，堆排序等都是基于集合元素之間的比較這一基本的思想，它們執行的時間復雜度最優是趨于O(nlgn)，而計數排序的運行機制不是基于集合元素之間的大小比較

計數排序不同于比較排序，是基于計數的方式，對于計數排序，假設每一個輸入都是介于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);}

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

C++,計數排序

  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個

C++,計數排序

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

C++,計數排序

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

C++,計數排序

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;

C++,計數排序

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;

C++,計數排序

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;

C++,計數排序

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;

C++,計數排序

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;

C++,計數排序

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;

C++,計數排序

計數排序的最后運行截圖

C++,計數排序

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