快速排序算法高校试讲PPT

1、试讲：快速排序目 录问题导入思想解读案例讲解123代码实现总结作业性能分析4561、问题导入：为什么会有快速排序？传统排序的缺点传统排序：冒泡排序选择排序插入排序两两比较传统排序的缺点2、核心思想：分治与递归分治思想3、案例讲解：个无序整数快速排序基本步骤递归的4个步骤1、选定Pivot中心轴2、将大于Pivot的数字放在Pivot的右边3、将小于Pivot的数字放在Pivot的左边4、分别对左右子序列重复前三步操作案例讲解3897162606093897162606093897案例讲解389716260609LR38Pivot9716260609LR0938(Pivot)0638(Pivot

2、)1638(Pivot)2609（Pivot）1609（Pivot）0616(Pivot)案例讲解1626060938973897162606093897案例讲解4、代码实现：C语言代码实现代码实现：一趟划分函数int Partition(SqList &L, int left, int right) L.rleft=l.r0; pivotkey=l.r0.key; while(left=pivotkey)-right;L.rleft=L.rright; while(leftright&L.rleft.key=pivotkey)+left; L.rright=L.rleft; while(le

3、ftright) L.rleft=pivotkey; reture left;void QSort(SqList &L,int left,int right)if(leftright) pivotloc=Partition(L,left,right); Qsort(L,left, pivotloc-1);Qsort(L,pivotloc+1,right);代码实现：快速排序函数5、性能总结：时空分析最好：划分后，左子序列和右子序列的长度相同最坏：有序，递归树成为单支树，每次划分只得到一个比上一次少一个对象的子序列，必须经过n-1趟才能把所有对象定位，而且第i趟需要经过n-i次关键码才能得到第i

4、个对象的安放位置性能总结：最好最坏场景分析可以证明，平均计算时间是O(nlog2n)。实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。快速排序是递归的，需要有一个栈存放每层递归调用时参数（新的left和right）。最大递归调用层次数与递归树的深度一致，因此，要求存储开销为O(log2n)。性能总结：时间和空间分析时间效率：O(nlog2n)空间效率：O(log2n)-递归要用到栈空间不稳定性能总结6、总结作业：课程总结与课后作业课程总结解决传统排序两两比较带来的比较负荷问题的导入分而治之与递归基本思想主要讲解了一个位无序数字序列的案例以及语言代码的实现案例与代码时间复杂度，空间复杂度，最好、最坏情形性能总结课后作业1）在快速排序方法中，进行每次划分时，是从当前待排序区间 的（_） 向（_）依次查找出处于逆序的元素并交换之，最后将 中心元素交换到一个确定位置，从而以该位置把当前区间划分为前后 2）假定一组记录的关键字为 (46,79,56,38,40,80)，对其进行快速 排序的一次划分的结果为（_）。3）快速排序在（_）情况下效率