排序算法-9-計數排序

計數排序

前面已經介紹過的所有排序，包括插入排序、選擇排序、冒泡排序、歸并排序、雞尾酒排序、希爾排序、快速排序和堆排序都是比較排序，因為在他們的排序過程中，都需要經過比較，比較元素的大小然後調整順序。可以證明，在最壞情況下，任何比較排序都需要經過 Ω ( n log ⁡ n ) \Omega(n \log n) Ω(nlogn) 次比較，是以比較排序的時間複雜度最好也就能到 O ( n log ⁡ n ) O(n \log n) O(nlogn) 了。

那如果我們想進一步降低時間複雜度怎麼辦呢？自然我們就不能用比較排序了。那麼有不比較就能排序的方法嗎？答案是有，還不止一種。這一篇我們就先講一種：計數排序。

原理

計數排序的思想是對每一個元素，确定不大于它的元素個數，然後把它放到對應的位置就行了。如同一個班的學生從低到高排序，對一個學生來說，如果知道班上有10個人不比他高，那麼他就應該排到第11位。

如果有相同的元素，這裡還需要一點小技巧。比如有3個相同的元素，則要把這3個挨着放，最好能保持其穩定，即雖然都是一樣大小，但之前在前面的排序完還是在前面，3個元素的相對位置不變。

具體步驟如下：

1. 用一個數組記錄每個元素分别有幾個。
2. 計算出對每個元素分别有多少個元素不大于它。
3. 把每個元素按位置放好，若有相同值的元素，注意要調整其位置以避免相同元素放到相同位置。

實作

按照以上原理我們來用代碼實作。

下面就是用C語言實作的代碼。

• 要排序的數組a有n個元素。注意a中所有元素值都在[0,k]範圍内。
• 數組c先記錄每個元素分别有幾個，後記錄對每個元素分别有多少個元素不大于它。
• 數組b用于儲存排序結果。
• 最終将排序結果複制到a中。

/* a中所有元素值都在[0,k]範圍内 */
void count_sort(int a[], int n, int k)
{
	int *b, *c;
	int i;

	b = (int*)malloc(sizeof(int)*n);
	if (b==NULL) return;
	c = (int*)malloc(sizeof(int)*(k+1));
	if (c==NULL) {
		free(b);
		return;
	}

	memset(c, 0, sizeof(int)*(k+1));

	for (i=0; i<n; i++) {
		c[a[i]]++;
	} //此時c[i]中存的是a中有幾個i

	for (i=1; i<=k; i++) {
		c[i] += c[i-1];
	} //此時c[i]中存的是有幾個元素<=i

	for (i=n-1; i>=0; i--) {
		b[c[a[i]]-1] = a[i];   //将a[i]放入b中正确的位置
		c[a[i]]--;             //調整b的位置指針，避免相同元素放到相同位置
	}

	memcpy(a, b, sizeof(int)*n); //将排序結果複制到a中

	free(c);
	free(b);
}
           

為了驗證此函數的效果，加上了如下輔助代碼，對3個數組進行排序，運作結果在最後，可見排序成功。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE_ARRAY_1 5
#define SIZE_ARRAY_2 6
#define SIZE_ARRAY_3 20

void show_array(int a[], int n);

void count_sort(int a[], int n, int k);

void main()
{
	int array1[SIZE_ARRAY_1]={1,4,2,9,0};
	int array2[SIZE_ARRAY_2]={10,5,2,1,9,2};
	int array3[SIZE_ARRAY_3];

	for(int i=0; i<SIZE_ARRAY_3; i++) {
		array3[i] = (int)((10.0*rand())/(RAND_MAX+1.0));
	}

	printf("Before sort, ");
	show_array(array1, SIZE_ARRAY_1);
	count_sort(array1, SIZE_ARRAY_1, 9);
	printf("After sort, ");
	show_array(array1, SIZE_ARRAY_1);

	printf("Before sort, ");
	show_array(array2, SIZE_ARRAY_2);
	count_sort(array2, SIZE_ARRAY_2, 10);
	printf("After sort, ");
	show_array(array2, SIZE_ARRAY_2);

	printf("Before sort, ");
	show_array(array3, SIZE_ARRAY_3);
	count_sort(array3, SIZE_ARRAY_3, 10);
	printf("After sort, ");
	show_array(array3, SIZE_ARRAY_3);
}

void show_array(int a[], int n)
{
	if(n>0)
		printf("This array has %d items: ", n);
	else
		printf("Error: array size should bigger than zero.\n");

	for(int i=0; i<n; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
}

           

運作結果：

Before sort, This array has 5 items: 1 4 2 9 0
After sort, This array has 5 items: 0 1 2 4 9
Before sort, This array has 6 items: 10 5 2 1 9 2
After sort, This array has 6 items: 1 2 2 5 9 10
Before sort, This array has 20 items: 8 3 7 7 9 1 3 7 2 5 4 6 3 5 9 9 6 7 1 6
After sort, This array has 20 items: 1 1 2 3 3 3 4 5 5 6 6 6 7 7 7 7 8 9 9 9
           

分析

時間複雜度

從代碼可見，count_sort中隻有一層循環，有三次，量級分别是 n n n、 k k k、 n n n，是以其時間複雜度為 O ( n + k ) O(n+k) O(n+k)，若 k = O ( n ) k = O(n) k=O(n)，則計數排序的時間複雜度為 O ( n ) O(n) O(n)。

空間複雜度

因為計數排序需要兩個輔助數組b和c來存儲中間結果，是以其空間複雜度為 O ( n + k ) O(n+k) O(n+k)，若 k = O ( n ) k = O(n) k=O(n)，則計數排序的空間複雜度為 O ( n ) O(n) O(n)。

要注意的是計數排序要求所有資料都是屬于某個小區間的整數。如果範圍太大，即 k k k 太大，則時間複雜度、空間複雜度都會變成增加，會影響排序效率。

穩定性

穩定。