试讲：快速排序
目录
1
问题导入
2
思想解读
3
案例讲解
4
代码实现
5
性能分析
6
总结作业
1、问题导入：为什么会有快速排序？传统排序的缺点Fra bibliotek传统排序：
冒泡排序 选择排序 插入排序
两两比较
传统排序的缺点
2、核心思想：分治与递归
分治思想
3、案例讲解：６个无序整数
快速排序基本步骤
递归的4个步骤
1、选定Pivot中心轴 2、将大于Pivot的数字放在Pivot的右边 3、将小于Pivot的数字放在Pivot的左边 4、分别对左右子序列重复前三步操作
3）快速排序在（________________________________）情况下效率最低，在 （_______________________________________________）_情况下最易发挥其长处。
4）快速排序在平均情况下的时间复杂度为（__________） ，在最坏 情况下的时间复杂 度为（_ ____）。
案例讲解
38
97
16
26
06
09
97 38
26 16
06
09
案例讲解
97
38
26
16
09 06
L
R
案例讲解
接下来再分别对左子序列和右子序列进行排序
左子序列
右子序列
38
Pivot
09<38(Pivot) 06<38(Pivot)
16<38(Pivot) 26<38(Pivot)
97>38(Pivot)
真诚感谢各位评委老师！
}
代码实现：快速排序函数
void QSort(SqList &L,int left,int right) {
if(left<right) { pivotloc=Partition(L,left,right); Qsort(L,left, pivotloc-1); Qsort(L,pivotloc+1,right);
while(left<right&&L.r[right].key>=pivotkey)--right; L.r[left]=L.r[right];
while(left<right&&L.r[left].key<=pivotkey)++left; L.r[right]=L.r[left];
} L.r[left]=pivotkey; reture left;
时间效率：O(nlog2n) 空间效率：O(log2n)--递归要用到栈空间 不稳定
6、总结作业：课程总结与课后作业
课程总结
问题的导入 解决传统排序两两比 较带来的比较负荷
基本思想 分而治之与递归
案例与代码
主要讲解了一个６位无 序数字序列的案例以及 Ｃ语言代码的实现
性能总结
时间复杂度，空间复杂 度，最好、最坏情形
课后作业
1）在快速排序方法中，进行每次划分时，是从当前待排序区间 的（_____） 向（_____） 依次查找出处于逆序的元素并交换之，最后将 中心元素交换到一个确定位置，从而以该位 置把当前区间划分为前后
2）假定一组记录的关键字为 (46,79,56,38,40,80)，对其进行快速 排序的一次划分的结果 为（_________________）。
可以证明，平均计算时间是O(nlog2n)。 实验结果表明：就平均计算时间而言，快速排序是我 们所讨论的所有内排序方法中最好的一个。 快速排序是递归的，需要有一个栈存放每层递归调用时参 数（新的left和right）。 最大递归调用层次数与递归树的深度一致，因此，要求存储 开销为O(log2n)。
性能总结
97
26 16
09 06
L
R
案例讲解
左子序列
16
26
09 06
L
R
案例讲解
09
左子序列长度为1，
不需要继续排序
需要对右子序列进行排序
06<09（Pivot）
16>09（Pivot）
26>09（Pivot）
16
26
06
L
R
案例讲解
16
16 L
26>16(Pivot)
26 R
案例讲解
97
97
38
} }
5、性能总结：时空分析
性能总结：最好最坏场景分析
最好：划分后，左子序列和右子序列的长度相同
最坏：有序，递归树成为单支树，每次划分只得到一个比上一次少 一个对象的子序列，必须经过n-1趟才能把所有对象定位，而且第i趟 需要经过n-i次关键码才能得到第i个对象的安放位置
性能总结：时间和空间分析
16 09 06
26 16
38 26
06
09
4、代码实现：C语言代码实现
代码实现：一趟划分函数
int Partition(SqList &L, int left, int right) {
L.r[left]=l.r[0]; pivotkey=l.r[0].key;
while(left<right) {