利用基数排序LSD方法给等长字符串按字典序排序

利用基数排序LSD方法给等长字符串按字典序排序

0x00 前言

我们都知道将字符串按字典序排序有很多方法，今天我们来谈谈利用如何基数排序的方法排序。

基数排序和计数排序一样，都是桶排序的一种，但是计数排序不太适合将字母排序，所以我们这里使用基数排序。

基数排序简单来说就是将字母拆分为几部分，每个部分排序，这个排序可以从前往后排，也可以从后往前排。本文我们着重介绍从后往前排的情况。

0x01 揭秘逻辑

先细读代码，然后我们再来细聊这段代码。

char str[10][6];
void card_sort( void ){
	char result_array[10][6];
	for(int i = 4;i>=0;i--){
		int count_array[26]={0};
		for(int j=0;j<10;j++){
			int num = str[j][i]-'a';
			count_array[num]++;
		}
		
		for(int j=1;j<26;j++){
			count_array[j] = count_array[j] + count_array[j-1];
		}
		
		for(int j=0;j<10;j++){
			int num = str[j][i]-'a';
			strcpy(result_array[--count_array[num]],str[j]);
		}
		
		for(int j=0;j<10;j++){
			strcpy(str[j],result_array[j]);
		}
	}
}

本段代码的目的是给10个长度为5的英文单词按字典序排列。

设置str字符数组，是用来存储这10个长度为5的单词。

我们设置一个从4到0的for循环，用于区分长度为5的英文单词各个位。

然后将count_array数组初始化。

接下来的两步,是将频率放入count_array内，然后将其转换为索引。

接下了是我认为的最重要的一步了，将元素安装索引分类，这里我们用到result_array这个临时数组来临时存储数据。

该循环每执行完毕一次，就排好一位的字母。

这里第一轮排序结果是：

appla bbbbb applb ccccc applc ddddd appld apple qqqqq zzzzz

这里将count_array自减，是为了填充相同的数据可以填充到上一个空位。前面按频率相加然后转换为索引和这里自减就是实现这一算法的精髓。

最后就是将临时数组里面的数据交给要排列的数组，表示这一位排列成功。

0x02 思考该方法的局限性

动一动你的小脑袋，这种方法有什么局限性？

是啊，从后往前排的话，如果字符串不等长怎么办？

这就有问题了，所以这种标准的基数排序的LSD方法只能对付等长的字符串，如果长度不一定相等的话，我们就要使用基数排序的MSD方法了。

如果本文反响比较好的话，就继续更基数排序的MSD方法来给字符串排序。