[DataStructure]Quick Sort(快速排序法)

目前公認最快的排序法，雖然最壞的時候還是會衝到O(n^2)，不過大部份還是很快的(Quick Sort的速度與基準點的選擇有關)

Quick Sort分為幾個步驟
以{41,24,76,11,45,64,21,69,19,36}這個陣列為例

1.先將最左邊的數41當成基準點(s)
2.索引 I 由左邊向右找，一直找到大於基準點(s)的數
3.索引 J 由右邊向左找，一直找到小於基準點(s)的數
4.如果 I >= J 就跳出迴圈。如果 I < J，array[I]和array[J]交換 6.基準點與array[J]交換，這時 J 因為第3步驟的關係，會一直找到小於基準點的數(這時 I 已 >= J，雖迴圈跳出了，但 J 的值還在)
7.對基準點左邊及右邊進行相同步驟的遞迴

I 找到比基準點大的、J 找到比基準點小的
[41],24,76(I),11,45,64,21,69,19,36(J)
I、J交換，繼續往下找
[41],24,36,11,45(I),64,21,69,19(J),76
I、J交換，繼續往下找
[41],24,36,11,19,64(I),21(J),69,45,76
I、J交換且繼續往下找，但是 I >= J 所以會break，這時 J 停留在21
[41],24,36,11,19,21(J),64,69,45,76
基準點與 J 交換
21,24,36,11,19,[41],64,69,45,76
最後再以基準點左右兩邊做相同遞迴

Java

public class test{
	static int [] num = {41,24,76,11,45,64,21,69,19,36};
	public static void main(String [] argv){
		quick_sort();
		for(int i : num){
			System.out.print(i + " ");
		}
	}
	//Quick Sort Start
	public static void quick_sort(){
		sort(0,num.length-1);
	}
	//Recursion
	public static void sort(int left, int right){
		//確定是否可以排序
		if(left < right){
			int i = left;
			int j = right + 1;
			while(true){
				//向右找，直到找到比基準點大的
				while(i + 1 < num.length && num[++i] < num[left]);
				//向左找，直到找到比基準點小的
				while(j - 1 >= 0 && num[--j] > num[left]);
				if(i >= j) break;
				swap(i,j);
			}
			//基準點與j交換(這時候的j已經跑到比基準點小的數了)
			swap(left,j);
			//遞迴排序基準點左半邊
			sort(left, j - 1);
			//遞迴排序基準點右半邊
			sort(j + 1 , right);
		}
	}
	//交換
	public static void swap(int i, int j){
		int temp = num[i];
		num[i] = num[j];
		num[j] = temp;
	}
}