算法导论公开课笔记（二）快速排序和随机化算法
2017-09-29 本文已影响218人
EboyWang
快速排序
与归并排序一样，快速排序也使用了分治的思想解决排序问题。
对一个典型的子数组A[p..r]进行快速排序的三步分治过程：
- 分解：数组A[p..r]被划分为两个（可能为空）子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每一个元素都小于等于A[q],而A[q]也小于等于A[q+1..r]中的每个元素。其中计算下标q也算划分过程的一部分。
- 解决： 通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]进行排序。
- 合并：因为子数组都是原址排序，所以不需要额外的合并操作：数组A[p..r]已经有序。
伪代码实现快速排序：
QUICKSORT(A,p,r)
if p < r
q=PARTITION(A,p,r)
QUICKSORT(A,p,q-1)
QUICKSORT(A,q+1,r)
Java实现版：
/**
*
* @param src 待排序的数组
*/
public static void quickSort(int[] src,int left ,int right){
if(left<right){
int mid=partition(src, left, right);
quickSort(src, left, mid-1);
quickSort(src, mid+1, right);
}
}
数组的划分
算法的关键部分就是PARTITION过程，它实现了对子数组A[p..r]的原址重排。
PARTITION(A,p,r)
x=A[r]
i=p-1
for j=p to r-1
if A[j]<=x
i=i+1
exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i+1
快速排序的划分和过程
快速排序分解过程
Java实现版：
/**
* 划分操作
*
* @param src
* 待排序的数组
* @param left
* 左边界
* @param right
* 右边界
*/
public static int partition(int[] src, int left, int right) {
int key = src[left];//挖坑
int i = left;
int j = right;
while (i < j) {
while (i < j && src[j] > key) {
j--;
}
if (i < j) {
src[i++] = src[j];// 挖坑填数
}
while (i < j && src[i] < key) {
i++;
}
if (i < j) {
src[j--] = src[i];// 挖坑填数
}
}
src[i] = key;//填空
// 这种情况下第一趟结束 i的坐标都比他小i的右边都比他大
return i;
}
随机化版本的快速排序
在理解了快速排序的划分过程之后，随机化快速排序的过程就很好理解了。
首先随机化快排是为了解决出现最坏情况时 Ω（n^2）的运行时间的问题，将快速排序变成一个“稳定”的算法，随机化后，快排的期望运行时间为O(n* lg n)。
随机化快排其实做的很简单，就是在划分的时候，不是确定性的选择主元（provit），而是随机的选择主元，这要就保证了只有很小的几率下每次都出现最坏的划分情况。
随机化快排的划分过程：
/**
* 随机划分操作
*
* @param src
* 待排序的数组
* @param left
* 左边界
* @param right
* 右边界
*/
public static int randomizedPartition(int[] src, int left, int right) {
/*随机选取主元元素*/
Random random = new Random();
int random_index = random.nextInt(right-left+1)+left;
System.out.println("random_index="+random_index);
/**
* 交换
*/
int temp = src[random_index];
src[random_index] = src[left];
src[left]=temp;
int key = src[left];//挖坑
int i = left;
int j = right;
while (i < j) {
while (i < j && src[j] > key) {
j--;
}
if (i < j) {
src[i++] = src[j];// 挖坑填数
}
while (i < j && src[i] < key) {
i++;
}
if (i < j) {
src[j--] = src[i];// 挖坑填数
}
}
src[i] = key;//填空
// 这种情况下一趟结束 i的坐标都比他小i的右边都比他大
return i;
}
以上，谢谢阅读，希望你有所收获！
算法导论公开课笔记（一）算法分析与设计
算法导论公开课笔记（二）快速排序和随机化算法
算法导论公开课笔记（三）线性时间排序
算法导论公开课笔记（四）顺序统计、中值
动态规划算法
