算法导论读书笔记(4)

快速排序

快速排序是一种原地排序算法，对包含 n 个数的输入数组，最坏情况运行时间为 Θ ( n2 )。虽然这个最坏情况运行时间比较差，但快速排序通常是用于排序的最佳的实用选择。这是因为其平均性能相当好：期望的运行时间为 Θ ( n lg n )，且 Θ ( n lg_n_ )记号中隐含的常数因子很小。

像合并排序一样，快速排序也是基于分治模式的。下面是对一个子数组 A [ p .. r ]排序的分治过程的三个步骤：

分解：

数组 A [ p .. r ]被划分成两个（可能为空）子数组 A [ p .. q - 1 ]和 A [ q + 1 .. r ]，使得 A [ p .. q - 1 ]中的每一个元素都小于等于 A [ q ]，而且，小于等于 A [ q + 1 .. r ]中的元素。下标 q 也在这个划分过程中计算。

解决：

通过递归调用快速排序，对子数组 A [ p .. q - 1 ]和 A [ q + 1 .. r ]排序。

合并：

因为两个子数组是就地排序的，将它们合并不需要操作，整个数组 A [ p .. r ]已排序。

快速排序的伪代码:

QUICK-SORT(A, p, r)
1 if p < r
2     q = PARTITION(A, p, r)
3     QUICK-SORT(A, p, q - 1)
4     QUICK-SORT(A, q + 1, r)

Partition部分

PARTITION(A, p, r)
1 x = A[r]
2 i = p - 1
3 for j = p to r - 1
4     if A[j] <= x
5         i = i + 1
6         exchange A[i] with A[j]
7 exchange A[i + 1] with A[r]
8 return i + 1

PARTITION 总是选择一个 x = A [ r ]作为 主元 （pivot element），并围绕它来划分子数组。在第3行到第6行中循环的每一轮迭代开始时，对于任何数组下标 k ，有

1. 如果 p <= k <= i ，则 A [ k ] <= x
2. 如果 i + 1 <= k <= j - 1，则 A [ k ] > x
3. 如果 k = r ，则 A [ k ] = x

下图总结了这一结构。过程 PARTITION 作用于子数组 A [ p .. r ]后得到四个区域。 A [ p .. i ]中的各个值都小于等于 x ， A [i + 1 .. j - 1 ]中的值都大于 x ， A [ r ] = x 。 A [ j .. r - 1 ]中的值可以是任何值。

QuickSort 实现:

//QuickSort.h

1.cpp

#ifndef _QUICK_H_
#define _QUICK_H_

class Sort{
public:
	int Partition(int *,int,int);
	void QuickSort(int *,int,int);
private:
	

protected:
};

//QuickSort.cpp

#include <iostream>
#include "QuickSort.h"

int Sort::Partition(int *A, int p, int r){
	using namespace std;
	int x = A[r];
	int i = p - 1;
	for (int j = p; j <= r - 1; j++){
		if (A[j] <= x){
			i = i + 1;
			swap(A[i], A[j]);
		}
	}
	swap(A[i + 1], A[r]);
	return i + 1;
}

void Sort::QuickSort(int *A,int p,int r)
{
	using namespace std;
	if (p < r){
		int q = Partition(A, p, r);
		QuickSort(A, p, q - 1);
		QuickSort(A, q + 1, r);
	}
}

void main(){
	using namespace std;
	int A[10] = { 0, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
	Sort * s = new Sort;
	s->QuickSort(A, 0, 9);
	for (int i = 0; i < 10; i++)
		cout << A[i] << " ";
	cout << endl;
	system("pause");
}

运行结果: <p align="center"> </p>

Quick Sort 性能研究

如果划分是左右对称的，那么从渐进意义上来说，就和merge-sort算法的复杂度一样，如果划分不是对称的，那么就是和插入排序的速度一样慢。

最坏情况下:

快速排序的最坏情况划分发生在划分过程产生的两个区域分别包含 n - 1个元素和1个0元素的时候。假设算法的每一次递归调用都出现了这种不对称划分。划分的时间代价为 Θ ( n )。对一个大小为0的数组进行递归调用后，返回 T ( 0 ) = Θ ( 1 )，故算法的运行时间为 T ( n ) = T ( n - 1 ) + Θ ( n )。最终得到解为 T ( n ) = Θ ( n2 )。

最好情况下：

在 PARTITION 过程可能的最平衡划分中，一个子问题的大小为 FLOOR（n / 2） ，另一个子问题的大小为 CEIL(n / 2) - 1。这种情况下，其运行时间的递归式为 T ( n ) <= 2 T ( n / 2 ) + Θ ( n )。该递归式的解为 T ( n ) = O ( n lg n )。

RANDOMIZED-PARTITION （随机划分） 随机选取主原

RANDOMIZED-PARTITION(A, p, r)
1 i = RANDOM(p, r)
2 exchange A[r] with A[i]
3 return PARTITION(A, p, r)

比较排序

之前已经介绍了几种能在 O ( n lg n )时间内排序 n 个数的算法。比如归并排序，堆排序和快速排序。这些算法都有一个相同的性质：排序结果中，各元素的次序基于输入元素间的比较。这类排序算法统称为 比较排序 。

在一个比较排序算法中，仅用比较来确定输入序列< a1 ， a2 ， …， an >的元素间次序。就是说，给定两个元素 ai 和 aj ，测试 ai < aj ， ai <= aj ， ai = aj ， ai >= aj 或 ai > aj 中的哪一个成立，以确定 ai 和 aj 之间的相对次序。

比较排序可以被抽象地视为 决策树 。一棵决策树是一棵满二叉树，表示某排序算法作用于给定输入所做的所有比较，而控制结构，数据移动等都被忽略了。下图是插入排序作用于含三个元素的输入序列上的决策树。

个人认为这个决策树挺无聊的。