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

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

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

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

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

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

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

• 在快速排序中,您选择的数据透视定义了两个“桶”:低于数据透视,大于数据透视。

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

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