クイックソートは、要素(元々は1つを見つけることができる)を参照(ピボット)として見つけ、次に配列を分割して、参照の左側の要素の値が基準値よりも大きくないようにすることです。参照の右側の要素は、基準値に大きくありません。ベンチマークとして使用される要素は、ソート後に正しい位置に調整されます。再帰的に迅速に並べ替えて、他のN-1要素をソート後に正しい位置に調整します。最後に、各要素はソート後に正しい位置にあり、ソートが完了します。したがって、クイックソートアルゴリズムのコアアルゴリズムは、操作を分割することです。つまり、ベンチマークの位置を調整し、再帰を分割および征服するためにリターンベンチマークの最終位置を調整する方法です。
クイックソートのアルゴリズムは次のとおりです。
1)ソートが始まるときに2つの変数iとjを設定します。i= 0、j = n-1;
2)最初の配列要素をキーデータとして使用し、キー、つまりkey = a [0]に割り当てます。
3)jから始めて前方から検索します。つまり、後ろから開始してフォワード(j-)を検索し、キーよりも小さい最初の値を見つけ、[j]と[i]を交換します。
4)backward、つまり前から後方へ(i ++)を開始するためにiから開始し、キーよりも大きい最初のa [i]を見つけ、[i]と[j]を交換します。
5)I = jになるまで手順3と4を繰り返します。 4はjとiの値をキーに変更して、j-1、i = i+1が条件を満たし、交換するときにjポインターの位置を見つけます。さらに、i == jは、I+またはJ-が完了したときに正確に行われ、この時点でループが終了する必要があります。
例を挙げましょう、これは理解しにくいかもしれません。ソートされるシーケンスがあると仮定します
コードコピーは次のとおりです。
パッケージcom.zc.manythread;
java.util.randomをインポートします。
/**
*クイックソート
* @author管理者
*
*/
パブリッククラスQSORT {
int [] date;
public qsort(int [] date){
this.date = date;
}
/**
*交換機能
* @param a
* @param i
* @param J
*/
プライベートボイドスワップ(int a []、int i、int j){
int t;
t = a [i];
a [i] = a [j];
a [j] = t;
}
/***********************
*関数をソートします
* @param a
* @param lo0
* @Param HI0
* @戻る
*/
int [] Quicksort(int a []、int lo0、int hi0){//分割と治療の方法は、配列を[lo0..q-1]と[q+1..hi0]に分割することです。
int lo = lo0;
int hi = hi0;
int mid;
if(hi0> lo0){
mid = a [(hi0+lo0)/2];
while(lo <= hi){
while((lo <hi0)&&(a [lo] <mid))++ lo;
while((hi> lo0)&&(a [hi]> mid)) - hi;
if(lo <= hi){
スワップ(a、lo、hi);
++ lo;
- こんにちは;
}
}
if(lo0 <hi){
QuickSort(A、LO0、HI);
}
if(lo <hi0){
QuickSort(A、LO、HI0);
}
}
aを返します。
}
/****************
*
*重複した配列データを作成します
********************/
private static int [] createdate(int count){
int [] data = new int [count];
for(int i = 0; i <data.length; i ++){
data [i] =(int)(math.random()*count);
}
データを返す;
}
/**
*重複した配列データはありません
* @param count
* @戻る
*/
private static int [] createdate1(int count){
int [] data = new int [count];
ランダムrand = new Random();
boolean [] bool = new boolean [100];
int num = 0;
for(int i = 0; i <count; i ++){
する {
//生成された数値が同じ場合、ループを続けます
num = rand.nextint(100);
} while(bool [num]);
bool [num] = true;
データ[i] = num;
}
データを返す;
}
/************主な機能*****************/
public static void main(string [] args){
final int count = 10;
int [] data = createdate1(count);
for(int n:data){
System.out.print(n+"/t");
}
QSORTデータ1 = new QSORT(data);
System.out.println();
int [] a = data1.quicksort(data、0、count-1);
for(int n:a){
System.out.print(n+"/t");
}
}
}
結果は次のとおりです。
上記は、この記事で説明されているすべてのコンテンツです。