快速排序

快速排序：

通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序。

把整个序列看做一个数组，把第零个位置看做中轴，和最后一个比，如果比它小交换，比它大不做任何处理； 交换了以后再和小的那端比，比它小不交换，比他大交换。

这样循环往复，一趟排序完成，左边就是比中轴小的，右边就是比中轴大的， 然后再用分治法，分别对这两个独立的数组进行排序。

 

快速排序是对冒泡排序的一种本质改进。

不稳定，时间复杂度 最理想 O(n) 最差时间O(n^2)   平均复杂度：O(NlogN)

 

public class QuickSort {
	/**
	 * 获取中轴位置
	 * @param list
	 * @param low
	 * @param high
	 * @return
	 */
	public int getMiddle(Integer[] list, int low, int high) {
		
		// 数组的第一个作为中轴
		int tmp = list[low];
		while (low < high) {
			while (low < high && list[high] > tmp) {
				high--;
			}
			
			// 比中轴小的记录移到低端
			list[low] = list[high];
			while (low < high && list[low] < tmp) {
				low++;
			}
			
			// 比中轴大的记录移到高端
			list[high] = list[low];
		}
		
		// 中轴记录到位
		list[low] = tmp;
		
		// 返回中轴的位置
		return low; 
	}

	public void _quickSort(Integer[] list, int low, int high) {
		if (low < high) {
			
			// 将list数组进行一分为二
			int middle = getMiddle(list, low, high);
			
			 // 对低字表进行递归排序
			_quickSort(list, low, middle - 1);
			
			 // 对高字表进行递归排序
			_quickSort(list, middle + 1, high);
		}
	}

	public void quick(Integer[] str) {
		if (str.length > 0) { 
			// 查看数组是否为空
			_quickSort(str, 0, str.length - 1);
		}
	}

	public static void main(String[] args) {
		Integer[] list = { 34, 3, 53, 2, 23, 7, 14, 10 };
		QuickSort qs = new QuickSort();
		qs.quick(list);
		for (int i = 0; i < list.length; i++) {
			System.out.print(list[i] + " ");
		}
		System.out.println();
	}

}