ディレクトリ
コンセプト
クイックソートはその名の通り、高速な効率性を特徴とするソートアルゴリズムで、バブルソートを改良したものです。1960年にイギリスのコンピュータ専門家トニー・ホールによって提案されました。
基本的な考え方
ソートされた配列から、ランダムに、あるいは固定された位置（通常は最初か最後）で、ベンチマークと呼ばれる数値を見つけます。そして、基準より小さいものを左に、大きいものを右に置きます；
どのようにそれを配置するには、つまり、左の交換は、ベンチマークよりも小さく、右はベンチマークよりも大きいので、2つのサブアレイに配列された後、同じようにサブアレイは、より小さなサブアレイに分割され、それが分解することができるまで、交換のためのベンチマーク番号です。データ全体を順序付けられた配列にすること。
クイックソートは、パーティショニングと呼ばれる分割戦略を使います。これは現在、さまざまな言語に付属するソートライブラリの多くで使われています。
空間の複雑さ
クイックソートは、補助空間として非常に小さなスタックしか必要としないインプレースソートで、空間複雑度がO(log2n)であるため、データセットが比較的大きい場合に適しています。
時間の複雑さ
時間の複雑さはより複雑で、最良の場合でO(n)、最悪の場合でO(n2)です。
- O(n)：理想的には、各分割で選択される中間テーブルの数は、現在のシーケンスをほぼ均等に正確に分割し、log2n回の分割の後、長さ1のサブテーブルが得られます。従って、アルゴリズム全体の時間複雑度はO(nlog2n)です。
- O(n2)：最悪の場合、毎回選択される中間数は、現在のシーケンスで最大または最小の要素であるため、各分割の結果のサブテーブルの1つは空のテーブルになり、もう1つのサブテーブルの長さは元のテーブルの長さ-1になります。したがって、長さnのデータテーブルを高速にソートするには、分割にn回行く必要があり、ソートアルゴリズム全体の時間複雑度はO(n2)になります。
アルゴリズムのステップ
1. 基準となる数値を中心点として選択します；
2. ピボットより大きい数値をピボットの左側に置きます；
3.ピボットより小さい数をピボットの右側に配置します；
4.最初のソートが終わると、左と右のサブシーケンスはそれぞれ最初の3つのステップを再帰的に繰り返します。
具体例
インスタンスの配列： arr[] = {19, 97, 9, 17, 1, 8}；
1.基準数Pivotを取り出し、その値を中心軸とします。
クイックソートのルール：右側にピットがある場合は、左側のArr[L + n]から値を取って埋めます；
2.ベンチマーク値の左側から、Arr[L]の左側は空です、値の右側から最初の右添え字を埋めるために、Arr[R]で、最初から "8 "の最初の値に；
3.Arrの[R]とベンチマーク値の比較を取り、ベンチマーク値よりも小さいことが判明し、Arrの[R]に挿入され、ベンチマーク値ピボットの位置を占めます。
4.次に、Arr[L+1]の位置から値を削除し、マッチングとソートを右へ続け、マッチした値を右のArr[R]の空の位置に挿入します；
マッチングルール：基準値より大きい値はArr[R]に挿入され、小さい場合はそのまま無視されてスキップされ、座標Lと座標Rが一致するまで右側の値を取り続けます。
5.取り出された値がPivotより大きいことが確認されると、Arr[R]に挿入されます。
6.左側にピットがあるので、右側のArr[R-1]からマッチングを続け、Arr[R-1]=1と基準値より小さい値をArr[L]のピットに挿入します；
7.ピットの右側は、一致し続けるために左から値を取り続ける、それはArr [L + 1]=9に取られ、ベンチマーク値よりも小さい、それは無視され、スキップされ、一致し続けるためにArr [L + 1]を探し続けます。
8.マッチングを続けるために、左の座標+1から値を取り続けます。Arr [L] = 17と取られ、基準値より小さい場合は無視されスキップされます。
9.最後に、L座標とR座標が一致し、ピボット基準値が入力されます。
10.この時点で、左右の副列に分けられる急速な分類の完全なプロセスの最初の円形の終わりはピボット基準値、右ピボット基準値より大きいより左よりより少しです。
11.**再帰的に左と右のサブシーケンスを処理するために続けて、左と右に絞り込まれている値は、高速ソートの終了、順序配列の最終結果{1,8,9,17,19,97};**中間再帰的なプロセスは、ここでは繰り返されません。
高速行コード
@java
package com.softsec.demo;
/**
* Created with IDEA
*
*
*
* @Description
* @Version 1.0
*/
public class quickSortDemo {
public static void main(String[] args) {
// テスト配列を作成する
int[] arr = new int[]{19,97,9,17,1,8};
System.out.println("ソート前:");
showArray(arr); // 配列を印刷する
// 高速スケジューリング・インターフェースを呼び出す
quickSort(arr);
System.out.println("
" + "ソート後:");
showArray(arr);// 配列を印刷する
}
/**
* クイックソート
* @param array
*/
public static void quickSort(int[] array) {
int len;
if(array == null
|| (len = array.length) == 0
|| len == 1) {
return ;
}
sort(array, 0, len - 1);
}
/**
* 再帰的に実装された高速行のコアアルゴリズム
* @param array
* @param left
* @param right
*/
public static void sort(int[] array, int left, int right) {
if(left > right) {
return;
}
// baseベンチマークの数を
int base = array[left];
int i = left, j = right;
while(i != j) {
// 順番は重要で、右から始めて、基準値より小さい数字が見つかるまで左に向かっていく。
while(array[j] >= base && i < j) {
j--;
}
// 基準値より大きな数字が見つかるまで、左から右へもう一度検索する。
while(array[i] <= base && i < j) {
i++;
}
// 上記のループの終わりは、その場所が見つかったか、あるいは（i>=j)配列中の2つの数値の位置を入れ替える
if(i < j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
// データを真ん中に置く
array[left] = array[i];
array[i] = base;
// 再帰的に、上記と同じ操作を行い、データムの左辺と右辺に続ける。
// iは上記で特定されたデータム値の位置であり、再度処理する必要はない。
sort(array, left, i - 1);
sort(array, i + 1, right);
}
/**
* 配列印刷
* @param num
*/
private static void showArray(int[] num) {
for (int i = 0; i < num.length; i++) {
System.out.print(num[i] + " ");
}
}
}
結果を返します：
ソート前
19 97 9 17 1 8
ソート後
1 8 9 17 19 97
Process finished with exit code 0
@python
#クイックソート リスト、開始位置、終了位置を渡す
def quick_sort( li , start , end ):
# もしstartとendが一致したら、ソートしようとしているサブカラムには数字が1つしか残っていないということなので、ソートする必要はない。
if not start < end :
return
mid = li[start] #最初の数を取り、それを基数としてmidを計算する。
low = start #low基数から左辺の位置をマークして、midより大きい数を見つける。
high = end #high右端を左端にマークして、midより小さい数の位置を見つける
# ループさせるには、lowとhighが一致しない限り続け、lowとhighが等しくなったら一致させる。
while low < high :
#高い方から左に向かって、真ん中より小さいか等しい最初の数を見つけ、その位置に印をつける。
# もしローとハイが出会ったら、それは探されていない。
while low < high and li[high] > mid :
high -= 1
#whileから飛び出すとき、highがある添え字は、右辺にあるmidより小さい数である。
#見つかった数字を左の空白に入れる。
li[low] = li[high]
# 低い方から右に向かって、真ん中より大きい最初の数字を見つけ、その位置に印をつける。
# もしローとハイが出会ったら、それは探されていない。
while low < high and li[low] <= mid :
low += 1
#whileループを抜けたときにlowがある添え字は、midより大きい左側の数字である。
# 見つかった数字を右の空いたスペースに置く。
li[high] = li[low]
#上記は一度だけ行われた。 右から小さな数を見つけて左に移動し、左から大きな数を見つけて右に移動する。
#whileが飛び出すと、lowとhighの出会いに相当し、空いたスペースにmidの位置が置かれる。
li[low] = mid
#この時点で、midの左側に表示されている数字はすべてmidより小さく、midの右側に表示されている数字はすべてmidより大きい。
#次に、midの左側にある数字を上記のようにソートする。
quick_sort( li , start, low-1 )
#mid右側の数字はすべて上記のようにソートされている
quick_sort( li , low +1 , end )
#入力関数
if __name__ == '__main__':
li = [19,97,9,17,1,8]
quick_sort(li , 0 , len(li) -1 )
print(li)
