JAVAクイックソートプロセス図解(10ステップ以内)
4167 ワード
くだらないことは言わないで、以下は図解して高速の順序付けのアルゴリズムを説明して、そしてJAVAコードを添付します
「3 4 7 2 4 3 1 4 5 9」という10個の数をすばやく並べ替えると
ステップ1では、まず基準数を設定します.この基準数は任意の位置で指定できます.ここでは、最初の数を基準数、すなわち3として選択します.ここでは赤で表示します.
3
4
7
2
4
3
1
4
5
9
ステップ2では、左右の2つのポインタを設定します.ここでのポインタは本物のポインタではなく、2つの検出器です.左の検出器leftは左の1位から基準数より大きい数を探し、右の検出器rightは右の1位から基準数より小さい数を探します.簡単に言えば、左のポインタは大きい数を探し、右のポインタは小さい数を探します.ここで注意しなければならないのは、右ポインタで先に探す必要があることです.
3
4
7
2
4
3
1
4
5
9
left right
ステップ3、右ポインタを先に
3
4
7
2
4
3
1
4
5
9
left right
第4歩、1対3を探し当てて小さくて、止まって、今左のポインタまで探し始めます
3
4
7
2
4
3
1
4
5
9
left right
第5歩、今彼らはすべて探し当てて、彼らが今指している数を交換します
3
1
7
2
4
3
4
4
5
9
left right
次に、右のポインタを先に行って、2つのポインタが出会うまで、つまりleft>=rightの時、彼らが出会ったことを代表して、次の位置は
3
1
7
2
4
3
4
4
5
9
left right
スワップ
3
1
2
7
4
3
4
4
5
9
left right
さあ、今rightはもう一歩歩いてleftと出会ったので、彼はまたleftここに止まった.
3
1
2
7
4
3
4
4
5
9
left
right
止まったら、基準数と交換します
2
1
3
7
4
3
4
4
5
9
left
right
これにより、クイックソートの最初のソートが完了し、はっきり言えば基準数を最終的に適切な位置に置き、左は基準数より小さい数、右は基準数より大きい数、次はこの配列を基準数によって左右の2つの数グループに分けて、それぞれ前の方法でソートすることができ、この段階では再帰形式を採用することができる.
一部の学友は闻いて、あなたのこの乱数は极端ではありませんて、それは例えば私が1つの“1 4 2 3 5”を设置して、このような1つの乱数を比较して、简単に言えば、第1の基准数1は最も小さいため、しかし私达は知らないで、私达はやはり针が先に行って、ずっと左の针と出会って、つまり1の位置まで歩いて、この时更に交换して、1と1が交換され、再帰的な流れに入ります.すなわち、「1」と「4 2 3 5」の2つの配列に分かれ、前の手順を繰り返します.
コード実装:
まとめ:高速ソートアルゴリズムは実際には難しくなく、多くの初心者がこのアルゴリズムに触れたばかりのとき、彼がどのようにソートした後、どのように再帰したのか、それから突然ソートしたのか分からないと思っていました.実際には、高速ソートアルゴリズムがどのように再帰されるのか、なぜ再帰されるのかをどのように知る必要はありません(ここでは、再帰で使用される配列アドレスは常に同じであり、異なるのは、上のポインタが指す位置だけです).その再帰フローは最初と同じであるため、最初のソートの流れを理解する必要があります.最も重要な3つのオブジェクト、データム数、右ポインタ、左ポインタをすばやくソートすることを覚えておいてください.
「3 4 7 2 4 3 1 4 5 9」という10個の数をすばやく並べ替えると
ステップ1では、まず基準数を設定します.この基準数は任意の位置で指定できます.ここでは、最初の数を基準数、すなわち3として選択します.ここでは赤で表示します.
3
4
7
2
4
3
1
4
5
9
ステップ2では、左右の2つのポインタを設定します.ここでのポインタは本物のポインタではなく、2つの検出器です.左の検出器leftは左の1位から基準数より大きい数を探し、右の検出器rightは右の1位から基準数より小さい数を探します.簡単に言えば、左のポインタは大きい数を探し、右のポインタは小さい数を探します.ここで注意しなければならないのは、右ポインタで先に探す必要があることです.
3
4
7
2
4
3
1
4
5
9
left right
ステップ3、右ポインタを先に
3
4
7
2
4
3
1
4
5
9
left right
第4歩、1対3を探し当てて小さくて、止まって、今左のポインタまで探し始めます
3
4
7
2
4
3
1
4
5
9
left right
第5歩、今彼らはすべて探し当てて、彼らが今指している数を交換します
3
1
7
2
4
3
4
4
5
9
left right
次に、右のポインタを先に行って、2つのポインタが出会うまで、つまりleft>=rightの時、彼らが出会ったことを代表して、次の位置は
3
1
7
2
4
3
4
4
5
9
left right
スワップ
3
1
2
7
4
3
4
4
5
9
left right
さあ、今rightはもう一歩歩いてleftと出会ったので、彼はまたleftここに止まった.
3
1
2
7
4
3
4
4
5
9
left
right
止まったら、基準数と交換します
2
1
3
7
4
3
4
4
5
9
left
right
これにより、クイックソートの最初のソートが完了し、はっきり言えば基準数を最終的に適切な位置に置き、左は基準数より小さい数、右は基準数より大きい数、次はこの配列を基準数によって左右の2つの数グループに分けて、それぞれ前の方法でソートすることができ、この段階では再帰形式を採用することができる.
一部の学友は闻いて、あなたのこの乱数は极端ではありませんて、それは例えば私が1つの“1 4 2 3 5”を设置して、このような1つの乱数を比较して、简単に言えば、第1の基准数1は最も小さいため、しかし私达は知らないで、私达はやはり针が先に行って、ずっと左の针と出会って、つまり1の位置まで歩いて、この时更に交换して、1と1が交換され、再帰的な流れに入ります.すなわち、「1」と「4 2 3 5」の2つの配列に分かれ、前の手順を繰り返します.
コード実装:
//
public static void quickSort(int[] datas,int left,int right){
if(lefttemp){// , ,
int num=datas[p1];
datas[p1]=datas[p2];
datas[p2]=num;
p2--;
}else{
p1++;
}
}else{
p2--;
}
}
//
datas[left]=datas[p1];// left right left
// right , left
datas[p1]=temp;
quickSort(datas, left, p1);//
quickSort(datas, p1+1, right);
}
}
public static void main(String[] args) {
int length=10;
int[] list= new int[length];
// 10
for(int i=0;i
まとめ:高速ソートアルゴリズムは実際には難しくなく、多くの初心者がこのアルゴリズムに触れたばかりのとき、彼がどのようにソートした後、どのように再帰したのか、それから突然ソートしたのか分からないと思っていました.実際には、高速ソートアルゴリズムがどのように再帰されるのか、なぜ再帰されるのかをどのように知る必要はありません(ここでは、再帰で使用される配列アドレスは常に同じであり、異なるのは、上のポインタが指す位置だけです).その再帰フローは最初と同じであるため、最初のソートの流れを理解する必要があります.最も重要な3つのオブジェクト、データム数、右ポインタ、左ポインタをすばやくソートすることを覚えておいてください.