radix_通过JavaScript了解Radix排序

柔情只为你懂 2022-11-27 04:26 111阅读 0赞

radix

Because of the nature of comparison-based sorting, it’s mathematically impossible to improve much beyond `O(nlogn)`, like with [merge sort][] and [quick sort][]. Instead, we can be a bit more clever and avoid comparisons all together to get something closer to `O(n * m)`.

由于基于比较的排序的本质，从数学`O(nlogn)` ，无法像`O(nlogn)`那样进行很大的改进，例如[合并排序][merge sort]和[快速排序][quick sort] 。 取而代之的是，我们可以更聪明一些，避免在一起进行比较，以使结果更接近`O(n * m)` 。

## 先决条件 **(**Prerequisites**)** ##

A basic understanding of [Big O Notation][] is essential to think about radix sort relative to other algorithms.

对[Big O表示法的][Big O Notation]基本理解对于考虑相对于其他算法的基数排序至关重要。

## 概念 **(**Concept**)** ##

Radix sort, also known as bucket sort, is one of the oldest sorting algorithms and even pre-exists computers. It was used to sort punched cards back in the 1880s.

基数排序，也称为存储桶排序，是最古老的排序算法之一，甚至是预先存在的计算机。 它在1880年代曾用于对打Kong卡进行分类。

It’s based on the idea of having a sub-array, or bucket, for each type of data we need to compare, like A-Z or in our case 0-9. We take the first character/digit in each item, add the whole item to it’s corresponding bucket, then put them back into an array while retaining their new order.

它基于为我们需要比较的每种数据类型(如AZ或本例中为0-9)设置一个子数组或存储桶的想法。 我们在每个项目中采用第一个字符/数字，将整个项目添加到其相应的存储桶中，然后将它们放回数组中，同时保留其新顺序。

We can then move on to the next character/digit and repeat the process. When an item runs out of characters/digits we’ll add it to the first bucket, since everything else is obviously larger/longer. When we’ve done this as many times as the number of digits/characters of the largest item, our array will have been completely sorted without making any pesky comparisons.

然后，我们可以继续下一个字符/数字并重复该过程。 当某项用完字符/数字用完后，我们会将其添加到第一个存储桶中，因为其他所有内容显然都更大/更长。 当我们完成此操作的次数达到最大项目的位数时，我们的数组将被完全排序，而不会进行任何令人讨厌的比较。

Graphic/Animation thanks to [VisuAlgo.net][]

图形/动画得益于[VisuAlgo.net][]

## 实践数据 **(**Practice Data**)** ##

Since numbers are much simpler, we can practice with an array of them from 1 to 50.

由于数字要简单得多，因此我们可以使用1到50的数组进行练习。

const unsortedArr = [31, 27, 28, 42, 13, 8, 11, 30, 17, 41, 15, 43, 1, 36, 9, 16, 20, 35, 48, 37, 7, 26, 34, 21, 22, 6, 29, 32, 49, 10, 12, 19, 24, 38, 5, 14, 44, 40, 3, 50, 46, 25, 18, 33, 47, 4, 45, 39, 23, 2];

## 实用工具 **(**Utilities**)** ##

Since we’re working with numbers, we want to start with the smallest number place and work up, so we’ll need a way to get each number at an index starting from the right.

由于我们正在处理数字，因此我们希望从最小的数字位置开始并逐步完善，因此我们需要一种方法来从右开始的索引处获取每个数字。

The most intuitive way I’ve found is to take the number we want, convert it into a string, and select from it as an array with a negative index. If a number’s not at that index we can just return a zero so it’ll be placed in the front of our sorted array.

我发现的最直观的方法是获取所需的数字，将其转换为字符串，然后从中选择带有负索引的数组。 如果数字不在该索引处，我们可以返回一个零，以便将其放置在已排序数组的前面。

const getNum = (num, index) => {
      const strNum = String(num);
      let end = strNum.length - 1;
      const foundNum = strNum[end - index];
    
      if (foundNum === undefined) return 0;
      else return foundNum;
    };
    
    console.log(getNum(4353, 2));

Because we’re working back one digit at a time we need the algorithm to run as many times as the longest number, so if we have an item with 8 digits, it needs to be ran 8 times. Radix sort’s average complexity is `O(n * m)` because it’s the amount of items times the amount of times it needs to be ran.

因为我们一次要回一位数，所以我们需要算法运行最长数字的次数，因此，如果我们有一个8位数字的项目，则需要运行8次。 基数排序的平均复杂度为`O(n * m)`因为它是项目数乘以需要运行的次数。

To get how many times it should run we can search through the array for the largest number, then return its length.

为了获得它应该运行多少次，我们可以在数组中搜索最大数目，然后返回其长度。

const largestNum = arr => {
      let largest = "0";
    
      arr.forEach(num => {
        const strNum = String(num);
    
        if (strNum.length > largest.length) largest = strNum;
      });
    
      return largest.length;
    };

## 基数排序 **(**Radix Sort**)** ##

Implementation is pretty straight-forward, for every digit place we can use `Array.from` to create 10 empty buckets. For every item they’ll be placed in the corresponding bucket, when that’s done we’ll flatten the array of buckets into a single array to start over with the next character place. When we’ve reached the end of our longest digit our fully sorted array can be returned.

实现非常简单，对于每个数字位，我们都可以使用`Array.from`创建10个空存储桶。 对于每个项目，它们将被放置在相应的存储桶中，完成后，我们会将存储桶数组展平为单个数组，以从下一个字符开始。 当我们到达最长位数的末尾时，可以返回完全排序的数组。

## 结论 **(**Conclusion**)** ##

While playing around with this, I tried it on an array of 5,000 items, to my utter amazement it was done in only 23 milliseconds! I don’t know about you, but I think that’s an incredible improvement over the other algorithms we’ve covered so far.

在玩这个游戏的时候，我尝试了5,000个项目，仅用23毫秒就完成了！ 我不了解您，但是我认为这是迄今为止我们所介绍的其他算法的不可思议的改进。

> 翻译自: [https://www.digitalocean.com/community/tutorials/js-radix-sort][https_www.digitalocean.com_community_tutorials_js-radix-sort]

radix

[merge sort]: https://www.digitalocean.com/community/tutorials/js-understanding-merge-sort
[quick sort]: https://www.digitalocean.com/community/tutorials/js-quick-sort
[Big O Notation]: https://www.digitalocean.com/community/tutorials/js-big-o-notation
[VisuAlgo.net]: https://visualgo.net
[https_www.digitalocean.com_community_tutorials_js-radix-sort]: https://www.digitalocean.com/community/tutorials/js-radix-sort