专栏首页云霄雨霁字符串排序----低位优先的字符串排序

字符串排序----低位优先的字符串排序

基于键索引记数法来实现

低位优先的字符串排序能够稳定地将定长字符串进行排序。

生活中很多情况需要将定长字符串排序,比如车牌号、身份证号、卡号、学号......

算法思路:低位优先的字符串排序可以通过键索引记数法来实现----从右至左以每个位置的字符作为键,用键索引记数法将字符串排序W遍(W为字符串的长度)。稍微思考下就可以理解,因为键索引记数法是稳定的,所以该方法能够产生一个有序的数组。

public class LSD {
    public static void sort(String[]a,int W) {
        int N = a.length;
        int R = 256;
        String[] aux = new String[N];
		//循环W次键索引记数法
        for(int d = W-1; d>=0;d++) {
            int[] count = new int[R+1];
			//键索引记数法第一步--频率统计
            for(int i=0;i<N;i++)
                count[a[i].charAt(d)+1]++;
			//键索引记数法第二步--将频率转化为索引
            for(int r=0;r<R;r++)
                count[r+1]+=count[r];
			//键索引记数法第三步--排序
            for(int i=0;i<N;i++)
                aux[count[a[i].charAt(d)]++] = a[i];
			//键索引记数法第四步--回写
            for(int i=0;i<N;i++)
                a[i]=aux[i];
		}
	}
}

从代码可以看出,这是一种线性时间排序算法,无论N有多大,它都只遍历W次数据。

对于基于R个字符的字母表的N个以长为W的字符串为键的元素,低位优先字符串排序需要访问~7WN+3WR次数组,使用的额外空间与N+R成正比。

下一篇:高位优先的字符串排序

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 字符串排序----三向字符串快速排序

    SuperHeroes
  • 动态联通性问题----union-find算法

    SuperHeroes
  • 加权有向图----一般性单源最短路径问题(Bellman-Ford算法)

    SuperHeroes
  • 面试中可能被问到的常用排序算法

    排序算法是一种比较简单的算法,从我们一开始接触计算机编程开始接触的可能就是排序或者搜索一类的算法,但是因为排序在其他的一些算法中应用较多,所以为了提高性能已经研...

    本人秃顶程序员
  • [数据结构拾遗]字符串排序算法总结

    版权声明:本文为博主原创文章,转载请注明原文地址链接。 https://blog.csdn.net/qqxx6661/article/details/8...

    后端技术漫谈
  • 疯子的算法总结(六) 复杂排序算法 ② 桶排序

    从《基于比较的排序结构总结 》中我们知道:全依赖“比较”操作的排序算法时间复杂度的一个下界O(N*logN)。但确实存在更快的算法。这些算法并不是不用“比较”操...

    风骨散人Chiam
  • leetcode454. 4Sum II

    现有四个等长且无序的整数数组,先要求从这四个数组中分别取一个数字,使得它们的和为0,问这四个数组中共有多少满足条件的数字集合。

    眯眯眼的猫头鹰
  • MySQL数据库数据信息迁移

    环境内核信息: [root@zabbix-01 ~]# uname -a Linux lodboyedu-01 2.6.32-696.el6.x86_64 #1...

    863987322
  • kubernetes(十三) k8s 集群监控

    Prometheus(普罗米修斯)是一个最初在SoundCloud上构建的监控系统。自2012年成为社区开源项目,拥有非常活跃的开发人员和用户社区。为强调开源及...

    alexhuiwang
  • 【HDU 4614】Vases and Flowers(线段树区间更新懒惰标记)

    题目 0到n-1的花瓶,操作1在下标a开始插b朵花,输出始末下标。操作2清空[a,b]的花瓶,求清除的花的数量。 线段树懒惰标记来更新区间。 操作1,先查询0到...

    饶文津

扫码关注云+社区

领取腾讯云代金券