秋招準備-アルゴリズム-ソート(合計)

1.
Ques:簡単な説明選択ソート
選択ソートは、各サイクルで極値を選択し、ソートされていない領域の端点と交換することで、ソートを完了します.
例えば、第1ラウンドで最小値を選択し、このときの未ソート領域が0~n-1であれば、この最小値を0番配列要素と交換してソートを完了し、このようにして、外ループがn回後にソートを完了する.
中間変数:最小値をソートするたびにtemp、最小値のインデックスindexを保存します.
2.
Ques:挿入ソートの簡単な説明
指定されたレコードのセットについて、最初のレコードをソート済みシーケンスとして設定し、残りのレコードを無秩序シーケンスとして設定し、2番目のレコードから順番にシーケンスの対応する位置に挿入します.最後の無秩序シーケンスの挿入が完了すると、ソートが完了します.
比較は、挿入するエレメントが自分の位置を判断するときにソートされたシーケンスのエレメントとの比較で発生します.
3.
Ques:泡立ちソートの簡単な説明
バブルソートの特徴は元素が上昇することであり、アルゴリズム上で表現すると、k回目のサイクル時に、まだソートされていない元素を左から右に2回比較し、両者の間が大きいのは右側であることを保証し、大きいのは右側で1回交換することで、ソートされていない元素が比較を完了した後、ソートされていない要素の最大値は右端に上昇し、この最大値はソートを完了し、残りの要素を記録が1つしか残っていないまで繰り返します.
4.
Ques:集計ソートの簡単な説明
再帰と分治に用いられ,シーケンスをますます小さい半サブテーブルに分割し,さらに半サブテーブルを並べ替え,最後にシーケンスを撮った半サブテーブルをますます大きな秩序シーケンスに統合する.
シミュレーションダイアログ:
私は一般的に集計ソートを紹介します.また、集計の考え方が簡単だからです.それは、小さなサブテーブルに分けて、サブテーブルを並べて、統合することです.これは抽象的です.具体的な実現の上で実は更に再帰と分岐の思想を体現することができます.
例えば、1~8の要素があるとしたら、私たちは再帰の底から言えば、彼らを絶えず二分した後、1,2,3,......8つの単独のシーケンスになります.このシーケンスは私たちの心の中に定義されています.実際には彼らはまだ配列の中で動いていません.それはどのようにこの抽象的なサブシーケンスを統合したのでしょうか.操作すると、1と2番要素を2つの配列を追加して保存し、この2つの配列をサブシーケンスと見なし、この2つのサブシーケンスを2つのルートで集計し、実際の配列の1、2番のビットに並べ替えます.
では、3、4番、5、6番、7、8番も同じ理屈で、最下層のサブテーブルのソートが完了し、さらに上のサブシーケンスが1、2になります.3,4......そして,この4つのサブテーブルのシーケンスはいずれも2つの並べ替えを経て秩序化され,次いでこの4つのサブテーブルに対して2つの並べ替えを行い,最後に2つの秩序化サブテーブルになり,もう一度2つの並べ替えを経て結果が得られた.
これは最下層の再帰の過程で、それでは再帰関数の書き方は先に分けて後に合わせて、分けて再帰呼び出し自身で、合わせは別の関数を書いて、サブシーケンスを合併して、具体的な実現の中で、1つの中間量が実は簡単であることを理解すれば、その中間量は、サブテーブルを分割する時、与えた最初と最後のシーケンス番号の平均値で、最初のシーケンス番号からこの中間量までは、分割された左サブテーブルであり、中間量から最後のシーケンス番号までは分割された右サブテーブルであり、どの2つの配列が集計されているかを2つの配列で集計する際に、この2つのサブテーブルとして使用され、抽象的な分割と集計のプロセスが完了します.
現場実装:
⑴.再帰的な構造を覚える

public void MergeSort(int[] arr,int start,int end)
	{
		if(start

(2)二重集計集計サブテーブルを実現するMerge()

public void Merge(int[] arr,int start,int mid,int end)
	{
		if(start>=end)
			return ;
		//     ，         ，    
	
		//       start~mid       
		//       mid+1~end       
		//                start~end   
	}

5.
Ques:クイックソートの簡単な説明
速い列は分治を採用して、私の理解は、1つのベンチマークの値を見つけて、このベンチマークの値が満たす条件は、その左側の値はすべてそれより小さくて、その右側の値はすべてそれより大きくて、この値を見つけた後に、更に両側の部分に対して上述の操作を続けます.
このロッド値は実は順番を並べた後、その要素が位置しているので、ロッド値を決定することは要素の位置を決定し、小さなサブテーブルに分解し続けた後、2つの要素しかない場合、1つの値の位置を決定し、この2つの要素のソートを完了し、実際にはすべての区間に対してロッド値を求め、これでソートが完了します.
ポイント:スティック値の検出方法
一般的には、最初のレコードをスケール値として、その位置を探してindexでこの値を記録してから検索を開始します.
命令j=end.右から探しますが、a[j]がindexより小さい場合は、a[i],a[j]を交換します.このとき、値はa[j]に移動し、a[i]は指定された領域にあり、i++である.
そしてiから、左から右に探して、a[i]がindexより大きい場合は、a[i],a[j]を交換します.このとき、値はまたa[i]に戻り、a[j]は指定された領域にあり、j--;
上記の操作を繰り返し、常にiを保証する
i=jの場合、このときのa[i]またはa[j]は値であり、すでに中間位置にある.
実装:
たんほうこうこうかんインプリメンテーション

	public static void sort(int arr[],int start,int end)
	{
		int i = start;
		int j = end;
		while(ii ，a[k]>=a[i]   
		{
			while(i=index  
			if(istart)	        sort(arr,start,i-1);
		if(end>i+1)		sort(arr,i+1,end);
	}

双方向交換実装ですが、詳細に注意してください.

public static void sort(int arr[],int start,int end)
	{
		int i = start+1;
		int j = end;
		int index = arr[start];
		while(iindex)		 j--;    //  j  arr[j]<=index
			while(arr[i]=index
			if(i>=j) break;    //    ，1.j=start,   arr[start]     2.i=j，     arr[start]      
			if(istart)	        sort(arr,start,i-1);
		if(end>i+1)		sort(arr,i+1,end);
	}

6.
Ques:ヒルソートの簡単な紹介
ヒルソートは縮小増分ソートとも呼ばれ、補間の一種であり、原理はまずソートされる配列要素を複数のサブシーケンスに分割し、これらのサブシーケンスを公差の異なる等差数列として理解し、その後、これらのシーケンスに対して挿入ソートを完了し、最後の公差が1になるまで、公差を小さくして繰り返し操作し、実際には挿入ソートを行う.しかし、このとき要素は基本的に秩序化されており、公差が大きい場合、ジャンプ式の移動により、比較と交換の回数が大幅に減少するため、効率の向上を実現することができる.
実装:
三層サイクルの初期h,i,jがどういう意味なのかを把握し,簡単に実現できる.
hは公差であり、length/2を1までとることができる.自分で指定することもできますが、最後に1があればいいです.
hが一定の場合、0~h-1はそれぞれこれらの数列の最初の要素であり、h~len-1は対応する数列に挿入できる要素であり、iはそれらを遍歴する責任を負う
a[i]は対応する配列に挿入する必要がある要素であり、jは対応する数列と比較し、挿入操作を実行し、a[i]が存在する配列シーケンスはi,i-h,i-2 hであるべきである.

	public static void shellSort(int arr[])
	{
		int length = arr.length;
		int i,j,h;
		for(h=length/2;h>0;h=h/2)
		{
			for(i=h;i=0;j-=h)	//  a[i]
				{
					if(arr[j]>temp)
						arr[j+h]=arr[j];
					else 
						break;
				}
				arr[j+h]=temp;
			}
		}
	}

7.
Ques:スタックのソートの簡単な説明