字符串排序使用合并排序 [英] String sorting using Merge Sort

问题描述

这将是排序有 N 字符，每个 N 字符串最坏的复杂性？会不会是刚刚 N 倍的平均。案例为O（n log n）的或其他什么东西......？

What will be the worst complexity for sorting n strings having n characters each? Will it be just n times its avg. case O(n log n) or something else...?

推荐答案

由于@orangeoctopus，使用标准的排序算法对 N 尺寸的字符串<$ C $的集合ç> N 将导致为O（n ^ 2 * LOGN）的计算。

As @orangeoctopus, using standard ranking algorithm on a collection of n strings of size n will result in O(n^2 * logn) computation.

但是 - 请注意，您可以做在为O（n ^ 2），其变化上的基数排序。

However - note that you can do it in O(n^2), with variations on radix sort.

最简单的方法来做到这一点[在我看来 - 是

The simplest way to do it [in my opinion] - is

1. 建立一个线索，并与您的所有字符串填充它。进入 每个字符串 O（N）和你这样做 N 次 - 总的O（ N ^ 2）
2. 在做一个 DFS 字典树上，每次遇到大关结束时间串 - 它添加到排序的集合。加入这样的字符串的顺序是字典顺序，所以你的列表将会字典顺序排序，当您完成。

1. build a trie, and populate it with all your strings. Entering each string is O(n) and you do it n times - total of O(n^2)
2. do a DFS on the trie, each time you encounter the mark for end for string - add it to the sorted collection. The order of the strings added this way is lexicographically, so your list will be sorted lexicographically when you are done.

这是很容易看到你不能做任何更好然后为O（n ^ 2），因为只有读取数据为O（n ^ 2），因此该解决方案是最佳的时间复杂度大O符号表示。

It is easy to see you cannot do it any better then O(n^2), since only reading the data is O(n^2), thus this solution is optimal in terms of big O notation of time complexity.

这篇关于字符串排序使用合并排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！