計數排序的流程一般是找出資料中的最大值和最小值，創建哈希表，把資料-最小值當作陣列中的下標訪問哈希表并標記數量，然后遍歷哈希表，當表中的值大于時，把下標+最小值依次放入陣列中，它是一種典型的用空間換取時間的演算法，
特點是速度快，但也有很大局限性，而且資料的差值不宜過大，否則會非常浪費記憶體，數學期望越小、重復數越多，性價比越高，通常來說也只是為了排序整數才會使用，
int* count_sort(int* arr,size_t len)
{
int min = arr[0] , max = arr[len-1];
for(int i=0; i<len; i++)
{
if(arr[i] < min) min = arr[i];
if(arr[i] > max) max = arr[i];
}
int* tmp = calloc(sizeof(int),max-min+1);
for(int i=0; i<len; i++)
{
tmp[arr[i]-min]++;
}
for(int i=0,j=0; i<=max-min; i++)
{
while(tmp[i]--)
{
arr[j++] = i+min;
}
}
free(tmp);
return arr;
}
以前我也一直用以上形式，但是這種寫法似乎不能說明計數排序的穩定的，真是不純吶，查閱資料后發現了一種純度很高的寫法，
int* tim_sort(int* arr,size_t len)
{
int min = arr[0] , max = arr[0];
for(int i=0; i<len; i++)
{
if(arr[i] < min) min = arr[i];
if(arr[i] > max) max = arr[i];
}
int* tmp = calloc(sizeof(int),max-min+1);
for(int i=0; i<len; i++)
{
tmp[arr[i]-min]++;
}
int sum = 0;
for(int i=0;i<=max-min;i++)
{
sum += tmp[i];
tmp[i] = sum;
}
int* sss = calloc(sizeof(int),len);
int index;
for(int i = 0;i<len;i++)
{
index = tmp[arr[i]-min] - 1;
sss[index] = arr[i];
tmp[arr[i]-min] --;
}
free(tmp);
return sss;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/86381.html
標籤：其他