詳細--クイックソート---javaコードの追加
O(N*logN) ， ， ---- ， ， ， IT ， ， 。総じて言えば、直接暗記して急速に並べ替えるのはやはり一定の難易度があって、本人が自分の理解について急速に並べ替えることに対して白話の解釈をしたため、みんなに理解して役に立つことを望んで、急速に並べ替えて、急速に解決します.
クイックソートは、1962年にC.R.A.Hoareが提案した区分交換ソートである.分割法(Divide-and-ConquerMethod)と呼ばれる分割法を採用しています.
この方法の基本的な考え方は:
1.まず、数列から1つの数を基準数として取り出します.
2.パーティション化プロセスでは、この数より大きい数を右に、それより小さい数または等しい数を左にすべて配置します.
3.各区間が1つになるまで、左右の区間について2番目のステップを繰り返す.
高速ソートを分治法と呼ぶが,分治法という3つの字は高速ソートのすべてのステップをうまく要約できないことは明らかである.そこで、私の迅速なソートについてさらに説明しました.穴を掘って数を埋める+分治法です.
まず例を見てみましょう.定義は以下に示されます(自分の話で定義をまとめることができれば、コードを実現するのに役立ちます).
1つの配列を例として、区間の最初の数を基準数とします.
0
1
2
3
4
5
6
7
8
9
72
6
57
88
60
42
83
73
48
85
初期時、i=0; j = 9; X = a[i] = 72
a[0]の数をXに保存したので、配列a[0]に穴を掘ったと理解でき、他のデータをここに埋め込むことができる.
jからXより小さいかXに等しい数を探します.j=8で条件を満たすと、a[8]を掘り出して前のピットa[0]に記入する.a[0]=a[8]; i++;このような穴a[0]は解決されたが、また新しい穴a[8]が形成された.これはどうしたのか.簡単で、a[8]という穴を埋めるために数字を探します.今回はiからXより大きい数を後ろに探し、i=3で条件に合致した場合、a[3]を掘り出して前の穴にa[8]=a[3];j--;
配列:
0
1
2
3
4
5
6
7
8
9
48
6
57
88
60
42
83
73
88
85
i = 3; j = 7; X=72
上の手順を繰り返して、まず後ろから前へ探して、それから前から後ろへ探します.
jから前へ探し、j=5で条件に合致した場合、a[5]を掘り出して前の穴に埋め、a[3]=a[5];i++;
iから後ろに探し、i=5の場合、i=jで終了する.
このとき,i=j=5であり,a[5]はちょうど前回掘った穴であるため,Xをa[5]に埋め込む.
配列:
0
1
2
3
4
5
6
7
8
9
48
6
57
42
60
72
83
73
88
85
a[5]の前の数字はすべてそれより小さく、a[5]の後ろの数字はすべてそれより大きいことがわかる.したがって、a[0...4]とa[6...9]の2つのサブ区間について上記の手順を繰り返すとよい.
ピット埋め込み数をまとめる
1．i =L; j = R; 基準数を掘り出して最初のピットa[i]を形成する.
2.j--それより小さい数を後ろから前へ探し、見つけたらこの数を掘り出して前の穴a[i]に記入する.
3.i++は、それより大きい数を前から後ろに探し、見つけた後も前のピットa[j]に埋め込む.
4.i=jまで2,3の2ステップを繰り返し、基準数をa[i]に記入する.
このまとめに従って、ピットの記入数のコードを簡単に実現します.
[cpp] view plain copy
int AdjustArray(int s[],int l,int r)/調整後の基準数の位置を返す
{
int i = l, j = r;
int x=s[l];//s[l]すなわちs[i]が最初のピットである
while (i
{
//右からxより小さい数を探してs[i]を記入する
while(i = x)
j--;
if(i
{
s[i]=s[j];//s[j]をs[i]に埋め込むと、s[j]は新しいピットを形成する.
i++;
}
//左からx以上の数を探してs[j]を記入する
while(i
i++;
if(i
{
s[j]=s[i];//s[i]をs[j]に埋め込むと、s[i]は新しいピットを形成する
j--;
}
}
//終了時、iはjに等しい.xをこのピットに埋め込む. s[i] = x;
return i;
}
分割法のコードを書き直す:
[cpp] view plain copy
void quick_sort1(int s[], int l, int r)
{
if (l
{
int i=AdjustArray(s,l,r);//先成掘削穴埋め法調整s[]quick_sort 1(s,l,i-1);//再帰呼び出し quick_sort1(s, i + 1, r);
}
}
このようなコードは明らかに簡潔ではなく、その組み合わせを整理します.
[cpp] view plain copy
//クイックソートvoid quick_sort(int s[], int l, int r)
{
if (l
{
//Swap(s[l],s[(l+r)/2]);//中間のこの数と最初の数を交換する注1 参照
int i = l, j = r, x = s[l];
while (i
{
while(i=x)/右から左へx未満の最初の数を探します
j--;
if(i
s[i++] = s[j];
while(i//左から右へ最初のx以上の数を探します
i++;
if(i
s[j--] = s[i];
}
s[i] = x;
quick_sort(s,l,i-1);//再帰呼び出し quick_sort(s, i + 1, r);
}
}
高速ソートには、ランダムに基準数を選択するなど、区間内のデータが少ない場合に直接別の方法でソートして再帰深さを低減する改良バージョンがたくさんあります.興味のある筒は、さらに深く研究することができます.
注1、本によっては中間の数を基準数としているものもありますが、この便利さを実現するには非常に便利で、直接中間の数と最初の数を交換すればいいのです.
転載は出典、原文住所を明記してください.http://blog.csdn.net/morewindows/article/details/6684558
自分で書いたjavaコード:
package quickSort; public class main {public void dayin(int a[]){for(int i=0;iSystem.out.print(a[i]+"-");}System.out.println();}public void quicksort(int a[],int l,int r){if(lint i=l,j=r;int x=a[i];while(i//xより小さい数を右から左に探してa[i]while(ix)j--//a[0]より小さい数を見つける;if(ia[i]=a[j]//a[0]より小さい数をa[0];i+//左から右へx以上の数を探してa[j]while(iif(ia[j]=a[i];////a[i]をa[j]に記入すると、a[i]は新しいピットj--を形成する;}}a[i]=x;//////////////////////////////////////////////////////////////////////////a[i]をa[j]に記入する.quicksort(a,l,i-1)////////////////////再帰呼び出し快速シーケンスiより前の数quicksort(a,i+1,r)//////////////////////////再帰呼び出し快速ソートiより後の数}public args) {//TODO Auto-generated method stubint a[]={72,6,57,88,60,42,83,73,48,85,1};main main=new main();main.quicksort(a, 0, a.length-1);main.dayin(a);} }