快速排序与快速选择

快速排序算法就是将一列无序的数字排成有序，通过使用分治法，快速排序能够在O(nlog(n))的时间内完成，相比堆排序等其他也是O(nlog(n))复杂度的排序算法，快速排序的基数更小，因此效率也就越高。

快速选择是在快速排序的基础上，在一列无序数中快速地计算出第K大的数字，同样使用分治法。快速选择可以避免许多不必要的排序工作。

以下是快速排序的算法实现：

快速排序通过a<b，b<c则a < c的比较传递规则，通过分治法，每一次分治时都实现b左边的数都比b本身小(大)，b右边的数都比b大(小)，同时，将b复制到它应有的位置，通过多次递归，最后转化为两个数或者一个数的排序，从而完成正列数的排序。

快速排序需要选取并确定pivot的位置，并且pivot所在的左边的数都小于或大于pivot，pivot右边的数则相反。因此，通常将快速排序分成以下三个函数：

	public static int[] quickSort1 (int arr[]) {
		int[] temp = copyArr(arr);
		qsort1 (temp, 0, arr.length-1);
		return temp;
	}
	
	private static void qsort1 (int arr[], int start, int end) {
		if (start < end) {
			int spliter = partition1 (arr, start,  end);
			//qsort1 (arr, start, spliter); cause StackOverFlowError
			qsort1 (arr, start, spliter-1);
			//qsort1 (arr, spliter, end); cause StackOverFlowError
			qsort1 (arr, spliter+1, end);
		}
	}
	
	private static int partition1 (int arr[], int start, int end) {
		int pivot = arr[start];
		int b = start, e = end;
		while (b < e) {
			while (b < e && arr[e] <= pivot) e--;
			arr[b] = arr[e];
			while (b < e && arr[b] >= pivot) b++;
			arr[e] = arr[b];
		}
		arr[b] = pivot;
		return b;
	}

以下是快速选择的算法实现：

由于快速排序的每一次排序都实现了pivot的位置的准确定位，并且左边的数都小于（或大于）pivot，那么，对于选择第K大（  小）的数来说，只要和pivot的位置比较一下，如果K比pivot的位置小，则第K大的数一定在pivot的左边，只需要对pivot左边的数再进行一次或多次快速排序就可以找到答案了。

	public static int Select1 (int arr[], int kth) {
		if (kth > arr.length) throw new ArrayIndexOutOfBoundsException("Number not enough to select!");
		int[] temp = copyArr(arr);
		quickSelect1 (temp, 0, temp.length-1, kth-1);
		return temp[kth-1];
	}
	
	private static void quickSelect1 (int arr[], int start, int end, int kth) {
		if (start < end && end >= kth) {
			int spliter = partition1(arr,start,end);
			if (spliter > start && kth < spliter) quickSelect1(arr,start,spliter-1,kth);
			if (spliter < end && kth > spliter) quickSelect1(arr,spliter+1,end,kth);
		}
	}

	private static int partition1 (int arr[], int start, int end) {
		int pivot = arr[start];
		int b = start, e = end;
		while (b < e) {
			while (b < e && arr[e] <= pivot) e--;
			arr[b] = arr[e];
			while (b < e && arr[b] >= pivot) b++;
			arr[e] = arr[b];
		}
		arr[b] = pivot;
		return b;
	}

快速排序的注意点：

1. 快速排序一定要注意，分治递归的时候边界不能有重合。

2. 快速排序每一趟都需要确定pivot的位置，如果仅仅只是比较，但是没有对pivot进行定位，虽然有交换，但是最后排出来的数还是有乱序。