基数排序

在上篇文章中,我们已经学习过了计数排序,计数排序和我们这篇文章要讲的基数排序,两者都是基于 桶排序 的思想。

计数排序的思想在于将相同元素放到同一个桶里。

下面我们主要是讲解基数排序的思想,具体代码的实现不做学习要求。

基数排序思想介绍

基数排序的核心思想是根据元素的个位、十位、百位…依次来进行排序。

具体来说,基数排序可以分为 LSD(Least Significant Digit)MSD(Most Significant Digit)两种方式,分别从最低位和最高位开始进行排序。

我们先来看一下 LSD 基数排序(从最低位开始)的实现过程。

假设我们要对一组整数进行排序,我们可以先找到其中最大的数,确定它的位数,然后从个位到最高位依次进行排序。具体步骤如下:

  1. 创建 10 个桶,分别表示 0-9 这 10 个数字。
  2. 先根据个位数字将所有元素放入对应的桶中。
  3. 将桶中的元素按顺序取出,重新放入原数组中。(桶里的元素先入先出
  4. 重复以上步骤,依次按十位、百位…这样逐渐排序,直至所有位数都排完。

示例

我们举个例子

  • 先从个位开始进行基数排序,如下图,可以看到排完序之后,数组在个位上是有序的

  • 再从十位开始进行基数排序,如下图,可以看到排完序之后,数组在后两位上是有序的

  • 再从最高位百位开始进行基数排序,如下图,如果数字只有两位,则补 0,可以看到排完序之后,数组已经实现有序。

MSD 基数排序

至于 MSD基数排序,其思想与 LSD 类似,不同之处在于它是从最高位开始排序,直到最低位。

不过大家重点还是掌握 LSD 基数排序,其他的我们仅作了解即可。

示例:

在上面的例子中,我们已经对百位进行了入桶操作,接下来需要对每个桶里的元素根据十位进行下一轮的基数排序。

其实这里接下来可以用递归的方式来处理每一位,直到所有位数都排完。

时间复杂度

基数排序的时间复杂度为 {O(n * k)},其中 n 为元素的个数,k 为元素的位数。

空间复杂度

基数排序的空间复杂度为 {O(n * k)},其中 n 为元素的个数,k 为桶的数量(一般为 10,表示 0-9 十个数字)。

在基数排序中,需要额外使用桶来存放元素,因此空间复杂度与元素的个数和桶的数量有关。

稳定性

因为基数排序的使用场景只适用于整数数字的排序,因此也不会对稳定性有什么要求了。

写在最后

总的来说,基数排序是一种高效的排序算法,只是对元素的要求比较高,只适用于整数或者能转换为整数的数据类型,对于其他类型的数据需要进行适当转换才能使用基数排序。

通过这篇文章,相信你已经对基数排序有了一定的了解,感兴趣的也可以尝试去实现一下代码,锻炼编码能力。

发表回复

后才能评论