Java算法之快速排序

快速排序的基本思想：

通過一趟排序将待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分關鍵字小，則分别對這兩部分繼續進行排序，直到整個序列有序。

快速排序的示例：

（a）一趟排序的過程：

（b）排序的全過程

把整個序列看做一個數組，把第零個位置看做中軸，和最後一個比，如果比它小交換，比它大不做任何處理；交換了以後再和小的那端比，比它小不交換，比他大交換。這樣循環往複，一趟排序完成，左邊就是比中軸小的，右邊就是比中軸大的，然後再用分治法，分别對這兩個獨立的數組進行排序。

基準數：一般指定第一個元素為基準數（任意元素都可以作為基準數）。

//快速排序
public class QuickSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 };
		quickSort(arr, 0, arr.length - 1);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + ",");
		}
	}

	public static void quickSort(int[] arr, int frist, int last) {
		if (frist > last)
			return;// 遞歸出口
		int i = frist;
		int j = last;
		int temp = arr[frist]; // 基準數
		while (i != j) {
			while (arr[j] >= temp && j > i) { // 從右開始尋找小于基準數的元素
				j--;
			}
			while (arr[i] <= temp && i < j) { // 從左開始尋找大于基準數的元素
				i++;
			}
			if (i < j) { // 找到了小于和大于基準數的數
				int t = arr[i];
				arr[i] = arr[j];
				arr[j] = t;
			}
		}
		if (i == j) { // 找到了中間數，交換基準數與中間數
			arr[frist] = arr[i];
			arr[i] = temp;
		}
		// 遞歸
		quickSort(arr, frist, j - 1); //對于數組中小于中間數的部分進行遞歸排序
		quickSort(arr, i + 1, last);  //對于數組中大于中間數的部分進行遞歸排序
	}
}