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

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

该算法思路与高为优先的字符串排序算法几乎相同,只是对高位优先的字符串排序算法做了小小的改进。

思路:根据键的首字母进行三向切分,然后递归地将三个子数组进行排序。

三向字符串快速排序实现并不困难,只需对三向快排代码做些修改即可:

代码中的charAt(String[] a,int d)方法是获取下标d处的字符,exch()是交换函数。

public class Quick3string {
    private static int charAt(String s, int d) {
        if(d<s.length())return s.charAt(d);
        else return -1;
    }
    public static void sort(String[] a) { sort(a,0,a.length-1,0); }
	
    public static void sort(String[] a,int lo, int hi, int d) {
        if(hi<=lo)	return;
        int lt = lo, gt = hi;
        int v = charAt(a[lo], d);
        int i = lo+1;
        while(i<=gt) {
            int t = charAt(a[lo],d);
            if(t<v)	exch(a,lt++,i++);
            else if(t>v)	exch(a,i,gt--);
            else i++;
        }
        sort(a,lo,lt-1,d);
        if(v>=0) sort(a,lt,gt,d+1);
        sort(a,gt+1,hi,d);
    }
}

相对于高位优先字符串算法的优点

  1. 高位优先字符串算法可能会创建许多的空数组(前缀相同的情况下),但本算法总是只有三个;
  2. 本算法不需要额外的空间。
  3. 要将含有N个字符串的数组排序,三向字符串快速排序需要比较字符~NlnN次。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mathor

十大经典排序算法(动图演示)

不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面。 时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。 ...

2.2K40
来自专栏ACM算法日常

HDU1106:排序 (重新修正)

之前发过一篇HDU 1106的题目,但是因为有童鞋说那篇的源码提交后超时,我们的AlphaWA童鞋重新做了一遍,这次是0ms!算是修正之前的问题,非常感谢~

9210
来自专栏数据结构与算法

快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记...

34170
来自专栏数据结构与算法

24:单词的长度

24:单词的长度 总时间限制: 1000ms 内存限制: 65536kB描述 输入一行单词序列,相邻单词之间由1个或多个空格间隔,请对应地计算各个单词的长度。...

33650
来自专栏前端儿

前缀式计算

输入有多组测试数据,每组测试数据占一行,任意两个操作符之间,任意两个操作数之间,操作数与操作符之间都有一个空格。输入的两个操作数可能是小数,数据保证输入的数都是...

17110
来自专栏武培轩的专栏

Leetcode#1.Two Sum(两数之和)

题目描述 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。 示例: 给定 nums ...

34670
来自专栏机器学习和数学

[编程经验] Python 中列表list介绍

列表是Python中非常重要的一种数据结构,使用频率非常高,本文主要介绍对于学习python的新手来说,需要掌握的一些基础知识。 1. 创建列表 ? 列表用中括...

38650
来自专栏数据结构与算法

26:字符串最大跨距

26:字符串最大跨距 总时间限制: 1000ms 内存限制: 65536kB描述 有三个字符串S,S1,S2,其中,S长度不超过300,S1和S2的长度不超过...

45680
来自专栏PHP在线

php面试题(二)

1 <?php echo count (false); $a = count ("567") + count(null) + count(false); ec...

45180
来自专栏AI派

TensorFlow 修炼之道(1)——张量(Tensor)

TensorFlow名字可以拆解为两部分:Tensor、Flow。其中,Tensor 就表示张量。

51540

扫码关注云+社区

领取腾讯云代金券