快速排序.pptx

江西江西师师范大学范大学计计算机信息工程学院算机信息工程学院 数数据结构快速排序快速排序作者：杨劲松内容提要内容提要快速排序导入快速排序导入快速排序思想快速排序思想快速排序讲解快速排序讲解快速排序算法分析快速排序算法分析练习题练习题退出退出快速排序导入快速排序导入请同学们使用冒泡排序的方法将下列数据排序：请同学们使用冒泡排序的方法将下列数据排序：（从小到大）（从小到大）21 25 49 16 25 06 目录目录初始状态初始状态第一次交换结束第一次交换结束快速排序导入快速排序导入 冒泡排序过程冒泡排序过程目录目录第二次交换第二次交换第二次交换结束第二次交换结束快速排序导入快速排序导入 冒泡排序过程冒泡排序过程目录目录第三次交换结束第三次交换结束第二次交换结束第二次交换结束第四次交换结束第四次交换结束快速排序导入快速排序导入 冒泡排序过程冒泡排序过程目录目录第六次交换结束第六次交换结束第五次交换结束第五次交换结束请同学们说说冒泡排序是如何工作的快速排序导入快速排序导入目录目录 对所有记录从左到右每相邻的元素进行比较，不符合要求则交换快速排序导入快速排序导入 冒泡排序分析冒泡排序分析冒泡排序的基本做法：冒泡排序的基本做法：思考：在数据为以下排列时，冒泡的排序效果好不好？思考：在数据为以下排列时，冒泡的排序效果好不好？49 25 25 21 16 06 快速排序导入快速排序导入 冒泡排序分析冒泡排序分析初始状态是反序的，则需要进行初始状态是反序的，则需要进行初始状态是反序的，则需要进行初始状态是反序的，则需要进行n-1n-1趟扫描趟扫描趟扫描趟扫描目录目录快速排序导入快速排序导入 冒泡排序分析冒泡排序分析从直观上49移动到最终的位置经过了n-1次比较和交换49 25 25 21 16 0606 16 21 25 25 49能不能不经过能不能不经过n-1次比较和交换呢？次比较和交换呢？不能？这是由于冒泡排序中需要不能？这是由于冒泡排序中需要相邻的元素相邻的元素两两两比较、交换两比较、交换目录目录快速排序思想基本思想：基本思想：1 1）寻找一个中心元素（寻找一个中心元素（通常为第一个数通常为第一个数）2 2）将将小于中心点中心点的元素移动至的元素移动至中心点之前中心点之前，大于中大于中心点心点的元素移动至的元素移动至中心点之后中心点之后。3 3）对上步分成的两个无序数组段重复对上步分成的两个无序数组段重复1 1）、）、2 2）操作直）操作直到段长为到段长为1 1。t tt=t=t目录目录快速排序思想以以21为中心元素为中心元素划分可得：划分可得：以以06、49为中为中心元素心元素划分可得：划分可得：目录目录快速排序讲解选取中心元素的问题选取中心元素的问题选取第一个数为中心元素选取第一个数为中心元素如何划分问题如何划分问题如何重复步骤如何重复步骤将所有数据排序将所有数据排序使用递归使用递归目录目录当已知中心元素的前提下，怎样将其他元素划分好？（即：当已知中心元素的前提下，怎样将其他元素划分好？（即：大于中心点在之后，小于中心点在之前）大于中心点在之后，小于中心点在之前）需要解决的问题需要解决的问题快速排序讲解i012345i=0i=1j=5j=5ji=1j=3i=1j=4i=2j=3i=2j=2算法终止算法终止目录目录快速排序讲解请同学们思考该算法有没有可以改进的地方目录目录快速排序讲解i012345i=0i=1j=5j=5ji=1j=3i=1j=4i=2j=3i=2j=2算法终止算法终止通过动画，可以看出每次中心元素都要交换。通过动画，可以看出每次中心元素都要交换。根据划分的思想最后位置一定是中心元素根据划分的思想最后位置一定是中心元素可以申请一个变量保存中心元素，以避免交换可以申请一个变量保存中心元素，以避免交换目录目录快速排序讲解i=left;j=right;int temp=aleft;do/从右向左找第从右向左找第1个不小于中心元素的位置个不小于中心元素的位置jwhile(aj temp&ij)j-;if(ij)a I =a j;i+;ai=temp;left,right用于限定要排序数列的范围,temp即为中心元素程序填空程序填空当前元素小于中心元当前元素小于中心元素结束循环时，应当素结束循环时，应当在中心元素的左边在中心元素的左边移至左边移至左边目录目录快速排序讲解/从左向右找第从左向右找第1个不大于中心元素的位置个不大于中心元素的位置iwhile(aitemp&ij)i+;if(ij)aj=ai;j-;while(ij);ai=temp;/将中心元素将中心元素将中心元素将中心元素t t填入最终位置填入最终位置填入最终位置填入最终位置程序填空程序填空目录目录快速排序讲解函数头：函数头：函数头：函数头：quicksort(int a,int left,int right)初始化：初始化：初始化：初始化：i=left;j=right;int temp=aleft;划分：划分：划分：划分：do一次划分一次划分 while(ij);中心元素填入：中心元素填入：中心元素填入：中心元素填入：ai=temp;递归地对剩余段作快速排序递归地对剩余段作快速排序递归地对剩余段作快速排序递归地对剩余段作快速排序quicksort(a,left,i-1);quicksort(a,i+1,right);目录目录快速排序完整代码void quicksort(int a,int left,int right)int i,j;if(lefttemp&ij)j-;if(ij)ai=aj;i+;目录目录while(aitemp&ij)i+;if(ij)aj=ai;j-;while(ij);ai=temp;quicksort(a,left,i-1);quicksort(a,i+1,right);快速排序完整代码目录目录算法分析算法分析思考：当数据有序的情况下，快速排序的效率如何？思考：当数据有序的情况下，快速排序的效率如何？快速排序的最坏时间复杂度为快速排序的最坏时间复杂度为O(n2)06 16 21 25 25 49例例快速排序的最好时间复杂度为快速排序的最好时间复杂度为O(nlog2n)快速排序的平均时间复杂度为快速排序的平均时间复杂度为O(nlog2n)快速排序是不稳定的排序方法快速排序是不稳定的排序方法目录目录练习题练习题1）在快速排序方法中，进行每次划分时，是从当前待排序区间在快速排序方法中，进行每次划分时，是从当前待排序区间 的的_ 向向_依次查找出处于逆序的元素并交换之，最后将依次查找出处于逆序的元素并交换之，最后将 中心元素交换到中心元素交换到一个确定位置，从而以该位置把当前区间划分为前后一个确定位置，从而以该位置把当前区间划分为前后 两端两端中间中间2）假定一组记录的关键字为假定一组记录的关键字为 (46,79,56,38,40,80)，对其进行快速，对其进行快速 排序排序的一次划分的结果为的一次划分的结果为_。38 40 46 56 79 843）快速排序在快速排序在_情况下效率最低，情况下效率最低，在在_情况下情况下最易发挥其长处。最易发挥其长处。排序对象已经按其关键字从小到大排好排序对象已经按其关键字从小到大排好每次划分对象定位后，左侧子序列与右每次划分对象定位后，左侧子序列与右 侧子序列长度相同侧子序列长度相同4）快速排序在平均情况下的时间复杂度为快速排序在平均情况下的时间复杂度为_，在最坏，在最坏 情况下情况下的时间复杂度为的时间复杂度为_。O(nlog2n)O(n2)目录目录