algorithm - 就地进行基数排序 - 尝试了解如何进行

Question

我正在学习所有已知/典型的排序算法(插入、冒泡、选择、快速、合并排序......)，现在我刚刚阅读了基数排序。

我想我已经理解了它的概念，但我仍然想知道它如何就地完成？让我解释一下我是如何理解的:

它由 2 个阶段组成:分区和收集。他们将交替被处决。在分区阶段，我们将把数据分成每个......让我称这些为桶。在收集阶段我们将再次收集数据。这两个阶段都会针对要排序的键的每个位置执行。因此，循环的数量取决于键的大小(如果我们想要对整数进行排序，那么可以说是数字的数量)。

我不想详细解释这两个阶段，因为它太长了，我希望你能读到这里，因为我不知道如何就地执行这个算法..

也许你可以用文字而不是代码来解释？我需要在考试时了解它，但我在互联网上找不到任何解释，至少不是以简单易懂的方式。

如果您想让我解释更多，请告诉我。我会尽一切努力去理解它。

Answer 1

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

我引用这篇文章:

Binary MSD radix sort, also called binary quicksort, can be implemented in-place by splitting the input array into two bins - the 0s bin and the 1s bin. The 0s bin is grown from the beginning of the array, whereas the 1s bin is grown from the end of the array. [...] . The most significant bit of the first array element is examined. If this bit is a 1, then the first element is swapped with the element in front of the 1s bin boundary (the last element of the array), and the 1s bin is grown by one element by decrementing the 1s boundary array index. If this bit is a 0, then the first element remains at its current location, and the 0s bin is grown by one element. [...] . The 0s bin and the 1s bin are then sorted recursively based on the next bit of each array element. Recursive processing continues until the least significant bit has been used for sorting.

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

• 每一步只有两个存储桶，假设为 0 和 1。由于算法是“就地”的，因此您可以交换元素(如快速排序)以将每个元素放入正确的存储桶(0 或 1)中，具体取决于其基数。

• 递归处理:每个存储桶根据下一个基数分为两个存储桶。

无符号整数的理解非常简单:您可以考虑从最高有效位到最低有效位的位。对于其他数据类型来说，它可能更复杂(并且过度)。

总结一下快速排序算法的差异:

• 在快速排序中，您选择的主元定义了两个“桶”:低于主元，大于主元。

• 在二进制基数排序中，两个桶由基数(例如最高有效位)定义。

在这两种情况下，您都会交换元素以将每个元素放入其“存储桶”中并递归处理。