代码之家 › 专栏 › 技术社区 › eyesima

使基数排序到位-尝试理解如何

in-place radix-sort explain sorting algorithm

2

eyesima · 技术社区 · 8 年前

我想我已经理解了它的概念,但我仍然想知道如何在适当的地方做到这一点?让我解释一下我是如何理解它的:

它由两个阶段组成:分区和收集。它们将交替执行。在分区阶段,我们将把数据分为两部分。。让我把这些叫做桶。在收集阶段,我们将再次收集数据。这两个阶段将针对要排序的键的每个位置执行。因此,周期的数量是基于键的大小(如果我们想要排序整数,我们可以说是数字的数量)。

我不想太详细地解释这两个阶段,因为它太长了,我希望你能一直读到这里,因为我不知道如何在适当的地方做这个算法。。

如果你想让我解释更多,请告诉我。我会做任何事情来理解它。

1 回复 | 直到 8 年前

1

2

jferard 8 年前

维基百科(有时)是你的朋友: https://en.wikipedia.org/wiki/Radix_sort#In-place_MSD_radix_sort_implementations .

二进制MSD基数排序,也称为二进制快速排序,可以通过将输入阵列拆分为两个存储箱(即 0s纸盒和1s纸盒。0s垃圾箱从数组,而1s存储箱是从数组的末尾开始增长的。[...] . 最重要的检查第一个数组元素的位。如果该位为1,则边界(数组的最后一个元素),1s bin增长为为0,则第一个元素保持在其当前位置,并且已用于排序。

主要信息是:它是一个和递归基数排序。换句话说:

递归处理:根据下一个基数,每个存储桶被分成两个存储桶。

无符号整数的理解非常简单:从最高有效位到最低有效位。对于其他数据类型,它可能更复杂(而且过于复杂)。

要总结快速排序算法的区别:

在快速排序中,您选择的数据透视定义了两个“桶”:低于数据透视,大于数据透视。
在二进制基数排序中,两个桶由基数(例如最高有效位)定义。

在这两种情况下,您交换元素以将每个元素放入其“bucket”中并递归处理。