数据结构与算法学习五：快速排序

一. 排序方法

1. 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
2. 分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。原排序数组data[0...n]。
   1. 分解：在data[low..high]中任选一个记录作为基准(pivot)，以此基准将当前无序区划分为左、右两个较小的子区间data[low..pivotpos-1]和data[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录pivot，右边的子区间中所有记录的关键字均大于等于pivot，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。
   2. 递归：data[low..high]被划分为两个子区间data[low..pivotpos-1)和data[pivotpos+1..high]，而每个子区间采用相同的方法再次划分为两个子区间...
   3. 组合：因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。

二. 动画演示

     http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/kuaisupaixu.htm

三.Java代码 

/**
	 * 快速排序
	 * @param data
	 * @param low data最小下标
	 * @param high data最大下标
	 * @return
	 */
	public static int[] quickSort(int[] data, int low, int high) {
		// 对data[low..high]快速排序
		int pivotpos; // 划分后的基准记录的位置
		if (low < high) {// 仅当区间长度大于1时才须排序
			pivotpos = partition(data, low, high); // 对data[low..high]做划分
			quickSort(data, low, pivotpos - 1); // 对左区间递归排序
			quickSort(data, pivotpos + 1, high);// 对右区间递归排序
		}
		return data;
	}

	/**
	 * 划分算法，划分后
	 * 左边子区间中所有记录的关键字均小于等于基准记录pivot
	 * 右边的子区间中所有记录的关键字均大于等于pivot
	 * 基准记录pivot则位于正确的位置上
	 * @param data
	 * @param i
	 * @param j
	 * @return
	 */
	public static int partition(int[] data, int i, int j) {
		// 并返回基准记录的位置
		int pivot = data[i]; // 用区间的第1个记录作为基准 ，
		while (i < j) { // 从区间两端交替向中间扫描，直至i=j为止
			while (i < j && data[j] >= pivot) {
				// pivot相当于在位置i上
				j--; // 从右向左扫描，查找第1个关键字小于pivot的记录data[j]
			}
			if (i < j) // 表示找到的data[j]的关键字<pivot
				data[i++] = data[j]; // 相当于交换data[i]和data[j]，交换后i指针加1

			while (i < j && data[i] <= pivot) {
				// pivot相当于在位置j上
				i++; // 从左向右扫描，查找第1个关键字大于pivot的记录data[i]
			}
			if (i < j) // 表示找到了R[i]，使data[i]>pivot
				data[j--] = data[i]; // 相当于交换data[i]和data[j]，交换后j指针减1
		} // endwhile
		data[i] = pivot; // 基准记录已被最后定位
		return i;
	}

四.时间复杂度和稳定性

1. 最好时间复杂度
   1. 在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：

      0(nlogn)

2. 最坏时间复杂度
   1. 最坏情况是数组有序时，每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。

      因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：

      C_max=n(n-1)/2=O(n²)

3. 平均时间复杂度
   1. 0(nlogn)
4. 算法的空间复杂度：快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O(lgn)，故递归后需栈空间为O(lgn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。
5. 快速排序是非稳定的，例如[2，2，1]。