綜述
計數排序不是基于比較的排序算法,其核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中.
作為一種線性時間復雜度的排序,計數排序要求輸入的數據必須是有確定范圍的整數.
算法描述
1.找出待排序的數組中最大和最小的元素；
2.統(tǒng)計數組中每個值為i的元素出現的次數,存入數組C的第i項；
3.對所有的計數累加(從C中的第一個元素開始,每一項和前一項相加）；
4.反向填充目標數組:將每個元素i放在新數組的第C(i)項,每放一個元素就將C(i)減去1.
示意圖
性質
排序類別:非交換排序
是否是穩(wěn)定排序:穩(wěn)定
是否是原地排序:否
時間復雜度:O(n+k)
空間復雜度:O(k)
說明
它的優(yōu)勢在于在對一定范圍內的整數排序時,它的復雜度為Ο(n+k)(其中k是整數的范圍),快于任何比較排序算法.
當然這是一種犧牲空間換取時間的做法,而且當O(k)>O(n*log(n))的時候其效率反而不如基于比較的排序
基于比較的排序的時間復雜度在理論上的下限是O(n*log(n)), 如歸并排序,堆排序
計數排序是一個穩(wěn)定的排序算法.
當輸入的元素是n個0到k之間的整數時,時間復雜度是O(n+k),空間復雜度也是O(n+k),其排序速度快于任何比較排序算法.
當k不是很大并且序列比較集中時,計數排序是一個很有效的排序算法.
計數排序的缺點是當最大值最小值差距過大時,不適用計數排序,當元素不是整數值,不適用計數排序.
算法思想
計數排序對輸入的數據有附加的限制條件:
1术辐、輸入的線性表的元素屬于有限偏序集S称鳞；
2匪燕、設輸入的線性表的長度為n,|S|=k(表示集合S中元素的總數目為k）,則k=O(n).
在這兩個條件下,計數排序的復雜性為O(n).
計數排序的基本思想是對于給定的輸入序列中的每一個元素x,確定該序列中值小于x的元素的個數(此處并非比較各元素的大小,而是通過對元素值的計數和計數值的累加來確定）.一旦有了這個信息,就可以將x直接存放到最終的輸出序列的正確位置上.例如,如果輸入序列中只有17個元素的值小于x的值,則x可以直接存放在輸出序列的第18個位置上.當然,如果有多個元素具有相同的值時,我們不能將這些元素放在輸出序列的同一個位置上,因此,上述方案還要作適當的修改.
算法過程
假設輸入的線性表L的長度為n,L=L1,L2,..,Ln挣输；線性表的元素屬于有限偏序集S,|S|=k且k=O(n),S={S1,S2,..Sk}；則計數排序可以描述如下:
1姿搜、掃描整個集合S,對每一個Si∈S,找到在線性表L中小于等于Si的元素的個數T(Si)；
2捆憎、掃描整個線性表L,對L中的每一個元素Li,將Li放在輸出線性表的第T(Li)個位置上,并將T(Li)減1.
Python實現
def count_sort1(array):
length = len(array)
res = [None] * length
# 首次循環(huán)遍歷, 每個列表的數都統(tǒng)計
for index in range(length):
# p 表示 a[i] 大于列表其他數 的次數
p = 0
# q 表示 等于 a[i] 的次數
q = 0
# 二次循環(huán)遍歷, 列表中的每個數都和首次循環(huán)的數比較
for two_index in range(length):
if array[index] > array[two_index]:
p += 1
elif array[index] == array[two_index]:
q += 1
for k in range(p, p + q): # q表示相等的次數,就表示, 從p開始索引后, 連續(xù)q次,都是同樣的數
res[k] = array[index]
return res
dest = [5, 2, 7, 4, 8, 1, 6, 3]
result = count_sort1(dest)
print('最后的結果是:', result)
'''
最后的結果是: [1, 2, 3, 4, 5, 6, 7, 8]
'''
C語言實現
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void CountSort(int *arr, int len){
if(arr == NULL) return;
int max = arr[0], min = arr[0];
for(int i = 1; i < len; i++){
if(arr[i] > max) max = arr[i];
if(arr[i] < min) min = arr[i];
}
int size = max - min + 1;
int *count =(int*)malloc(sizeof(int)*size);
memset(count, 0, sizeof(int)*size);
for(int i = 0; i < len; i++)
count[arr[i] - min]++;//包含了自己舅柜！
for(int i = 1; i < size; i++)
count[i] += count[i - 1];
int* psort =(int*)malloc(sizeof(int)*len);
memset(psort, 0, sizeof(int)*len);
for(int i = len - 1; i >= 0; i--){
count[arr[i] - min]--;//要先把自己減去
psort[count[arr[i] - min]] = arr[i];
}
for(int i = 0; i < len; i++){
arr[i] = psort[i];
}
free(count);
free(psort);
count = NULL;
psort = NULL;
}
void print_array(int *arr, int len)
{
for(int i=0; i<len; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
int arr[8] = {5, 2, 7, 4, 8, 1, 6, 3};
CountSort(arr, 8);
print_array(arr, 8);
return 0;
}
