ソートアルゴリズム(5):高速ソートとその最適化分析

1.クイックソートアルゴリズム
クイックソートアルゴリズム:分治ポリシーに基づいて、分類+再帰的に配列をクイックソートし、一般的に各部分の最初の要素を基準要素として選択します.高速ソートが高速なのは、バブルソートで隣接する要素を比較することに対して、高速ソートは基準値を設定し、ジャンプ式の交換によって基準値より小さい要素と基準値より大きい要素を2つの部分に分け、順序が終わるまで繰り返します.
注意:高速ソートのアルゴリズムはたくさんありますが、私はずっと理解していません.最後にピット+再帰の仕方がわかりやすいことが分かった.
クイックソート手順:
1)基準値を一時変数に格納、このとき基準値位置がピット位になる2)左から右へ比較し、基準値より小さい値を基準値位置に格納と、ピット位置が今回のインデックス終了位置になり、メンテナンスi変数3)を右から左へ比較し、基準値より大きい値を最新のピット位に格納と、ピット位置が今回のインデックス終了位置になるので、メンテナンスj変数4)i>jの場合、1ラウンドの比較が終了し、一時変数の基準値を最後のピットに格納する.5)新たに生成された配列の順序付けが完了するまで、再帰的に順序付けされる.
ピット+再帰的な高速排出プロセスの図解:

は5を基準値として一時変数flagに格納、ソート区間両端インデックスはleft=0、right=6

となる.
0
1
2
3
4
5
6
5
4
3
6
8
2
7

は、左から右へ遍歴する、基準値より小さい値を基準値位置に格納すると、ピット位置が今回のインデックス終了位置となり、インデックス変数i

を維持する.
0
1
2
3
4
5
6
4
ピット位置
3
6
8
2
7

は、右から左に遍歴する、基準値より大きい値を最新のピット位置に格納すると、ピット位置が今回の終了位置となり、インデックス変数j

を維持する.
0
1
2
3
4
5
6
4
2
3
6
8
ピット位置
7

ラウンド終了後、仮変数の基準値を最後のピットに格納します.

0
1
2
3
4
5
6
4
2
3
ピット位置
8
6
7

は、新しく生成された2つの部分配列を、並べ替えが完了するまで、同じ論理の高速並べ替えを行う.

public class QuickSort02 {
	public static void main(String[] args) {
		int[] arr = {2,5,6,3,8,4,9,1};
		quickSort(arr,0,7);
		for (int i : arr) {
			System.out.print(i + ",");
		}
	}
	
	/**
	 *     :               
	 * @param arr      
	 * @param left      
	 * @param right      
	 */
	public static void quickSort(int[] arr,int left,int right) {
		//         
		if(left < right) {
			//          
			int flag = arr[left];
			//            i   j  ，           。
			int i = left;
			int j = right;
			
			while(iflag) {
					j--;
				}
				arr[i] = arr[j];    //   j        i ，        j
				
				//      ，         ，       
				while(i

2.

1） ， ， ；

： ， ， 。

2） O(N^2)。 ， ， logN。 ， ， N ， O(N^2)；

：

3） ， ， ， ， O(N^2)。

： ，

3.

。

O(N^2)， O(N*logN)。 N 。 O(N)， lg(N+1) ， N 。

： ， 。 lg(N+1)。 ， N 。

4.

， O(1) ； ， ：

      ：O(logn)  ； ，

      ：O( n )