私は北京で仕事を探しています(二):java実現アルゴリズム<1>バブルソート+直接選択ソート
3944 ワード
仕事を探す.1週間余りの思想闘争を経て、やはりJAVA方面の仕事を探すことにしました.PHPの給料より少し高いようですから.ほほほ:-)(実は私はこれが笑颜で、どんなQQ入力法で、アナログの表情はすべてなくて、とても人间的ではありません.)
本題に戻れば,決めた以上.急いで前の知識を振り返ってみなければなりません.結局、仕事ではなく仕事を探しています.
ランキングは明らかに筆記試験、面接の過程で必ず身につけなければならないものです.
すべてのソートが小さいものから大きいものにデフォルト設定されているとします.
1、泡立ち順
配列長をNとする.
ステップ1:隣接する2つの要素のサイズを比較し、前の要素が後の要素の値より大きい場合は、この2つの要素の位置を交換します.第2ステップ:配列の0番目の要素(0は下付き)からN-1番目の要素を第1ステップの方法で順番に遍歴すると、最大の要素も大きな泡が水面に浮かび上がりやすいように、一番上に「噴き出す」ことができます.第3ステップ:区間範囲を縮小する操作、すなわちN=N-1であり、Nが0でなければ第2ステップの操作を繰り返し、そうでなければソートは完了する.
次に、私たちが言った手順に従って、次のコードを簡単に書くことができます.
public void bubbleSort(int[] arr){
// for
for(int i=0;i<arr.length;i++) {
// for ， 1 ，
for(int j=1;j<arr.length-i;j++) {
if(arr[j-1]>arr[j]) {
// ，
int temp = arr[j-1] ;
arr[j-1] = arr[j] ;
arr[j] = temp ;
}
}//end of for(j)
}//end of for(i)
}コードの交換の2つの要素は、実は小さなポイントでもあり、swap(int num 1,int num 2)の方法を書くと、javaはすべて値伝達であり、予想された結果に達しないことがわかります.やはり配列全体を伝達し,交換する2つの下付き値を伝達することで,交換を書くswap法を実現できるが,やや曲がりくねった感じがするので,ソートfunctionで直接交換したほうがよい.
また、2つの要素の値を交換しても、いろいろな方法があります!!
最も一般的なのは、私が書いたコードのように、中間一時変数tempを新規に作成し、回転に使用し、3ステップで簡単に交換を実現することができます.
int temp = num1;
num1= num2;
num2= temp ;
もう1つの方法は、中間変数を新規作成する必要がなく、1つ目より少し回るかもしれませんが、簡単に理解できます.あまり覚えにくいと思ったら、図を描いて、すぐに覚えて使うことができることを保証しましょう.
num1=num1+num2;
num2=num1-num2;
num1=num1-num2;他にも、小さな方法がたくさんあります.いろいろなことがこのような交換の目的を達成することができます.自分でやってみよう~~~(^記号などでもいい@!)
まとめ:もう一つの価値は、バブルソートでコードを見たことがある人は、原理を知っている人は、その効率が非常に低いことを知っているはずです.
もう2つの最適化方法があり、1つ目は内ループが開始されたときにフラグビットを設定し、ある内ループが一度も交換されていない場合は、ソートが完了したことを示し、2層forループを完全に遍歴してから終了する必要はありません.
2つ目は、前回の内ループを記録したときに最後に交換された要素の下付き文字を記録するレコーダ変数を設定することであり、このレコーダ変数の意味は、あるループの最後に要素交換を行ったサブ説明であり、そのサブの後の要素は必ず秩序があることである.次のラウンドでは、レコーダ変数で識別される下付きの前段を並べ替えるだけでいいので、このようにして、不要な操作を減らすことができるでしょう.
コードは先にあげないで、必ず自分で実現して、原理のコードが自分のコードであることを理解しました.決してわざと知ったふりをしてはいけない,一時の速さを逞しくしてはいけない.
2、直接選択ソート
配列長は依然としてNである.
原理がなくて、私は毛糸を言います!言うまでもなく、まず原理を挙げます:配列を秩序領域と無秩序領域に分けて、無秩序領域の中で1つの最小の要素を選んで直接秩序領域の最後に置きます.無秩序領域に1つの要素がないか、1つの要素しか残っていません.
ステップ1:初期化時、デフォルトの配列はすべて無秩序領域です.ステップ2:無秩序領域で最小値の要素を選択し、秩序領域の後の要素の位置と交換します.交換後、秩序化領域は後に拡張されたようになります.ステップ3:無秩序領域要素の数が0または1になるまで、ステップ2の操作を繰り返し、ソートが完了します.
小二、客官にコードをつけましょう!!!
//
public void selectSort(int[] arr) {
int minIndex = -1 ;
for(int i=0;i<arr.length;i++) {
minIndex = i;//
for(int j=i+1;j<arr.length;j++) {
// ，
if(arr[j]<arr[minIndex]) {
minIndex = j ;
}
}
// ， i minIndex
int temp = arr[i] ;
arr[i] = arr[minIndex] ;
arr[minIndex] = temp ;
}
}
前の2つの要素を交換する問題に戻ります.コードは次のとおりです.
num1=num1+num2;
num2=num1-num2;
num1=num1-num2;前述した2つ目の方法は、コードの仮想マシンでの動作順序の問題が原因なのか、BUGの発生につながるのか、多少のBUGがあります.読者たちは自分で実験してみることができる.私たちの人為的な原理理論は成立しています!しかし、コードのマシン内での動作順序が異なると問題になります.これを同期の問題と言います...
3つ目の交換方法を提供します.
if(num1 != num2) {
num1 ^= num2;
num2 ^= num1;
num1 ^= num2;
}
。 ， 。このビットアルゴリズムに詳しい子供靴はすべて理解するべきです!等しいか同じかの2つの数値演算は0です.これは隠れた危険ではないでしょうか.そして、1万歩下がって言えば、等しいのにどうして席を変えますか.神経よ!運転が速すぎるのが嫌ですか?ほほほ...... 0.0
今日はここまでにしましょう.毎日自分を高め続けなければなりません.今度は試験問題を少し整えて分析します~~~ついでに他のソートアルゴリズムについて話します.特に、直接挿入ソートと直接選択ソートの違いは同じです.
原理を知っているプログラマーだけが良いプログラマーであり、もっと簡単に言うことを覚えておいてください.分からないなら、無理に暗記しなければならない.何で~~そう言うんだよね?何で......きっと......ね......