[Swift]计数排序|Countingsort【用微信查看本文链接可查看到引用图片】

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号&＃xff1a;山青咏芝&＃xff08;shanqingyongzhi&＃xff09;
➤博客园地址&＃xff1a;山青咏芝&＃xff08;https://www.cnblogs.com/strengthen/&＃xff09;
➤GitHub地址&＃xff1a;https://github.com/strengthen/LeetCode
➤原文地址&＃xff1a;https://www.cnblogs.com/strengthen/p/11075275.html 
➤如果链接不是山青咏芝的博客园地址&＃xff0c;则可能是爬取作者的文章。
➤原文已修改更新&＃xff01;强烈建议点击原文地址阅读&＃xff01;支持作者&＃xff01;支持原创&＃xff01;
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

1、定义&＃xff1a;

　　计数排序&＃xff08;Counting sort&＃xff09;是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组&＃xff0c;其中第i个元素是待排序数组中值等于的元素的个数。然后根据数组来将中的元素排到正确的位置。

2、特征&＃xff1a;

　　当输入的元素是个到之间的整数时&＃xff0c;它的运行时间是。计数排序不是比较排序&＃xff0c;排序的速度快于任何比较排序算法。

　　由于用来计数的数组的长度取决于待排序数组中数据的范围&＃xff08;等于待排序数组的最大值与最小值的差加上1&＃xff09;&＃xff0c;这使得计数排序对于数据范围很大的数组&＃xff0c;需要大量时间和内存。例如&＃xff1a;计数排序是用来排序0到100之间的数字的最好的算法&＃xff0c;但是它不适合按字母顺序排序人名。但是&＃xff0c;计数排序可以用在基数排序算法中&＃xff0c;能够更有效的排序数据范围很大的数组。

3、算法步骤&＃xff1a;

(1)、找出待排序的数组中最大和最小的元素

(2)、统计数组中每个值为的元素出现的次数&＃xff0c;存入数组的第项

(3)、对所有的计数累加&＃xff08;从中的第一个元素开始&＃xff0c;每一项和前一项相加&＃xff09;

(4)、反向填充目标数组&＃xff1a;将每个元素放在新数组的第项&＃xff0c;每放一个元素就将减去1

4、Talk is cheap.Show me your code.

测试&＃xff1a;