菜鸟笔记
提升您的技术认知

什么是基数排序?

文章目录

  • 什么是基数排序
  • 稳定的计数排序
  • 基数排序的实现
  • 复杂度

什么是基数排序

数据结构与算法 | 计数排序
在之前的博客中,我介绍过一种非比较排序——计数排序
计数排序的原理很简单,就是用一个数组来统计每种数字出现的次数,然后按照大小顺序将其依次放回原数组,达成排序的目的。

但是计数排序有一个很严重的问题,就是其只能对整数进行排序,一旦遇到字符串时,就无能为力了。

为了弥补上述的缺点,针对于字符串基数排序诞生了。
基数排序在计数排序的基础上进行了改进,将排序工作拆分为多个阶段,每一个阶段只根据一个字符进行排序,一共排序K轮(K为数据长度)

例如我们需要对一组三个英文字母组成的字符串进行排序,按照以上规则,进行三轮排序。

(ps:这里用的LSD法)我们从低位往高位开始排,按照计数排序的思想,统计所有出现过的字符,按照其在ascii表中的顺序依次排序,得到以下结果

此时在第一轮的基础上,对倒数第二个字符进行排序

在第二轮的基础上,再对第一个字符进行排序


如此一来,就得到了有序的序列。这种将字符串拆分为多位,每位进行计数排序的算法,就是基数排序。

从上面来看,每一位的排序都基于上一位的基础,所以这也就要求我们的计数排序必须是稳定的,否则前后顺序无法保证,多轮的排序就没有了意义,下面就介绍如何实现稳定的计数排序。

稳定的计数排序

在之前的博客中,我当时介绍的计数排序是不稳定的,下面就对其进行改造,将其变为稳定排序。

那要这么做呢?我们知道,计数排序中的统计数组中存储了每个数字出现的次数,而我们还原时也只是按照数字来依次将其放回,这也就是其不稳定的原因,因为统计数组丝毫没有关心其在原数组中的位置。

要改进这一点,可以通过以下方法来实现,只需要加上几行简单的代码即可。

//保证计数排序稳定,对数组变形,统计数组的每一个位置的值为前面所有数字的数量合
//变形后每个位置的值即为该数据的排序的序号
int sum = 0;
for(int i = 0; i < range; i++)
{
  
    sum += count[i];
    count[i] = sum;
}

如上面代码,我们需要让统计数组中不再记录数组出现的次数,而是记录该位置前面所有数字出现的次数和,这种方式能让我们巧妙地得到序号。

例如下图

这样做的目的是什么呢?

//按照原数组的数据的位置,倒序将数据放回原位,确保稳定性
    vector<int> temp(arr.size(), 0);
    for(int i = arr.size() - 1; i >= 0; i--)
    {
  
        //序号-1才是下标位置
        temp[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }

因为我们此时统计数组中每一个位置的值,变成了由数组开头到那个位置所有元素的和,这也就意味着,他此时变成了一个排名
例如在原数据中有两个93,一个在前,一个在后,并且统计数组中93的位置为7。
我们通过上述方法,从后往前遍历时,将后面的93放到第七个位置,接着统计数组对应位置的排名减一,此时当我们放入前面的93时,他就变成了第六位,这样就保证了其稳定性。

这个看代码更好理解,思路都写在了注释中,改造完后的计数排序代码如下。

void countSort(vector<int>& arr)
{
  
    int max = arr[0], min = arr[0];
    
    //找出最大值和最小值,缩减范围
    for(int i = 1; i < arr.size(); i++)
    {
  
        if(arr[i] > max)
        {
  
            max = arr[i];
        }
        if(arr[i] < min)
        {
  
            min = arr[i];
        }
    }

    int range = max - min + 1;
    vector<int> count(range, 0);    //统计数组
    //统计每种数字出现的次数
    for(int i = 0; i < arr.size(); i++)
    {
  
        count[arr[i] - min]++;
    }

    //保证计数排序稳定,对数组变形,统计数组的每一个位置的值为前面所有数字的数量合
    //变形后每个位置的值即为该数据的排序的序号
    int sum = 0;
    for(int i = 0; i < range; i++)
    {
  
        sum += count[i];
        count[i] = sum;
    }

    //按照原数组的数据的位置,倒序将数据放回原位,确保稳定性
    vector<int> temp(arr.size(), 0);
    for(int i = arr.size() - 1; i >= 0; i--)
    {
  
        //序号-1才是下标位置
        temp[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }

    arr = temp; //将临时数据拷贝回原数组
}

基数排序的实现

在写基数排序之前,还有一个小问题需要说明一下,由于前面我们所说的情况都是字符串长度相等的时候,如果字符串长度不相同时,怎么处理呢?

因为字符串并不像整数一样排序依赖于长度,其排序主要依赖于字典序,所以我们以字符串中最长的数据为标准,而长度不足的在尾部补零即可。

实现代码如下

int getIndex(const string& str, int index)
{
  
    //如果超出字符串长度,则补零
    if(index >= str.size())
    {
  
        return 0;
    }
    return str[index];
}

void RadixSort(vector<string>& arr, int maxLen)
{
  
    vector<string> temp(arr);    //临时数组,用来保留每一趟的结果

	//从字符串尾部的字符依次向前排序
    for(int i = maxLen - 1; i >= 0; i--)
    {
  
        vector<int> count(128, 0);  //统计数组,这里图方便直接给了ascii的前128个

        //统计每种数字出现的次数
        for(int j = 0; j < arr.size(); j++)
        {
  
            int index = getIndex(arr[j], i);
            count[index]++;
        }

        //保证计数排序稳定,对数组变形,统计数组的每一个位置的值为前面所有数字的数量合
        //变形后每个位置的值即为该数据的排序的序号
        int sum = 0;
        for(int j = 0; j < count.size(); j++)
        {
  
            sum += count[j];
            count[j] = sum;
        }

        //按照原数组的数据的位置,倒序将数据放回原位,确保稳定性
        for(int j = arr.size() - 1; j >= 0; j--)
        {
  
            int index = getIndex(arr[j], i);
            temp[count[index] - 1] = arr[j];
            count[index]--;
        }
        arr = temp;	//将临时数据拷贝回原数组,因为下一轮需要借助上一轮的顺序继续排序
    }
}

复杂度

  • 时间复杂度:O(K * (N + M)),N为数据数量,M为字符取值范围,K为执行的计数排序次数。
  • 空间复杂度:O(N + M), N为数据数量,M为字符取值范围