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