基本的なソート方法には、 1. 選択ソート (「単純選択ソート」と「ヒープ ソート」に分かれる)、 2. 挿入ソート (「単純挿入ソート」と「ヒル ソート」に分かれる) があります。 ; 3. Exchange ソートは「バブル ソート」と「クイック ソート」に分かれます; 4. マージ ソート; 5. 基数ソート。
#基本的な並べ替え方法
並べ替え
#いいえソートアルゴリズムはどのような状況でも最適であり、問題を解決するには実際の状況に応じて最適なアルゴリズムを選択する必要があります。
アルゴリズムの安定性: ソート対象のレコードのセット内に、等しいレコードが 2 つある場合R と S であり、ソート対象のレコードでは、R が S の前にあります。ソート後も R がまだ S の前にある場合、つまり、ソートの前後で前後の位置が変わらない場合、ソート アルゴリズムは安定と呼ばれます
単純な選択ソート
単純な選択ソートは直感的です。ソート アルゴリズムは、未ソートのシーケンス内の最小の要素を選択してシーケンスの最初の要素と交換し、次に残りの未ソートのシーケンス内の最小の要素を選択してシーケンスの 2 番目の要素と交換する、というように続きます。小さいものから大きいものまでが形成されます。
時間計算量: O(N2)
ヒープ ソート
順序付けされていないシーケンスを最大のヒープに生成し、ヒープの先頭を入れ替えます。要素を最後の要素と交換し、残りの要素で最大ヒープを生成します 要素を順番に交換し、最大ヒープを生成します
時間計算量: O(NlogN) 空間計算量: O(1)
単純挿入ソート
ソート対象の配列の集合をソートに分割する 2つあります初期状態では、ソートされたシーケンスには最初の要素のみが含まれ、未ソートのシーケンスの要素は最初の要素を除いて N-1 個の要素になります。その後、未ソートのシーケンスの要素が 1 つずつ追加されます. ソートされたシーケンスに挿入します。このようにして、N-1 回の挿入後、未ソート シーケンスの要素数が 0 になり、ソートが完了します。
時間計算量: O(N2) 安定したソート
ヒル ソート
ソート対象の要素の集合を一定間隔でいくつかの配列に分割し、それぞれ挿入ソートを実行します。最初に設定した「間隔」は大きく、ソートの各ラウンドで間隔は「間隔」が 1 になるまで徐々に減少します。つまり、最後のステップでは単純な挿入ソートが実行されます。
時間計算量: と増分 シーケンスの選択は非安定ソートに関連しています
バブルソート
要素の場合 ソート対象の N 個のシーケンスをソートする場合、合計 N-1 サイクルが実行されます。 k回目のループでは、1番目からN-k番目までの要素を前から後ろに比較し、その都度隣り合う2つの要素を比較し、前者の要素が後者の要素より大きい場合、2つの要素の位置を入れ替えます。それ以外の場合は、位置は変更されないままになります。
時間計算量: O(N2)
クイック ソート
「ピボット」を基礎として、ソートされていない要素を 2 つのサブシーケンスに分割します。一方のサブシーケンスのレコードはすべてピボットより大きく、もう一方のサブシーケンスのレコードはピボットより小さい場合、2 つのサブシーケンスは同様の方法を使用して再帰的に並べ替えられます。
時間計算量: O(Nlog2N)
サイズ N のシーケンスを長さ 1 の N 個のサブシーケンスとして扱います。 次へ 隣接するサブシーケンスをペアでマージします。長さ 2 (または 1) の N/2 (1) 個の順序付きサブシーケンスを形成し、その後、隣接するサブシーケンスをペアでマージし続けます。ループを続けると、長さ N のシーケンスが 1 つ残る場合、このシーケンスは元のシーケンスをソートした結果
#時間計算量: O(Nlog2N) 空間計算量: O(N)
N 個のキーワードの値の範囲が 0 から M-1 で、M が N よりはるかに小さいことがわかっている場合、バケット ソート アルゴリズムは、キーワードの値ごとに「バケット」、つまり M 個のバケットが作成されます。N 個のキーワードをスキャンすると、各キーワードが対応するバケットに配置され、自然に順序付けされるバケットの順序で収集されます
基数ソート
基数ソートはバケット ソートを一般化したもので、ソート対象のレコードには複数のキーワードが含まれるとみなされます
以上が基本的な並べ替え方法は何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
