非比较排序都具有很大的局限性,包括技术排序,基数排序,桶排序等

计数排序

时间复杂度:O(N)

空间复杂度:O(range)

适用范围

数据的范围集中的数组进行排序,不适合数据分散的数组

方法

统计每个数据出现的次数为n

建立一个相同大小的数组,将每个数据都初始化为0

然后遍历原数组,是多少就对对应位置++(是0就对count[0]++)

一个值出现几次,他映射的位置次数就被加几次,就统计出了次数

当然,这里的映射不是绝对映射(数据大小不一定对应相同的数组下标)

即新开辟的数组count大小为max - min + 1

则映射应该为count[a[i]-min]++

这样一组数据就可以只开辟大小为10的数组,将100放在count[0],109放在count[109]

负数也是同理

void CountSort(int* a, int n)
{int min = a[0], max = a[0];for (int i = 1; i < n; i++){if (a[i] > max)max = a[i];if (a[i] < min)min = a[i];}int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);if (count == NULL){perror("malloc fail");return;}memset(count, 0, sizeof(int) * range);//统计次数for (int i = 0; i < n; i++){count[a[i] - min]++;}//排序int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}
}

局限性

只适合整型数组,不能排浮点数,字符串和结构体也不能排序