带你读《图解算法小抄》十四、排序（20）

带你读《图解算法小抄》十四、排序（19）https://developer.aliyun.com/article/1348131?groupCode=tech_library

2）优化手段：

基数排序的性能可以通过以下优化手段进行改进：

负数的处理：

基数排序默认适用于非负整数序列。若序列中包含负数，可以将负数和非负数分开进行排序，再进行合并。

// 场景1：对非负整数数组进行排序function radixSort(arr) {
  // 基础代码实现省略}
// 场景2：对包含负数的整数数组进行排序function radixSortWithNegative(arr) {
  const negatives = arr.filter((num) => num < 0);
  const positives = arr.filter((num) => num >= 0);
  const sortedNegatives = radixSort(negatives.map((num) => Math.abs(num)))
    .reverse()
    .map((num) => -num);
  const sortedPositives = radixSort(positives);
  return sortedNegatives.concat(sortedPositives);}// 示例用法const array = [170, 45, 75, -90, -802, 24, 2, 66];const sortedArray = radixSortWithNegative(array);
console.log(sortedArray); // 输出: [-802, -90, 2, 24, 45, 66, 75, 170]

基数排序是一种非比较性排序算法，通过按照位数进行多次分配和收集，实现整数序列的排序。我们可以使用基础的基数排序代码实现排序流程，并根据实际需求选择不同的优化手段来提高性能。通过桶的优化、桶内排序优化和处理负数的方法，我们可以进一步优化基数排序算法。在 JavaScript 中，我们可以使用上述代码实现基数排序，并根据实际场景选择适当的优化策略来满足排序需求。

3）复杂度

4）参考资料

• 维基百科
  
• YouTube
  
• ResearchGate
• 
  

9.计数排序

在计算机科学中，计数排序（Counting Sort）是一种根据键值为小整数的集合对对象进行排序的算法，也就是说，它是一种整数排序算法。它通过计算具有每个不同键值的对象的数量，并使用这些计数的算术运算来确定每个键值在输出序列中的位置。

它的运行时间与项的数量和最大键值与最小键值之间的差异成线性关系，因此仅适用于键的变化不显著大于项的数量的直接使用情况。

然而，它经常作为另一个排序算法（基数排序）的子程序使用，后者可以更有效地处理更大的键。

由于计数排序使用键值作为数组的索引，它不是一种比较排序，因此不适用于比较排序的下限 Ω(n log n)。

桶排序可以用于与计数排序相同的任务，并且具有类似的时间复杂度分析；然而，与计数排序相比，桶排序需要使用链表、动态数组或大量预分配的内存来保存每个桶中的项目集，而计数排序则将每个桶中存储一个数字（项目的计数）。

计数排序在每个数组元素的数字范围非常小的情况下效果最好。

带你读《图解算法小抄》十四、排序（21）https://developer.aliyun.com/article/1348129?groupCode=tech_library