前言

最後一天了，但好像連一半都還沒講完哈哈哈QQ，我們結束了初等排序的部分，最後想跟大家介紹的是 Quick Sort 快速排序，高等排序跟初等的差別在於時間複雜度，所以我們可想而知，高等的排序效率會比初等排序來的優秀。那依照慣例，我們先從觀念開始，再接著講解演算法，GoGo

Divide and conquer

Quick Sort
採用Divide-and-conquer方法，所以我們先來看看這個方法是在作甚麼
step 1. 將問題拆分成子問題
step 2. 每個子問題求解
step 3. 將子問題的結果合起來變完整結果

觀念

1. 選定最左邊的元素作為pivot
2. 進行partition，找出pivot正確位置
3. 左右重複執行此三條
   接著

• i 左邊往右開始找出大人國
• j 右邊往左開始找出小人國
• 找到之後判斷有沒有交合 (i小於j即沒有交合)，SWAP(a[i],a[j])
• 若i>j的話要進行pivot跟j交換的立碑SWAP

演算法

public class QuickSort{
	public static void main(String... args){
		int[] a = {6,8,40,2,5,25,1000000};
		int l = 0;
		int u = 5;
		int pk_idx = 0; // pivot index
		QuickSort(a,l,u);
		for(int item :a){
			System.out.print(item+",");
		}
	}

	public static void QuickSort(int[] a,int l,int u){ // l is pivot
		int i = l+1;
		int j = u;

		if(l<u){
			while(i<=j){
				while(a[i]<a[l]){
					i+=1;
				}	// find the a[i] bigger than pk
				while(a[j]>a[l]){
					j-=1;
				}	// find the a[j] small than pk
				if (i<j){
				 	swap(a,i,j);
				}
			}
			swap(a,l,j);
			QuickSort(a,l,j-1);
			QuickSort(a,j+1,u);
		}
	}

	public static void swap(int[] a, int i, int j){
		int temp = 0;
		temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}