インタビュアー: 一般的なソートアルゴリズムは何ですか?違い？

この記事はWeChatの公開アカウント「JS Daily Question」から転載したもので、著者はHuihuiです。この記事の転載についてはJS Daily Question公式アカウントまでご連絡ください。

ソートは、プログラム開発において非常に一般的な操作です。任意のデータ要素のセットをソートした後、それらを特定のルールに従ってソートされた順序付けられたシーケンスに変換できます。

ソートアルゴリズムはアルゴリズムの一種であり、その適用範囲は非常に狭いです。ソートアルゴリズムを徹底的に習得することは、プログラム開発に大いに役立ちます。

ソートアルゴリズムの品質は、主に時間の複雑さ、空間の複雑さ、および安定性から測定されます。

時間の計算量と空間の計算量については、すでに説明しました。ここでは、主に安定性の定義について見ていきます。

安定性とは、ソートするレコードのシーケンス内に同じキーワードを持つレコードが複数ある場合、ソート後もこれらのレコードの相対的な順序が変更されないことを意味します。

つまり、元のシーケンスではr[i] = r[j]であり、r[i]がr[j]の前にあり、ソートされたシーケンスでもr[i]がr[j]の前にある場合、このソートアルゴリズムは安定していると呼ばれ、そうでない場合は不安定と呼ばれます。

一般的なアルゴリズムソートアルゴリズムは次のとおりです。

シンプルで直感的なソートアルゴリズム。ソートする配列を繰り返し処理し、一度に 2 つの要素を比較して、順序が間違っている場合はそれらを交換します。

考え方は次のとおりです。

選択ソートは、シンプルで直感的なソートアルゴリズムです。また、交換ソートアルゴリズムでもあります。

どのようなデータが入力されても、時間の計算量は O(n2) です。そのため、データサイズが小さいほど良いです

唯一の利点は、追加のメモリストレージスペースを占有しないことです。

考え方は次のとおりです。

ソートされていないシーケンス内の最小（最大）要素を見つけ、ソートされたシーケンスの先頭に格納します。

残りのソートされていない要素から最小 (最大) の要素を探し続け、それをソートされたシーケンスの最後に配置します。

すべての要素がソートされるまで手順 2 を繰り返します。

挿入ソートはシンプルで直感的なソートアルゴリズムです

これは、順序付けられたシーケンスを構築することによって機能します。ソートされていないデータの場合は、ソートされたシーケンス内で後ろから前へスキャンし、対応する位置を見つけて挿入します。

解決策は次のとおりです。

ソートする配列をソートされた部分とソートされていない部分に分割します。最初は、最初の要素がソートされていると見なされます。
2 番目の要素から始めて、ソートされたサブ配列内の要素の適切な位置を見つけ、そこに挿入します (挿入する要素が順序付けられたシーケンス内の要素と等しい場合は、挿入する要素を等しい要素の後に挿入します)。
最後の要素が順序付けられたサブ配列に挿入されるまで、上記のプロセスを繰り返す。

マージソートは、マージ操作に基づいた効果的なソートアルゴリズムです。

このアルゴリズムは、分割統治法の非常に典型的な応用です。

順序付けられたサブシーケンスをマージして、完全に順序付けられたシーケンスを取得します。つまり、最初に各サブシーケンスを順序付けし、次にサブシーケンスのセグメントを順序付けします。

解決策は次のとおりです。

クイックソートは、バブルソートアルゴリズムの改良版です。基本的な考え方は、ソートするデータをソートパスを通じて 2 つの独立した部分に分割し、一方の部分のすべてのデータがもう一方の部分のすべてのデータよりも小さくなるというものです。

次に、このメソッドを使用して、データの 2 つの部分を個別にすばやく並べ替えます。並べ替えプロセス全体を再帰的に実行して、データ全体を順序付けられたシーケンスにすることができます。

解決策は次のとおりです。

シーケンスから要素を選択することを「ピボット」と呼びます。
基本値より小さいすべての要素が基本値の前に配置され、基本値より大きいすべての要素が基本値の後に配置されるようにシーケンスを並べ替えます (同じ数字がどちらの側にあってもかまいません)。このパーティションが完了すると、ベンチマークはシリーズの途中になります。これをパーティション操作と呼びます。
基本値より小さい要素の部分列と基本値より大きい要素の部分列を再帰的にソートする