快速排序

快速排序由于排序效率在同为O(N·logN)的几种排序方法中效率较高，因此经常被采用.想必大家都对此不陌生了。快速排序的主要用到的思想是分治,先从序列中选一个数做为基准数(一般选第一个数),然后把比基准数大的全放到它的右边，比基准数小的全放到它的左边，然后以这个基准数为中心，这样就有了两个区间，左区间和右区间，然后递归对这两个区间再次进行一开始的操作，直到每个区间只有一个数。

手写确实有点迷，这种思维当真是有点难度的。。多年之前，写过快排，那时候感觉理解了，如今再写。。物是人非

public class Main {

	public static void main(String[] args) {
		int arr[] = {1,3,4,2,5};
		quick_sort(arr, 0, arr.length - 1);
		for (int x : arr) {
			System.out.println(x);
		}
	}
	
	public static void quick_sort(int[] arr,int l,int r) {
		if(l < r) {
			int i = l, j = r,baseNum = arr[l];
			
			while(i < j) {
				// 从右向左找第一个小于baseNum的数  
				while(i < j && arr[j] >= baseNum) j--;
				if(i < j) {
					arr[i++] = arr[j];
				}
				// 从左向右找第一个大于等于baseNum的数  
				while(i < j && arr[i] < baseNum) i++;
				if(i < j) {
					arr[j--] = arr[i];
				}
			}
			arr[i] = baseNum;
			//分治
			quick_sort(arr, l, i - 1);
			quick_sort(arr, i + 1, r);
		}
	}
}