1、快速排序
同归并排序一样，快排也使用了分治法的思想。不同的是，归并的思路是将两个有序数列合并成一个有序数列，并将该步骤不断的递归下去。而快排的思路是如果数列中的每一个数都比他的左边的所有数都大，比他右边的所有数都小，那么该数列就一定是升序排列的。
1.1 步骤描述
分解，将数组分成两个子数组
和
。使得
大于等于
的每一个数，同时大于等于
的每一个数
递归,对子数组和
分别执行快排
出口,当子数组大小为1的时候,数组天然有序,此时停止递归,开始回溯
[站外图片上传中...(image-5a283f-1577971358918)]
上图可见,对数列排序.第一次选取70作为中间值,将数列分为
和
.后面的以此类推,知道子数组大小为1或者0为止
1.2 伪代码
quickSort(A,p,r):
if(p < r)
q = partition(A,p,r);
quicksort(A,p,q-1)
quicksort(A,q+1,r)
以上是快排的伪代码,当的时候,即对该数组进行 partition 操作,然后对子数组递归
其中 partition 就是二分数组的方法,返回值为中间值的索引,一下为 partition 的操作描述
partition(A,p,r)
x = A[r] //选取最后一个值为中间值,以他为标的分割数组
i= p-1
for j in (p...r-1)
if A[j] <= x
++i
交换 A[i] 和 A[j]
//经过一系列交换后,导致A[i+1]左边的都小于A[r],右边的都大于A[r]
交换 A[i+1] 和 A[r]
// (i+1) 就是A[r]的索引,作为返回值
return i+1
以上是 partition 操作的伪代码,大致思路就是选取最后一个值为中间值,然后使用两个游标开始遍历数组.
左边的都小于
,i到j的都是大于A[r]的.最终,
1.3 代码实现(Java)
/**
* @author: luzj
* @date:
* @description: 快排,已测试
*/
public class QuickSort {
void quickSort(Integer[] A, int p, int r) {
if (p < r) {
int q = partition(A, p, r);
quickSort(A, p, q - 1);
quickSort(A, q + 1, r);
}
}
private int partition(Integer[] A, int p, int r) {
Integer x = A[r];
int i = p - 1;
for (int j = p; j < r; j++) {
if (A[j] <= x) {
i++;
Integer tmp0 = A[i];
A[i] = A[j];
A[j] = tmp0;
}
}
Integer tmp1 = A[i + 1];
A[i + 1] = A[r];
A[r] = tmp1;
return i + 1;
}
public static void main(String[] args) {
Integer[] A = {13,19,9,5,12,8,7,4,21,2,6,11};
new QuickSort().quickSort(A,0,A.length-1);
for (int i = 0; i < A.length; i++) {
System.out.print(A[i]+" ");
}
}
}
2、 时间复杂度
快排的时间复杂度依赖于输入的分布,平均情况下快排的时间复杂度为.在均衡分割的时候(即
的索引落在数组中间),性能最好.
其实,即使每次数组分割都很不均匀的情况下,比如99:1的比例分割,快排的期望运行时间仍未.算法导论的７.4.2部分给出期望运行时间分析。
最坏的情况下,快排的运行时间为.当输入为一个有序数列的时候,快排坍缩为插入排序.每一次分叉只能分出一个数组出来,因此无法保证二叉树为对数高度.
3、小结
快排同归并排序一样，使用的是分治法．时间复杂度依赖于输入分布，平均期望运行时间为
网友评论