字符串排序----排序算法的选择

对字符串的排序可以使用前面的通用排序算法,但有些专用的字符串排序算法将比通用排序算法效率更高,它们突破了NlogN的时间下界。

算法

是否稳定

原地排序

运行时间

额外空间

优势领域

低位优先的字符串排序

NW

N

较短的定长字符串

高位优先的字符串排序

N到Nw之间

N+WR

随机字符串

三向字符串快速排序

N到Nw之间

W+logN

通用排序算法,特别适用于 含有较长公共前缀的字符串

字母表的长度为R,字符串的长度为N,字符串平均长度为w,最大长度为W。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏互联网杂技

各种排序算法总结

排序算法是最基本最常用的算法,不同的排序算法在不同的场景或应用中会有不同的表现,我们需要对各种排序算法熟练才能将它们应用到实际当中,才能更好地发挥它们的优势。今...

36950
来自专栏用户画像

排序算法 归纳总结

一、直接插入排序、冒泡排序和简单选择排序是最基本的排序方法,它们主要用于元素个数n(n<10000)不是很大的情形。

9120
来自专栏java一日一条

面试中的 10 大排序算法总结

查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗,只...

22930
来自专栏程序员叨叨叨

7.4 输入\输出修辞符(in\out\inout)

参数传递是指:函数调用实参值初始化函数形参的过程。在 C\C++中,根据形参值的改变是否会导致实参值的改变,参数传递分为“值传递(pass-by-value) ...

12510
来自专栏积累沉淀

各种排序算法的总结和比较

1 快速排序(QuickSort) 快速排序是一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序的就地版本。快速排序可以由下面四步组成。...

20460
来自专栏猿人谷

常见排序算法分析

一.常见排序算法的实现 1.冒泡排序 冒泡排序是非常容易理解和实现,,以从小到大排序举例: 设数组长度为N。 1.比较相邻的前后二个数据,如果前面数据大于后面...

21480
来自专栏轮子工厂

八大排序算法稳定性分析,原来稳定性是这个意思...

2、在一趟选择中,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了;

29160
来自专栏JavaEdge

2018-09-04Q:求1+2+3+...+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。方法一:递归实现1+2+..+n;

共同点:一,利用利用短路 && 来实现 if的功能;二,利用递归来实现循环while的功能

14020
来自专栏java思维导图

【一分钟知识】面对对象、基本类型

【一分钟回顾】系列 很多知识都是概念性的东西,有时候你知道这个技术的用法,但未必就能准确地说出它代表的含义与思想。一分钟回顾系列文章会从基础开始到后期的高级,带...

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

P1338 末日的传说

题目描述 只要是参加jsoi活动的同学一定都听说过Hanoi塔的传说:三根柱子上的金片每天被移动一次,当所有的金片都被移完之后,世界末日也就随之降临了。 在古老...

33390

扫码关注云+社区

领取腾讯云代金券