1
O（n^2）より良い時間で実行される挿入ソート以外のものを使用して、リンクされたリストを二重にソートする必要があります。私はクイックソートの使用を考えていましたが、アルゴリズムの理解に問題がありました。私が始めるのを助けるかもしれない何か理解しやすい文書に向けて私を指摘できますか？リンクリストのクイックソートを実装していますか？
A
答えて
2
私は実際にmerge sortをお勧めします。二重にリンクされたリストではより意味をなさないように感じ、O（n log n）のランタイムを持っています。 基本的に、中間を見つけてリストを半分に分割し、各半分をそれぞれソートしてから、2つを線形時間で結合します。
スレッドがあります。hereは、Javaを習得している場合には読み込みが簡単ではないかもしれないが、良い出発点かもしれません。
+0
重要な点は、クイックソートとは対照的に、*最悪の場合のランタイムも 'O（n * log n）'であることです。また、実装が簡単です:) –
関連する問題
- 1. クイックソートの実装
- 2. クイックソートの実装
- 3. Cクイックソート（リンクリスト）セグメンテーションエラー
- 4. クイックソートを実装するヘルプ
- 5. リンクリストの実装でメモリがリークしていますか？
- 6. クイックソートの実装の問題
- 7. Rubyでのクイックソートの実装
- 8. クイックソートjava arraylistの実装
- 9. この同時クイックソートの実装は正しいですか？
- 10. クイックソート3ウェイパーティション+ハイブリッド実装
- 11. リンクリストのクイックソートの実装が配列1よりもずっと遅いのはなぜですか？
- 12. XORリンクリストの実装
- 13. NumberFormatExceptionリンクリストの実装
- 14. プロトタイプ配列のクイックソート再帰関数を実装しています
- 15. クイックソートをCソート構造体で実装しようとしています
- 16. クイックソートを実装する方法は？
- 17. ダブルタイプの値でクイックソートを実装
- 18. クイックソートの実装で何が問題になっていますか？
- 19. Pythonのリンクリストの実装
- 20. リンクリストを使用したキューの実装
- 21. Javaでリンクリストを実装
- 22. 'スレッドセーフな'リンクリストの実装
- 23. 二重リンクリストの実装
- 24. リンクリストの実装ソート方法
- 25. ドットプロダクト計算リンクリストの実装
- 26. クイックソートの実装が期待どおりに動作しない
- 27. これはクイックソートの有効な実装ですか？
- 28. C++でリンクリストを実装するのが難しい
- 29. 矢印を使用したクイックソートの実装で何が問題になっていますか？
- 30. Javaでリンクリストを実装する
におけるアルゴリズムの優れた高レベルの記述[Hungerianフォークダンスを使用してクイックソートの可視のビデオ]（http://www.youtube.com/watch?v=ywWBy6J5gz8）もあります。 –
これを別のデータ構造に抽出してソートすることは許可されていますか、またはそれを適切にソートする必要がありますか？配列への抽出、クイックソートの実行、リンクリストへの戻しは、2n + nlognのようなものでなければなりません。 – captncraig
いいえ、ノードを格納するために他のデータ構造を使用することはできません。 –