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

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

一. 排序方法

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

?

二. 动画演示

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

?

四.时间复杂度和稳定性

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

最坏时间复杂度
最坏情况是数组有序时，每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。
因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：
Cmax = n(n-1)/2=O(n2)
平均时间复杂度
0(nlogn)
算法的空间复杂度：快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O(lgn)，故递归后需栈空间为O(lgn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。快速排序是非稳定的，例如[2，2，1]。