5

I'd like to know if there's some faster way to sort such array than quicksort/mergesort.

Maximum array's length is 10^6. Word's length is >=10 and <= 100 and the word can contain a-z and spaces (27 different characters in total). Characters are not unique in the words (they can repeat). All the words in an array are equally long.

4

5 に答える 5

8

You can put all the words in a trie (or a radix tree), and then print it in a DFS order, starting from the "smaller" lexicographical letter at each level in the DFS.

This solution will be O(n* |S|) where |S| is the average string length.

Simple example:

Let the set of strings be [ac,ab,aca]:

The resulting trie will be:

         a
       /  \
      /    \
     b      c
     |     / \
     $    $   a
              |
              $

And a DFS (which prefers lexicographically smaller characters): The DFS will start from a, go to b, and then to the end sign ($) and will first print ab, then go back to a, and right to c, and to the next $ sign, and will print ac, and next to a and its $ and will print aca, resulting in printing: 

ab
ac
aca

As expexted.

于 2012-10-28T14:59:31.277 に答える
1

基数ソートと基数トライについての回答を読んだ（そして賛成した）ので、非常に有益です。
だが。
基数ソートの場合-N個の要素を91回パスする必要があるため、91*Nになります。私は追加のスペースについて話しているのではありません。
マージソートの場合、N * log Nの比較があり、log N = log 1000000〜20なので、20*Nの比較が得られます。

では、どちらが速いのでしょうか？:)それとも、どこかで間違えたのでしょうか？

于 2012-10-28T16:15:23.330 に答える
1

比較ベースの並べ替えの下限は O(nlog(n)) です。この制限よりも低い最悪のケースで実行される、要素を相互に比較することに基づく並べ替えアルゴリズムを使用することはできません。

マージソートとヒープソートの両方の最悪の場合の実行時間は O(nlog(n)) です...そしてクイックソートの最悪の場合の実行時間は O(n^2) ですが、平均実行時間は O(n^ログ (n))。

クイックソートの実行時間は最悪で O(N^2) ですが、定数係数が小さいため (ヒープソートのように) O(nlog(n)) の実行時間で他のアルゴリズムを打ち負かすことがあります。現在のマシン アーキテクチャでの効率的な実行に適しています。

非比較ベースで線形時間 O(n) で整数 (ただし、それらに限定されない) を並べ替えることができる線形並べ替えアルゴリズム (例: カウント並べ替え、バケット並べ替え、および基数並べ替え)

MSD 基数ソートは、辞書式の数字 (この場合は文字) の順序を使用して、左から右に文字列をソートできます。

すべての文字列を最初に別の線形ソート アルゴリズム (バケット ソートなど) を使用して左端の文字を使用してソートし、次に左から 2 番目の文字を使用して再度ソートし、右端の文字でソートされるまで続けます。最後に、配列は完全にソートされます。

このアルゴリズムの実行時間は O(k*N) です。ここで、N は要素の数、k は平均キー長です (この場合、ワード長は >=10 && <=100 になります)。

于 2012-10-28T15:18:43.647 に答える
0

3 文字ごとの分散ソートではないのはなぜですか。それには 19683 (27*27*27) 要素のカウント ストレージが必要であり、これは実現可能なはずであり、最大で 34 パスが必要です。

しかしすぐに、キーごとのサブリスト (3 文字の倍数) は、残りの文字列に対して挿入ソートなどを使用できるほど短くなります。1.000.000/(27^3) は約 50

共通の長いプレフィックスがある場合、つまり、最初の 30 文字でリストが 20 または 30 のサブリストに分割される場合、同じメカニズムを長いキーで使用できます。次に、キーを数値ではなく文字列として表現し、ディクショナリに格納します。これは低速ですが、必要なパスが少なくなり、メモリも少なくなる可能性があります。また、バイナリ ツリー内の異なるキーの数が M の N*log(M) ルックアップが必要ですが、ハッシュも可能です。

于 2013-05-14T14:53:27.827 に答える
0

アスキー値は計算できるため、基本的にこれは整数ソートです。比較ベースのソート ルーチンは、せいぜい O(n lg n) - マージ ソート (サイズ n/2 の配列をさらに 2 つ作成するために追加のスペースが必要) または最悪でも O(n^2) (挿入ソート、クイックソート、しかし追加のスペースの複雑さはありません)。これらは、線形ソート アルゴリズムよりも漸近的に遅くなります。CLRS ( http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844 ) を見ることをお勧めします。線形時間でのソートに関する章。このシナリオでは、おそらく O(n) が最適です。また、この投稿が役立つ場合があります。線形時間でソートしますか?

基数ソートをチェックします。http://en.wikipedia.org/wiki/Radix_sort

于 2012-10-28T15:04:35.613 に答える