计数排序基础思路

所谓计数排序，也可以称为散列表 。也是一种简单的哈希桶。

今天，小编带大家来了解计数排序的基本思路。

一。基本思路

以升序为例，计数排序通俗来讲，分为三个步骤。

首先制作包含所有要排序的数的桶（相同的数制作一个桶即可）。

以2，3，6，1，4，1，2，3，7，6，8，9，5，4，3举例，就是制作9个桶，分别代表1，2，3，4，5，6，7，8，9。

第二步， 把所有的数依次放入桶中，桶中的数字代表该数有多少个。

第三步，从小到大依次把桶中的数全部拿出来。

排序完成。

小编希望大家自主实现一下代码，难度不大，相信自己！

ps:桶可以用数组下标代替。

 二。代码实现

void CountSort(int* a, int n)
{if (n <= 0) return;assert(a);int min = a[0], max = a[0];for (int i = 0; i < n; i++)//找出排序范围，减少空间浪费{if (min > a[i]) min = a[i];if (max < a[i]) max = a[i];}int* tmp = (int*)new int[max - min + 1], range = max - min + 1;memset(tmp, 0, sizeof(int) * range);for (int i = 0; i < n; i++)//入桶{tmp[a[i] - min]++;}int sub = 0;for (int i = 0; i < range; i++)//出桶{while (tmp[i]--){a[sub++] = i + min;}}
}

三。问题

时间复杂度：O（n)

空间复杂度：O（n)

计数排序的作用范围狭小，浮点数、结构体之类都不适用，且范围越大空间复杂度和空间浪费就越明显。

三连支持一下吧😀  如有错误，敬请斧正 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！