字符串排序

文章目录
  1. 1. 键索引排序
  2. 2. 低位优先的字符串排序
  3. 3. 高位优先的字符串排序

算法4 官网地址

键索引排序

说明: a[] 中存储待排序的数据,字符串名字,组号(我们作为键),组号在0~R-1,取出组号的方式:a[i].key()

  1. 计算各组的频率count[r+1]++;
  2. 频率转索引 count[r] = count[r-1] + count[r]
  3. 数据分类
  4. 回写

低位优先的字符串排序

如果字符串的长度均为W,那就从右向左以每个字符作为键,用键索引计数法将字符串排序W遍。

理解的方法是向前看:如果有两个键,他们中还没有被检查过的字符都完全相同,不同之处取决于已经检查过的字符,因为两个键已经排序,有序。另外,如果还没有被检查过的部分不同,那么已经被检查过的字符对于两者的最终顺序没有意义。之后的某轮会保证有序。

高位优先的字符串排序

首先用键索引计数法将所有字符串按照首字母排序,然后递归的再将每个首字母所对于的子数组排序。