視覚的直感的な感覚 7つのよく使われる並べ替えアルゴリズム

戦略を書いているとき,プログラムコードは必ずデータ整理の必要性を遭遇します. では,最小限のシステム費用 (時間,システムリソース) で科学的なプログラムを設計するにはどうすればよいですか?

• ### 1. 素早く並べ替える

インタビュー: 急速排列は,トニー・ホールが開発した排列アルゴリズムである.平均的な状況では,n個の項目を排列するには,Ο (n log n) 回の比較が必要である.最悪の状況では,Ο (n) 回の比較が必要であるが,この状況は一般的ではない.実際,急速排列は,通常,他のΟ (n log n) のアルゴリズムよりも明らかに速い.それは,その内部ループ (inner loop) が,ほとんどのアーキテクチャで非常に効率的に実現でき,そして,ほとんどの現実世界のデータで,設計選択を決定し,必要な時間の二次性の可能性を減らすことができるからである. ステップ: 列から1つの要素を選択し,それを基准軸 (pivot) と呼び, 列を並べ替え,基数より小さい要素はすべて基数の前に置き,基数より大きい要素はすべて基数の後に置き (((同じ数の基数はどちらにも行ける).この区画が退出した後,この基数は列の中間位置にある.これは区画 (((partition)) 操作と呼ばれている. 累乗的に ((recursive) 基数要素より小さい子数列と,基数要素より大きい子数列を並べます. 順序付け効果:

• ### 2. 順序を整える

インタビュー: 合併ソート (Merge sort) は,合併操作に基づいた有効なソートアルゴリズムである.このアルゴリズムは,分割法 (Divide and Conquer) を採用した非常に典型的なアプリケーションである. ステップ: リクエストスペース,その大きさを2つの既に排列されたシーケンスの合計に,そのスペースは合併後のシーケンスを格納するために使用 2つの指針を設定し,最初の位置は2つの順序付けされた順序の開始位置です. 2つの指針が指す要素を比較し,相対的に小さい要素を合体空間に入れて,指針を次の位置に移動する ステップ3を繰り返します. 他の配列の残りの要素を 配列の末尾に直接コピーする 順序付け効果:

• ### 3. 堆積する

インタビュー: ハイプソート (Heapsort) は,このデータ構造を利用して設計された並び算法である. ハイプソートは,ほぼ完全な二叉樹の構造であり,同時に,ハイププロパティを満たす:すなわち,子ノードのキー値またはインデックスは,常にその父ノードより小さい (または大きい) である. ステップ: オンラインで調べてみてください. 順序付け効果:

• ### 4. 選択した順番

インタビュー: 選択ソート (Selection sort) は,シンプルで直感的なソートアルゴリズムである.その動作原理は以下の通りである.まずは,未整理の序列の中で最小の要素を見つけ,その序列の開始位置に保存し,それから,残った未整理の要素から最小の要素を探し続けて,その序列の末尾に保存する.そして,すべての要素が整理が完了するまで,このように推論する. 順序付け効果:

• ### 5. 泡状の排列

インタビュー: バブルソート (Bubble Sort,台湾語訳:泡のソート,または泡のソート) は,単純なソートアルゴリズムである.これは,何度も何度も,順番を入れ替えるために,一度に2つの要素を比較し,その順番が間違っていれば,それらを交換する.列を訪問する仕事は,交換が不要になるまで繰り返し行われ,すなわち,その列はソートされている.このアルゴリズムの名前は,より小さな要素が,交換によってゆっくりと列の頂上に浮上するからである. ステップ: 隣接する要素を比較する.最初の要素が2つ目の要素より大きい場合,その2つを交換する. 隣接する要素の各ペアに対して同じ作業を,最初のペアから最後のペアまで行う.この時点で,最後の要素は最大数であるべきである. 上の手順を,最後のものを除いて,すべての要素に対して繰り返します. 上の手順を,数値のペアを比較する必要がなくなるまで,ますます少ない要素ごとに繰り返します. 順序付け効果:

• ### 6. 挿入する

インタビュー: 挿入ソート (Insertion Sort) のアルゴリズムの説明は,シンプルで直感的な排列アルゴリズムである.その動作原理は,並べられた配列を構築し,未並べられたデータに対して,並べられた配列の中で後ろから前へスキャンして,適切な位置を見つけ,挿入することである.挿入ソートを実装すると,通常,in-place排列 (in-place sort) を採用する (つまり,O (−1) の余分なスペースを使用する排列),したがって,後から前へとスキャンする過程で,並べられた要素を徐々に後方に移動して,最新の要素に挿入スペースを提供する必要がある. ステップ: この要素は,最初の要素から始めると,既に並べられていると考えられます. 次の要素を取り出し,並べた要素の列から前後にスキャンします. この要素が新しい要素より大きい場合は,次の位置に移動します. 新しい要素の位置より小さいまたは等しい並べられた要素を見つけるまでステップ3を繰り返す この位置に新しい要素を挿入します. ステップ2を繰り返します. 順序付け効果: (現時点では)

• ### 7. ヒル・ソリエーション

インタビュー: ヒルソート (Hill sort) は,挿入式ソートメントの高速で安定した改良版である. ヒル・ソートメントは,挿入ソートメントの以下の2つの性質に基づいて改善方法を提案した. 1 挿入式は,ほぼ排列されたデータに対して操作する際の効率が高く,すなわち,線形排列の効率を達成できる 2 しかし,挿入式は一般的に低効率です.挿入式はデータ移動を1回に1回しか行いません.

泡泡法 (最もシンプルな方法) を一番よく使っていますが,あなたは?