JS实现的计数排序与基数排序算法示例

本文实例讲述了JS实现的计数排序与基数排序算法。分享给大家供大家参考，具体如下： 计数排序 计数排序就是简单的桶排序，一个桶代表数组中一个数出现的个数，所以需要一个和数组数字范围一样大的辅助数组，一般用在范围小于100的排序，时间复杂度为O(n)，空间复杂度为数组的数字范围。 /** * 范围在 start - end 之间的排序 * 计数排序需要辅助数组，该辅助数组的长度是待排序数组的范围，所以一般用作范围小于100的排序 */ function countSort(arr, start, end) { var len = arr.length; // 桶数组 var s 计数排序和基数排序是两种非比较型的排序算法，它们在特定情况下能提供比比较型排序更快的速度。这两种算法都是基于将元素分配到不同“桶”中来完成排序的。 1. 计数排序（Counting Sort）： 计数排序是一种线性时间复杂度的排序算法，适用于待排序数组的元素范围相对较小的情况。它的工作原理是通过统计数组中每个元素出现的次数，然后根据这些计数来确定每个元素在排序结果中的位置。在JS中，实现计数排序的基本步骤如下： - 初始化一个与待排序数组元素范围相同大小的辅助数组（桶数组）。 - 遍历待排序数组，将每个元素作为索引增加其在辅助数组中的计数。 - 使用辅助数组的累计计数，从后向前填充结果数组。 在给定的代码中，`countSort`函数首先初始化了两个数组，一个是用于存储计数的`suportArr`，另一个是用于存储排序结果的`resArr`。接着，遍历输入数组`arr`，更新`suportArr`的计数，然后根据累计计数从后向前填充`resArr`。 2. 基数排序（Radix sort）： 基数排序是一种非比较型整数排序算法，它的基本思想是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序通常采用“桶”或“袋”来存储每个位上的数字。在JS中，基数排序的实现通常包括多个步骤，每个步骤对数组的一个位进行排序，直到所有位都处理完毕。 在给定的代码中，`radixSort`函数利用了 `_roundSort` 函数来对每个位进行排序。`_roundSort` 首先创建了一个大小为基数的桶数组，然后遍历原数组，根据当前位的值将元素放入对应的桶中。接着，按照桶的顺序重新组装数组。这个过程重复进行，每次处理下一个位，直到所有位都被处理。 基数排序的时间复杂度为 O(kn)，其中 k 是数字的最大位数，n 是元素数量。它的优点是不受输入数据分布的影响，但缺点是需要额外的空间来存储桶和中间结果。 在实际应用中，如果待排序的数据满足计数排序或基数排序的条件，这两种方法可以提供非常高效的排序解决方案。例如，对于包含大量重复元素且元素范围不大的整数数组，计数排序是一个很好的选择。而基数排序则适合处理大整数，尤其是位数较多且位上分布均匀的情况。