計數排序隻能用于整數,
計數排序函數的參數有倆個:
一個是要進行處理操作的數組,
另一個參數是數組中元素的個數
- 【思路】:
因為是根據數組下标的相對位置取代替比較操作的,是以要 malloc 一個數組;
但是要想确定 malloc 出空間的具體大小時,
就要先在傳入函數的數組中尋找最大的元素與最小的元素,二者的差再加上1,
即确定了可以容納這些數組中全部的元素,
盡管可能會出現一些空間的剩餘,但是無關緊要。
配置設定好數組後不要忘記要初始化,将裡面的元素全部初始化為 0;
這裡的初始化很重要,
因為數組中的資料都是連續存放的,
- 注意:
這裡的相對位置是指:
原數組中的資料(a[ i ])減去原數組中最小的那個數( min ),
得到的數字便是 malloc 後空間中的位置 count + (a[ i ] - min),
這裡的位置隻會存放其所對應的原數組中那個資料的個數,并不會存放其原數組中的資料
而且根據大的數字減去 min 得到的值更大,那麼它的相對位置相較于小的數字的位置更靠後,進而判别出了數的大小
在統計好 malloc 所配置設定的空間中的相對位置上的原數組中每一個資料的個數後,
就要在原數組中(注意是在原數組中)從第一個位置根據 malloc 數組空間内的個數依次進行重新的指派;
為了在原數組中從第一個位置依次向後開始指派,需要建立一個變量加以解決;
而這時原數組中的資料其實無關緊要,
而且資料之間的大小關系也根據其相對位置進一步的敲定;
我們可以通過 malloc 數組空間内的 相對位置 與 其相對位置對應的資料個數 和 原資料中的最小值
推斷出原數組中的各個位置應該存放相應大小的數字:
即 : malloc 數組空間的每一個位置坐标 加上 最小值,
此時統計好的資料個數是作為 while 循環的判定條件所存在的,
而當遇到有多個數字時,因為有 while 循環的判定條件和保證原數組空間從頭開始存放資料所建立的變量 保證,不必擔心少放的問題
- 易錯點:
代碼實作:
//計數排序:
/*适用于資料之間的範圍不大,但是數的大小較為集中的數列排序*/
/* 時間複雜度:O(max(range, N))
空間複雜度:O(range)*/
void CountSort(int* a, int n)
{
int min = a[0], max = a[0];
for (int i = 1; i < n; ++i)
{
if (a[i] < min)
min = a[i];
if (a[i] > max)
max = a[i];
}
// 統計次數的數組
int range = max - min + 1; //減去 min 是關鍵,即是相對映射
int* count = (int*)malloc(sizeof(int)*range);//開辟數列中最大數值個空間
if (count == NULL)
{
printf("malloc fail\n");
exit(-1);
}
memset(count, 0, sizeof(int)*range);//對 count 數組進行初始化,使其數組中的每個值均為 0
// 統計次數:
/*根據原數組中的資料在 malloc 數組中的相對位置來統計原數組中每一個數字所出現的個數,
當有一個數字出現多次時,不管這多個數字位于原數組中的哪一個位置,因為它們都與 min 的差相同,
即都在同一相對位置中。*/
for (int i = 0; i < n; ++i)//周遊的是原數組
{
count[a[i] - min]++; //count 是動态記憶體開辟出來的數組
/*[a[i]-min] 是相對映射的位置*/
}
// 向原數組回寫-排序
int j = 0;//建立該變量的目的便是要在原數組中從頭開始更換其元素之間的位置
for (int i = 0; i < range; ++i)/*時間複雜度取決于這裡的 range 上面循環中的 n;
而且這一次周遊的是 malloc 出來的那個數組;
故要注意其周遊的出口條件需要改變。*/
{
// 出現幾次就會回寫幾個 i+min
while (count[i]--)
{
a[j++] = i + min;//後置++,是要在原數組中進行資料與資料之間位置的改動
}
}
}