クイックソートアルゴリズムの実装と最適化

[[385051]]

この記事はWeChatの公開アカウント「Beta Learns JAVA」から転載したもので、著者はSilently9527です。この記事を転載する場合は、Beta Learning JAVA パブリックアカウントにお問い合わせください。

この記事は Github リポジトリ https://github.com/silently9527/JavaCore に含まれています。

プログラマーがよく使用する IDEA プラグイン: https://github.com/silently9527/ToolsetIdeaPlugin

完全にオープンソースの Taobao プロジェクト: https://github.com/silently9527/mall-coupons-server

序文

クイックソートは、最も広く使用されているソートアルゴリズムと言えます。その主な特徴は、インプレースソート (補助配列が不要で、スペースを節約) に基づいていることです。実際、長さ N の配列にクイックソートを使用する場合の時間計算量は NlogN です。以前の記事では他のソートアルゴリズムについても説明しましたが、いずれもこれら 2 つの機能を組み合わせることができませんでした。

簡単な並べ替えのアイデア

クイックソートも分割統治ソートアルゴリズムであり、配列を 2 つのサブ配列に分割し、サブ配列を再帰的にソートして、最終的に配列全体が整列していることを保証します。

アルゴリズムのアイデア:

分割要素（通常は配列の最初の要素）をランダムに選択します。
配列の左側からスキャンして分割要素以上の値を見つけ、配列の右側からスキャンして分割要素以下の値を見つけ、2つの値を交換します。
このプロセスは、左と右のポインタが出会うまで繰り返され、分割された要素の左側の値がその値よりも小さく、右側の要素がその値よりも大きくなるように要素が配置されます。
このプロセスは再帰的に繰り返され、配列全体が正しい順序になっていることが保証されます。

アルゴリズムの実装

クイックソートアルゴリズムの考え方に従って、実装の最初のバージョンを記述できます。

パブリッククラス QuickSort は SortTemplate を実装します {
    @オーバーライド
パブリックvoid ソート(比較可能な[] 配列) {
        クイックソート(配列、0、配列の長さ - 1);
    } 
 
    プライベートvoid quickSort(Comparable[]配列、 int lo、 int hi) {
        （最低 >= 最高）の場合{
戻る;
        }
 intパーティション = パーティション(配列、lo、hi);
        quickSort(配列、lo、パーティション - 1);
        クイックソート(配列、パーティション + 1、hi);
    } 
 
    プライベートintパーティション(比較可能な[]配列、 int lo、 int hi) {
 int i = lo、j = hi + 1;
        比較可能なel = array[lo];
        （真）の間{
            while (less(配列[++i], el)) {
                もし（i == hi）{
                    壊す;
                }
            }
            while (less(el, 配列[ --j])) {  
                もし（j == lo）{
                    壊す;
                }
            }
            もし (i >= j) {
                壊す;
            }
            exch(配列、i、j);
        }
        exch(配列, lo, j);
 jを返します。
    }
 }

このコードはクイックソートの従来の実装です。最悪のケースとして、ソートする配列がすでに [1,2,3,4,5,6,7,8] の順序になっている場合、クイックソートを実行するプロセスは図のようになります。

長さ N の配列の場合、最悪の場合、再帰が N-1 回必要になるため、時間の計算量は O(n2) になります。この状況を回避するために、アルゴリズムを改善する方法を見てみましょう。

アルゴリズムの改善

ランダム性を確保し、最悪の状況を回避するには、2 つの方法があります。1 つ目は、配列を並べ替える前にランダムにシャッフルすることです。2 つ目は、パーティションメソッドで分割要素を最初の要素ではなくランダムに選択することです。簡単な実装:

プライベートintパーティション(比較可能な[]配列、 int lo、 int hi) {
 int i = lo、j = hi + 1;
 int random = new Random().nextInt(hi - lo) + lo;
    exch(配列、lo、ランダム);
    比較可能なel = array[lo];
    （真）の間{
        while (less(配列[++i], el)) {
            もし（i == hi）{
                壊す;
            }
        }
        while (less(el, 配列[ --j])) {  
            もし（j == lo）{
                壊す;
            }
        }
        もし (i >= j) {
            壊す;
        }
        exch(配列、i、j);
    }
    exch(配列, lo, j);
 jを返します。
 }

挿入ソートへの切り替えはマージソートと同じです。小さな配列の場合は、直接挿入ソートに切り替えます。

プライベートvoid quickSort(Comparable[]配列、 int lo、 int hi) {
    （最低 >= 最高）の場合{
戻る;
    } 
     
    if (hi - lo < 5) { //テスト、5未満の場合、挿入ソートに切り替える
        挿入ソート(配列、lo、hi);
戻る;
    } 
 
 intパーティション = パーティション(配列、lo、hi);
    quickSort(配列、lo、パーティション - 1);
    クイックソート(配列、パーティション + 1、hi);
 } 
 
 // ソートを挿入
プライベートvoid挿入ソート(比較可能な配列[]、 int lo、 int hi) {
 ( int i = lo; i <= hi; i++) {
 for ( int j = i; j > lo && less(array[j], array[j - 1]); j --) {  
            exch(配列、j、j - 1);
        }
    }
 }

3 方向の分割ソートする必要がある配列内に多数の繰り返し要素がある場合、実装するクイックソートでは、再帰中に完全に繰り返されるサブ配列が多数発生します。それでもアルゴリズムでは分割されるため、改善の余地が大いにあります。

アイデアは、まず分割要素 (el) をランダムに選択し、次に配列を 3 つの部分 (より大きい、等しい、より小さい) に切り替えることです。1 回の再帰で、分割要素に等しいすべての値をソートできます。ポインタ lt と gt を維持して、a[lo..lt-1] が分割要素より小さく、a[gt+1..hi] が分割要素より大きくなるようにします。

変数を初期化します: lt=lo、i=lo+1、gt=hi
a[i] < el の場合、a[i] と a[lt]、i++、lt++ を入れ替える
a[i] > el の場合、a[gt] と a[i] を入れ替え、gt--
a[i] == el; i++

コード実装:

パブリッククラス Quick3waySort は SortTemplate を実装します {
    @オーバーライド
パブリックvoid ソート(比較可能な[] 配列) {
        クイックソート(配列、0、配列の長さ - 1);
    } 
 
    @SuppressWarnings( "チェックなし" )
    プライベートvoid quickSort(Comparable[]配列、 int lo、 int hi) {
        （最低 >= 最高）の場合{
戻る;
        }
 int lt = lo、i = lo + 1、gt = hi;
        比較可能なel = array[lo];
        (i <= gt) の間 {
 int tmp = el.compareTo(配列[i]);
            （tmp > 0）の場合{
                exch(配列、lt++、i++);
            }それ以外の場合 (tmp < 0) {
                exch(配列、i、gt --);  
            }それ以外{
                私は++;
            }
        }
        クイックソート(配列、lo、lt - 1);
        クイックソート(配列、gt + 1、hi);
    }
 }