クイックソートアルゴリズムと重複排除を使用したクイックソートを実装するPythonの簡単な例

クイックソートは、どちらもO(N*logN)であるいくつかのソート方法の中でソート効率が高いため、よく使用されます。

この方法の基本的な考え方は次のとおりです:

1.まず、シーケンスから基数として数値を取得します。

2.分割プロセス中、この数値より大きいすべての数値が右側に配置され、この数値以下のすべての数値が左側に配置されます。

3.各間隔に数値が 1 つだけになるまで、左右の間隔に対して 2 番目のステップを繰り返します。

ここで、例を使ってクイック キューを説明しましょう。

たとえば、次のような配列があります:

リーリー

ステップ 1: ベンチマークの数値を選択します。並べ替えは比較に関するものであるため、この用語を怖がらないでください。

たとえば、最後の数値 3 を基数として選択し、配列内の数値を 3 より小さい数値が左側に配置され、3 より大きい数値が右側に配置されます。次の結果が得られます:

リーリー

ステップ 2: 間隔の数を決定します。最初のステップの後、左側の間隔には 1 つの数値しかなく、それと比較する数値がないため、右側の間隔にはまだ操作を繰り返す必要はありません。 :

リーリー

最初のステップを繰り返し、基本数値として 5 を選択し、比較結果を取得します:

リーリー

このように、左右の範囲に数値が 1 つだけあり、並べ替えが完了したことを示します。最後に、すべての範囲を結合して並べ替え結果を取得します。

リーリー

リーリー

リーリー

リーリー

C、C#、JAVAなどよりもずっと簡単ではないでしょうか^.^

ヒント: 重複を削除するためのクイック並べ替え

以下のように、セットを単一値要素に変更するだけで済みます。ここでは Python3 を使用して説明します。
リーリー

出力:

リーリー

並べ替えや重複排除にセットを直接使用することもできます。

リーリー