算法导论_第七章_快速排序
快速排序的描述：
与归并排序一样，快速排序也使用了分治思想。
下面是对一个数组进行快速排序的三部分治过程：
1.分解：数组A[p,r]被划分为两个子数组A[p,q-1]和A[q+1,r]，使得A[p,q-1]中的每一个元素都小于等于A[q]，而A[q]也小于等于A[q+1,r];
2.解决：通过递归调用快速排序，对子数组进行排序。
3.合并：因为其是进行原址操作，所以其不需要合并
下面给出详细代码，介绍其具体运算过程：
/*************************************************************************
> File Name: quicksort.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月28日 星期二 21时11分41秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int partition(int A[],int p,int r);
void quicksort(int A[],int p,int r);
void swap(int *x,int *y){int t; t=*x; *x=*y; *y=t; }
int main(int argc,char *argv[])
{
int A[100]={5,4,3,2,1};
int n=5;
quicksort(A,0,n-1);
for(int i=0;i<n;i++)
printf("%3d",A[i]);
return 0;
}
void quicksort(int A[],int p,int r)
{
if(p>=r) return;
int q=partition(A,p,r);
//根据主元的位置进行递归求解
quicksort(A,p,q-1);
quicksort(A,q+1,r);
}
int partition(int A[],int p,int r)
{
int x=A[r];//以这个元素为主元，即拿这个元素与其他元素比较
int i=p-1;//i为最左边元素减一
//其中，从p到i为小于等于x的子数组1，而从i+1到j为大于等于x的子数组2，
//从j+1到r-1表示的是还未进行分配的子数组
//而元素r为主元
for(int j=p;j<=r-1;j++)
{
if(A[j]<=x)
{
i++;//子数组1加入一个元素
//加一后的i大于等于x
swap(A+i,A+j);
//交换后其恢复原来“秩序”
}
}
swap(A+i+1,A+r);//把主元放到合适的位置。
return i+1;//返回主元的位置
}
其实其核心就是 分割数组。
其把数组分为四个部分：
1.从p到i为小于等于x的子数组1，而
2.从i+1到j为大于等于x的子数组2，
3.从j+1到r-1表示的是还未进行分配的子数组
4.元素r为主元
最后把r放到数组1和数组2的中间位置
partition函数的时间复杂度为Θ(n)
快速排序的性能：
快速排序的运行时间依赖与划分是否平衡，如果划分是不平衡的，那么其性能就接近插
入排序了
最坏情况划分：
当划分产生两个子问题分别包含了n-1个元素和0个元素时，快速排序的最坏情况为
Θ(n^2)
其表达式为T(n)=T(n-1)+Θ(n)
利用主方法，其时间复杂度为Θ(n^2)
最好情况的划分
在最可能平衡的划分中，就是两个子数组长度相等或差1,这时，其T(n)=2*T(n/2)+Θ(n)
利用主方法 其时间复杂度为Θ(n*lg(n))
平衡的划分：
快速排序的平均运行时间更接近与其最好情况下的性能，而不是最坏情况下的性能。
假设算法为9：1划分，
利用一个递归树，表示，
其T(n)=T(9*n/10)+T(n/10)+Θ(n)
其每层的代价和为cn
一共有log(10/9) n=Θ(lg(n))层
所以其时间复杂度为O(n*lg(n))
99:1仍然一样，其时间复杂度为O(n*lg(n))，，因为其层数为log(100/99) n=Θ(lg(n))层
其实，任何一种常数比例的划分都会产生深度为Θ(lg(n))层的递归树，其中每层代价都为
O(n)，所以只要划分为常数比例的，其算法的运行时间为O(n*lg(n))
对于平均情况的直接观察：
当好和差的划分交替出现时，快速排序的时间复杂度与全是好的划分一样，仍然是
O(n*lg(n))。区别只是O的符号中隐含的常数因子要略大一些。
快速排序的随机化版本：
在这里不用对输入的数组进行随机排序，只需随机选取其主元就可以满足随机化算法
这样划分就可以满足随机条件
下面上代码：
/*************************************************************************
> File Name: quicksort.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月28日 星期二 21时11分41秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int partition_random(int A[],int p,int r);
void quicksort_random(int A[],int p,int r);
void swap(int *x,int *y){int t; t=*x; *x=*y; *y=t; }
int main(int argc,char *argv[])
{
srand(time(0));
int A[100]={5,4,3,2,1};
int n=5;
quicksort_random(A,0,n-1);
for(int i=0;i<n;i++)
printf("%3d",A[i]);
return 0;
}
void quicksort_random(int A[],int p,int r)
{
if(p>=r) return;
int q=partition_random(A,p,r);
//根据主元的位置进行递归求解
quicksort_random(A,p,q-1);
quicksort_random(A,q+1,r);
}
int partition_random(int A[],int p,int r)
{
int y=p+rand()%(r+1-p);//随机交换A[r]
swap(A+y,A+r);
int x=A[r];//以这个元素为主元，即拿这个元素与其他元素比较
int i=p-1;//i为最左边元素减一
//其中，从p到i为小于等于x的子数组1，而从i+1到j为大于等于x的子数组2，
//从j+1到r-1表示的是还未进行分配的子数组
//而元素r为主元
for(int j=p;j<=r-1;j++)
{
if(A[j]<=x)
{
i++;//子数组1加入一个元素
//加一后的i大于等于x
swap(A+i,A+j);
//交换后其恢复原来“秩序”
}
}
swap(A+i+1,A+r);//把主元放到合适的位置。
return i+1;//返回主元的位置
}
快速排序分析：
最坏情况分析
T(n)=max(T(q)+T(n-q-1))+Θ(n)
不妨猜测T(n)<=c*n^2
代入得 T(n)<=max(c*q^2+c(n-q-1)^2)+Θ(n)
二次函数的上界为n^2-c(2*n-1)
又有：n^2-c(2*n-1)+Θ(n)<=c*n^2
可以选择一个c使得c(2*n-1)>Θ(n)
Θ(n)-c(2*n-1)<0
期望运行时间：
我们首先对数组A的各个元素重新进行命名，z1,z2,z3,,,,zn
代表第i大的元素。
另外还定义z[i][j]为{zi,zi+1,,,,,zj}的集合。
这里利用了指示器随机变量X[i][j]代表了{zi和zj进行比较}
然后对于一个集合z[i][j]有 2/(j-i+1)的概率比较
(这里只有在主元选取zi和zj时能够进行比较，因为如果选取
中间元素的话，就把两个分割就无法进行比较)
然后根据求和
i: 1=>n-1
j: i+1=>n
sum+= 2/(j-i+1)
最后后得到E[x]=O(n*lg(n))
所以在随机算法和输入互异的情况下，快速算法的
期望运行时间为O(n*lg(n))