就地进行基数排序——试图理解如何
Making radix sort in-place - trying to understand how
我正在研究所有已知/典型的排序算法（插入、冒泡、选择、快速、合并排序..），现在我刚刚阅读了基数排序。
我想我已经理解了它的概念，但我仍然想知道如何就地完成它？让我解释一下我是如何理解的：
它由两个阶段组成：分区和收集。它们将交替执行。在分区阶段，我们将把数据分成每个……让我称这些为桶。在收集阶段，我们将再次收集数据。这两个阶段都将针对要排序的键的每个位置执行。所以循环的数量取决于键的大小（如果我们想要排序整数，我们宁愿说数字的数量）。
我不想详细解释这两个阶段，因为它太长了，我希望你能读到这里，因为我不知道如何就地执行这个算法..
也许你可以用文字而不是代码来解释？我在考试时需要知道它，但我在互联网上找不到任何解释，至少不是以一种简单易懂的方式。
如果你想让我解释更多，请告诉我。我会不惜一切代价去理解它。
维基百科（有时）是您的朋友：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。由于算法是 'in- place' 你交换元素（如在快速排序中）以将每个元素放在正确的桶中（0 或 1），具体取决于它的基数。
你递归处理：每个桶被分成两个桶，取决于下一个基数。
无符号整数很容易理解：你考虑从最高位到最低位的位。对于其他数据类型，它可能更复杂（并且矫枉过正）。
总结一下与快排算法的区别：
在快速排序中，您选择的主元定义了两个 "buckets"：低于主元，大于主元。
在二进制基数排序中，两个桶由基数定义（例如最高有效位）。
在这两种情况下，您交换元素以将每个元素放入其 "bucket" 并递归处理。
我正在研究所有已知/典型的排序算法（插入、冒泡、选择、快速、合并排序..），现在我刚刚阅读了基数排序。
我想我已经理解了它的概念，但我仍然想知道如何就地完成它？让我解释一下我是如何理解的：
它由两个阶段组成：分区和收集。它们将交替执行。在分区阶段，我们将把数据分成每个……让我称这些为桶。在收集阶段，我们将再次收集数据。这两个阶段都将针对要排序的键的每个位置执行。所以循环的数量取决于键的大小（如果我们想要排序整数，我们宁愿说数字的数量）。
我不想详细解释这两个阶段，因为它太长了，我希望你能读到这里，因为我不知道如何就地执行这个算法..
也许你可以用文字而不是代码来解释？我在考试时需要知道它，但我在互联网上找不到任何解释，至少不是以一种简单易懂的方式。
如果你想让我解释更多，请告诉我。我会不惜一切代价去理解它。
维基百科（有时）是您的朋友：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。由于算法是 'in- place' 你交换元素（如在快速排序中）以将每个元素放在正确的桶中（0 或 1），具体取决于它的基数。
你递归处理：每个桶被分成两个桶，取决于下一个基数。
无符号整数很容易理解：你考虑从最高位到最低位的位。对于其他数据类型，它可能更复杂（并且矫枉过正）。
总结一下与快排算法的区别：
在快速排序中，您选择的主元定义了两个 "buckets"：低于主元，大于主元。
在二进制基数排序中，两个桶由基数定义（例如最高有效位）。
在这两种情况下，您交换元素以将每个元素放入其 "bucket" 并递归处理。