挑戰二--第七章高等排序（四）

計數排序：

其實具體來說，我是沒太懂的，因為前面幾種排序的數組都是0開頭的，到計數排序突然說為了友善起見從1開始了。。。然後我就有點懵懵。。。。

emm其實算法具體就是記錄數組中每一個元素出現的次數然後再更新成記錄在原數組中有多少比該位置坐标小的數的個數。。。。。。（怎麼感覺越說越懵逼。。其實書上的圖示還是很清楚簡潔明了的。。。。但是我還是說不來。。。。尴尬。有機會要把書上的圖搬到部落格上面來。）

時間複雜度 線上性時間O(n+k)内完成，高效且穩定。

實作代碼

int Csort(int a[],int b[],int k){
	for(int i=1;i<=n;i++){
		c[a[i]]++;
	}
	for(int i=0;i<=k;i++){
		c[i]=c[i]+c[i-1];
	}
	for(int j=n;j>=1;j--){
		b[c[a[j]]]=a[j];
		c[a[j]]--;
	}

}
           

是不是有點着急回宿舍感覺有點着急并沒有很仔細的解釋這種算法了。。。。然而還有一張逆序數。利用标準庫排序，其實就是 sort和qsort。。。。emmm有時間整整，在網上找個好點的對比仔細看看再總結吧~