10.1 快速排序
10.1.1 算法概述
快速排序的算法跟归并函数的算法差不多，策略都是分而治之的策略
- 分而治之
- 主元(pivot)=>中枢枢纽的意思
伪码描述
voidQuicksort( ElementTypeA[],intN )
{
if( N<2 ) return;
pivot=从A[]中选一个主元;//主元的选择决定了快速排序到底快不快
将S= { A[] \pivot }将除了主元以外的元素分成两个独立子集://怎么分
A1= {a属于S|a<=pivot }和A2= {a属于S|a>=pivot };//一部分由小于等于pivot元素来组成的，另一部分由大于等于pivot元素组成
A[] =Quicksort(A1,N1) U {pivot} UQuicksort(A2,N2);
}
什么是快速排序算法的最好情况？每次正好中分
10.1.2 选主元
- 随机取pivot?rand()函数不便宜=相当花费时间
- 取头、中、尾的中位数
- 例如8、12、3的中位数就是8
- 测试一下pivot()不同的取法和堆运行速度有多大影响？
ElementTypeMedian3( ElementTypeA[],intLeft,intRight )
{
intCenter= ( Left+Right ) /2;
if( A[ Left ] >A[ Center ] )//三步的比较跟交换(保证从左到右的大小顺序)。左边比中间大
Swap( &A[ Left ],&A[ Center ] );
if( A[ Left ] >A[ Right ] )//左边比右边大
Swap( &A[ Left ],&A[ Right ] );
if( A[ Center ] >A[ Right ] )//中间比右边大
Swap( &A[ Center ],&A[ Right ] );
//这样三步交换下来，左边一定是最小的那个
Swap( &A[ Center ],&A[ Right-1 ] );//将pivot藏到右边(为了之后方便，先将Center放到现在需要考虑的子列的最右边)，然后就只需要考虑A[Left + 1]....A[ Right - 2]
returnA[ Right-1];//返回pivot
}
字符串交换(swap)swap操作实现交换两个容器内所有元素的功能。要交换的容器的类型必须匹配： 必须是相同类型的容器，而且所存储的元素类型也必须相同。调用了swap函数后，右操作数原来存储的元素被存放在左操作数中，反之亦然。
10.1.3 子集划分
- i和j不是C语言的指针意义，而是指向存放位置的意思
- 6是主元，被藏到了最右边的位置
- 将主元和i与j进行比较(比较完指针i与j当前的位置后向里靠)，发现大小符号相反的之后i与j当前的数值对调，如下图
-
网络异常，图片无法展示|
-
网络异常，图片无法展示|
-
网络异常，图片无法展示|
-
网络异常，图片无法展示|
-
网络异常，图片无法展示|
以上就是快速排序为什么快的原因：
- 每次他选定主元之后，这个主元在子集划分完成以后，他就被一次性的放在他最终的正确位置上
- 不像插入排序，每次做了元素交换以后，这个元素所待的位置只是临时的，当下一张新的扑克牌插进来的时候，这些牌所有的都要往后错，一张牌的插入就可能要牵扯到多次的移动
上述快速排序需要考虑的问题：
- 如果有元素正好等于pivot怎么办?
- 停下来做交换？当所有元素都相等的时候会做很多很多次完全没有用处的交换。但做了很多次无用的交换后最终我们的主元会被换到中间的位置(好处：每次递归的时候这个原始的序列都被基本上等分成两个等长的序列)复杂度NlogN
- 不理他，继续移动指针？避免了很多次无用的交换，但每次子集划分的时候，主元都是被放在某一个端点的(就复杂度又变成了N²了)
- 结论：还是选择停下来交换划算点
小规模数据的处理
- 快速排序的问题
- 用递归....
- 对小规模的数据(例如N不到100)可能还不如插入排序快
- 解决方案
- 当递归的数据规模充分小，则停止递归，直接调用简单排序(例如插入排序)
- 在程序中定义一个Cutoof的阈值(决定什么时候不递归)
10.1.4 算法实现
voidQuicksort( ElementTypeA[],intLeft,intRight )
{
if( Cutoff<=Right-Left ){
Pivot=Median3( A,Left,Right );//pivot是主元的意思，在这里返回的不仅仅只是一个主元的值
//这里的Left参数是最小值，Right参数是最大值。真正的主元被藏在了Right-1的地方
i=Left; j=Right-1;
for(;;){
while(A[ ++i ] <Pivot ){}
while(A[ --j ] <Pivot ){}
if( i<j)
Swap( &A[i],&A[j] );//i < j则证明中间还有其他元素，这时候就可以调换
//如果i > j则这个子集划分应该结束了
elsebreak;
}
Swap( &A[i],&A[Right-1]);//把藏在right-1这个位置的主元换到A[i]的位置上面去
Quicksort(A,Left,i-1);//递归的左半部分
Quicksort(A,i+1,Right);//递归的右半部分
}
else
Insertion_Sort(A+Left,Right-Left+1);//Right-Left+1：待排序列的总个数；A+Left：开始的地方
}
快速排序的标准接口应该怎么写？
voidQuick_Sort(ElementTypeA[], intN)
{
/* 这里写什么？如下*/
Quicksort( A, 0, N-1 );
}
