4.6.2 快速排序一,基本思想任取待排序序列中的某个元素作为 基准 （一般取第一个元素），将待排序元素 分为左右两个子表,左子表中元素的关键字值均小于或等于基准元素的关键字值，
右子表中元素的关键字值均大于或等于基准元素的关键字值，然后分别对两个子表继续进行划分，直至每一个子表 只有一个元素或为空 为止。最后得到的便是有序序列。
怎样具体实现？
概括地说：
一次划分就是从表的两端 交替方向 地向中间进行扫描,将小的放到左边,大的放到右边,作为基准的元素放到中间 。
快速排序一次划分过程
38 20 46 38 74 91 12
思考：怎样为 38找位置，正确地实现表的一次划分？
快速排序一次划分过程
1,i指向待划分区域最左端,j指向待划分区域最右端 ;
2,保存基准元素的值,r[0]=r[i] ;
3,从右向左扫描 (首先开始此方向的扫描 )
j从 右向左 移动,直到 r[j].key<r[0].key或 i==j;
4,若 r[j].key<r[0].key,则 r[i]=r[j],i=i+1,改变扫描方向；
5,从左向右扫描：
i从左向右 移动,直到 r[i].key>r[0].key或 i==j;
6,若 r[i].key>r[0].key,则 r[j]=r[i],j=j-1,改变扫描方向 ;
7,重复 3~6,直到 i,j位置重合 （ 即 i==j）,此位置即最终的划分位置；
8,将基准元素放入 最终的划分位置,r[i]=r[0]或 r[j]=r[0]
为了减少数据的移动,将作为基准的元素暂存到 r[0]中，
最后再放入最终位置
2,r[0]=r[i]
一次划分过程演示
i
38 20 46 38 74 91 12
j
0 1 2 3 4 5 6 7
1,i指向待划分区域最左端（ low）；
j指向待划分区域最右端（ high）；
low high
一次划分过程演示
i
38 20 46 38 74 91 12
j
0 1 2 3 4 5 6 7
3,j从右向左移动直到
r[j].key<r[0].key或 i==j;
38
一次划分过程演示
i
38 20 46 38 74 91 12
j
0 1 2 3 4 5 6 7
4,若 r[j].key<r[0].key,
则 r[i]=a[j],i=i+1,改变扫描方向 ;
38
一次划分过程演示
i
12 20 46 38 74 91 12
j
0 1 2 3 4 5 6 7
5,i从左向右移动直到
r[i].key>r[0].key或 i==j;
38
一次划分过程演示
i
12 20 46 38 74 91 12
j
0 1 2 3 4 5 6 7
6,若 r[i].key>r[0].key，
则 r[j]=a[i],j=j-1，改变扫描方向 ;
38 46
一次划分过程演示
i
12 20 46 38 74 91 46
0 1 2 3 4 5 6 7
3838
令,mid=j，形成两个子表,low~mid-1和 mid+1~high
一次划分过程结束
j
low highmid
3,j从右向左移动直到
r[j].key<r[0].key或 i==j;
i,j位置重合,扫描结束将基准元素放入最终确定的划分位置 (i,j重合处 )
实现一次划分的算法：
int Partition(list r[],int i,int j)
{ r[0]=r[i]; /* 暂存基准元素到 r[0]中 */
while(i<j) /*从表的两端交替地向中间扫描 */
{while(i<j&&r[j].key>=r[0].key)
j--;
if(i<j)
{ r[i]=r[j]; i++; }
while(i<j&&r[i].key<=r[0].key)
i++;
if (i<j)
{ r[j]=r[i]; j--; }
}
r[i]=r[0]; /*将基准元素放到其最终位置 */
return i; /* 返回基准元素所在的位置 */
}
二,算法实现
递归算法分析
递归退出的条件：
数据表为空或数据表中只有一个元素。
即,low≥high。
大规模问题与小规模问题的关系：
对一个 low~high区间的表的排序变成对
low~mid-1和 mid+1~high两个子表的排序。
快速排序的递归过程
38 20 46 38 74 91 12初始状态
[12 20 ] 38 [38 74 91 46] 第 1次划分分别快速排序 12 [20] 38 [74 91 46]
结束 [46] 74 [91]
结束
12 20 38 38 46 74 91 排序结果
递归算法
void QSort(list r[],int low,int high)
{/*对 r[low]到 r[high]范围内的元素进行快速排序 */
int mid;
{ if (low<high)
{ mid=Partition(r,low,high);
QSort(r,low,mid-1);
QSort(r,mid+1,high);}
}
}
下面的快速排序算法实现将一个长度为 n的线性表 r上的所有元素按关键字升序排列。
void Quick_Sort(list r[],int n)
{
QSort(r,1,n);
}
算法分析
4 3 3? 稳定性,不稳定的时间复杂度,
Ｏ (n2)
最快的情况,数据分布均匀
最慢的情况,正序或逆序
O（ nlog2n）
时间复杂度：
i j
4
4先暂存在
r[0]中
4 [ ]
3 33
i j
结果,3 3 4
快速排序的递归树
38
12 38
91
20 74
46
1
2
3
4深度越小效率越高
思考题
“三者取中,的规则
,三者取中,规则，即在当前区间里，将该区间首、尾和中间位置上的关键字比较，取三者之中值所对应的记录作为基准，在划分开始前将该基准记录和该区间的第 1 个记录进行交换，此后的划分过程与上面所给的 Partition算法完全相同。
开动脑筋基准元素如何选取能提高快速排序的时间性能？
课后练习题
1．假如待排序的关键字序列为 {1,2,3,4,5，
6,7}，请问初始状态为什么时，快速排序效率最高？
2．给定一组关键字序列 {19,26,92,87,11，
43,87,21}，用快速排序方法进行升序排列，
写出每趟排序后关键字的排列情况。
右子表中元素的关键字值均大于或等于基准元素的关键字值，然后分别对两个子表继续进行划分，直至每一个子表 只有一个元素或为空 为止。最后得到的便是有序序列。
怎样具体实现？
概括地说：
一次划分就是从表的两端 交替方向 地向中间进行扫描,将小的放到左边,大的放到右边,作为基准的元素放到中间 。
快速排序一次划分过程
38 20 46 38 74 91 12
思考：怎样为 38找位置，正确地实现表的一次划分？
快速排序一次划分过程
1,i指向待划分区域最左端,j指向待划分区域最右端 ;
2,保存基准元素的值,r[0]=r[i] ;
3,从右向左扫描 (首先开始此方向的扫描 )
j从 右向左 移动,直到 r[j].key<r[0].key或 i==j;
4,若 r[j].key<r[0].key,则 r[i]=r[j],i=i+1,改变扫描方向；
5,从左向右扫描：
i从左向右 移动,直到 r[i].key>r[0].key或 i==j;
6,若 r[i].key>r[0].key,则 r[j]=r[i],j=j-1,改变扫描方向 ;
7,重复 3~6,直到 i,j位置重合 （ 即 i==j）,此位置即最终的划分位置；
8,将基准元素放入 最终的划分位置,r[i]=r[0]或 r[j]=r[0]
为了减少数据的移动,将作为基准的元素暂存到 r[0]中，
最后再放入最终位置
2,r[0]=r[i]
一次划分过程演示
i
38 20 46 38 74 91 12
j
0 1 2 3 4 5 6 7
1,i指向待划分区域最左端（ low）；
j指向待划分区域最右端（ high）；
low high
一次划分过程演示
i
38 20 46 38 74 91 12
j
0 1 2 3 4 5 6 7
3,j从右向左移动直到
r[j].key<r[0].key或 i==j;
38
一次划分过程演示
i
38 20 46 38 74 91 12
j
0 1 2 3 4 5 6 7
4,若 r[j].key<r[0].key,
则 r[i]=a[j],i=i+1,改变扫描方向 ;
38
一次划分过程演示
i
12 20 46 38 74 91 12
j
0 1 2 3 4 5 6 7
5,i从左向右移动直到
r[i].key>r[0].key或 i==j;
38
一次划分过程演示
i
12 20 46 38 74 91 12
j
0 1 2 3 4 5 6 7
6,若 r[i].key>r[0].key，
则 r[j]=a[i],j=j-1，改变扫描方向 ;
38 46
一次划分过程演示
i
12 20 46 38 74 91 46
0 1 2 3 4 5 6 7
3838
令,mid=j，形成两个子表,low~mid-1和 mid+1~high
一次划分过程结束
j
low highmid
3,j从右向左移动直到
r[j].key<r[0].key或 i==j;
i,j位置重合,扫描结束将基准元素放入最终确定的划分位置 (i,j重合处 )
实现一次划分的算法：
int Partition(list r[],int i,int j)
{ r[0]=r[i]; /* 暂存基准元素到 r[0]中 */
while(i<j) /*从表的两端交替地向中间扫描 */
{while(i<j&&r[j].key>=r[0].key)
j--;
if(i<j)
{ r[i]=r[j]; i++; }
while(i<j&&r[i].key<=r[0].key)
i++;
if (i<j)
{ r[j]=r[i]; j--; }
}
r[i]=r[0]; /*将基准元素放到其最终位置 */
return i; /* 返回基准元素所在的位置 */
}
二,算法实现
递归算法分析
递归退出的条件：
数据表为空或数据表中只有一个元素。
即,low≥high。
大规模问题与小规模问题的关系：
对一个 low~high区间的表的排序变成对
low~mid-1和 mid+1~high两个子表的排序。
快速排序的递归过程
38 20 46 38 74 91 12初始状态
[12 20 ] 38 [38 74 91 46] 第 1次划分分别快速排序 12 [20] 38 [74 91 46]
结束 [46] 74 [91]
结束
12 20 38 38 46 74 91 排序结果
递归算法
void QSort(list r[],int low,int high)
{/*对 r[low]到 r[high]范围内的元素进行快速排序 */
int mid;
{ if (low<high)
{ mid=Partition(r,low,high);
QSort(r,low,mid-1);
QSort(r,mid+1,high);}
}
}
下面的快速排序算法实现将一个长度为 n的线性表 r上的所有元素按关键字升序排列。
void Quick_Sort(list r[],int n)
{
QSort(r,1,n);
}
算法分析
4 3 3? 稳定性,不稳定的时间复杂度,
Ｏ (n2)
最快的情况,数据分布均匀
最慢的情况,正序或逆序
O（ nlog2n）
时间复杂度：
i j
4
4先暂存在
r[0]中
4 [ ]
3 33
i j
结果,3 3 4
快速排序的递归树
38
12 38
91
20 74
46
1
2
3
4深度越小效率越高
思考题
“三者取中,的规则
,三者取中,规则，即在当前区间里，将该区间首、尾和中间位置上的关键字比较，取三者之中值所对应的记录作为基准，在划分开始前将该基准记录和该区间的第 1 个记录进行交换，此后的划分过程与上面所给的 Partition算法完全相同。
开动脑筋基准元素如何选取能提高快速排序的时间性能？
课后练习题
1．假如待排序的关键字序列为 {1,2,3,4,5，
6,7}，请问初始状态为什么时，快速排序效率最高？
2．给定一组关键字序列 {19,26,92,87,11，
43,87,21}，用快速排序方法进行升序排列，
写出每趟排序后关键字的排列情况。
