C++計數(shù)排序詳解
計數(shù)排序不同于比較排序,是基于計數(shù)的方式,對于計數(shù)排序,假設每一個輸入都是介于0~k之間的整數(shù)。對于每一個輸入元素x,確定出小于x的元素的個數(shù)。假如有17個元素小于x,則x就屬于第18個輸出位置。
計數(shù)排序涉及到三個數(shù)組A[0…..length-1],length為數(shù)組A的長度;數(shù)組B與數(shù)組A長度相等,存放最終排序的結(jié)果;C[0…..K]存放A中每個元素的個數(shù),k為數(shù)組A中的最大值。
int count_k(int A[],int length),此函數(shù)為了確定數(shù)組A中最大的元素,用來確定C數(shù)組的長度。
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; }
計數(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++)//計算A中元素的個數(shù) C[A[j]] = C[A[j]]+1; for(i=1;i<=k;i++)//計算小于等于C[i]的元素的個數(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++)//計算A中元素的個數(shù) C[A[j]] = C[A[j]]+1;
表示數(shù)組A中有2個0、0個1、2個2、3個3、0個4、1個5
for(i=1;i<=k;i++)//計算小于等于C[i]的元素的個數(shù) C[i] = C[i] + C[i-1];
小于等于0的數(shù)有兩個,小于等于1的數(shù)有兩個、小于等于2的數(shù)有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循環(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;
計數(shù)排序的最后運行截圖
計數(shù)排序分析:j=length-1;j>=0;j–此處為倒序,是為了保證排序的穩(wěn)定性,這個在基數(shù)排序中有重要的作用。
相關文章
VS2010 boost標準庫開發(fā)環(huán)境安裝教程
這篇文章主要為大家詳細介紹了VS2010 boost標準庫開發(fā)環(huán)境的安裝教程,具有一定的參考價值,感興趣的小伙伴們可以參考一下2017-04-04VScode + keil開發(fā)環(huán)境搭建安裝使用過程
這篇文章主要介紹了VScode + keil開發(fā)環(huán)境搭建及安裝使用過程,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-07-07