快速排序 课件

快速排序2021/5/91内容提要快速排序导入快速排序思想快速排序讲解快速排序算法分析练习题退出2021/5/92快速排序导入请同学们使用冒泡排序的方法将下列数据排序：（从小到大）212549162506

目录2021/5/93初始状态第一次交换结束快速排序导入–冒泡排序过程目录2021/5/94第二次交换第二次交换结束快速排序导入–冒泡排序过程目录2021/5/95第三次交换结束第二次交换结束第四次交换结束快速排序导入–冒泡排序过程目录2021/5/96第六次交换结束第五次交换结束请同学们说说冒泡排序是如何工作的快速排序导入目录2021/5/97对所有记录从左到右每相邻的元素进行比较，不符合要求则交换快速排序导入–冒泡排序分析冒泡排序的基本做法：思考：在数据为以下排列时，冒泡的排序效果好不好？492525211606

2021/5/98快速排序导入–冒泡排序分析初始状态是反序的，则需要进行n-1趟扫描目录2021/5/99快速排序导入–冒泡排序分析从直观上49移动到最终的位置经过了n-1次比较和交换492525211606061621252549能不能不经过n-1次比较和交换呢？不能？这是由于冒泡排序中需要相邻的元素两两比较、交换目录2021/5/910快速排序思想基本思想：1）寻找一个中心元素（通常为第一个数）2）将小于中心点的元素移动至中心点之前，大于中心点的元素移动至中心点之后。3）对上步分成的两个无序数组段重复1）、2）操作直到段长为1。t<t>=t目录2021/5/911快速排序思想以21为中心元素划分可得：以06、49为中心元素划分可得：目录2021/5/912快速排序讲解选取中心元素的问题选取第一个数为中心元素如何划分问题如何重复步骤①②将所有数据排序使用递归目录2021/5/913当已知中心元素的前提下，怎样将其他元素划分好？（即：大于中心点在之后，小于中心点在之前）需要解决的问题快速排序讲解i[0][1][2][3][4][5]i=0i=1j=5j=5ji=1j=3i=1j=4i=2j=3i=2j=2算法终止目录2021/5/914快速排序讲解请同学们思考该算法有没有可以改进的地方目录2021/5/915快速排序讲解i[0][1][2][3][4][5]i=0i=1j=5j=5ji=1j=3i=1j=4i=2j=3i=2j=2算法终止通过动画，可以看出每次中心元素都要交换。根据划分的思想最后位置一定是中心元素可以申请一个变量保存中心元素，以避免交换目录2021/5/916快速排序讲解i=left;j=right;inttemp=a[left];do{ //从右向左找第1个不小于中心元素的位置j while(a[j]>temp&&i<j)j--; if(i<j) { a[I]=a[j]; i++; }

a[i]=temp;left,right用于限定要排序数列的范围,temp即为中心元素程序填空当前元素小于中心元素结束循环时，应当在中心元素的左边移至左边目录2021/5/917快速排序讲解

//从左向右找第1个不大于中心元素的位置i while(a[i]<temp&&i<j)

i++; if(i<j) { a[j]=a[i]; j--; }}while(i<j);a[i]=temp;//将中心元素t填入最终位置程序填空目录2021/5/918快速排序讲解函数头：quicksort(inta[],intleft,intright)初始化：i=left;j=right;inttemp=a[left];划分：do{一次划分}while(i<j);中心元素填入：a[i]=temp;递归地对剩余段作快速排序quicksort(a,left,i-1);quicksort(a,i+1,right);目录2021/5/919快速排序完整代码voidquicksort(inta[],intleft,intright){ inti,j; if(left<right) { i=left;j=right; inttemp=a[left]; do { while(a[j]>temp&&i<j)

j--; if(i<j) { a[i]=a[j]; i++; }目录2021/5/920 while(a[i]<temp&&i<j) i++; if(i<j) { a[j]=a[i]; j--; } }while(i<j);

a[i]=temp; quicksort(a,left,i-1); quicksort(a,i+1,right); }}快速排序完整代码目录2021/5/921算法分析思考：当数据有序的情况下，快速排序的效率如何？快速排序的最坏时间复杂度为O(n2)061621252549例快速排序的最好时间复杂度为O(nlog2n)快速排序的平均时间复杂度为O(nlog2n)快速排序是不稳定的排序方法目录2021/5/922练习题1）在快速排序方法中，进行每次划分时，是从当前待排序区间的_____向_____依次查找出处于逆序的元素并交换之，最后将中心元素交换到一个确定位置，从而以该位置把当前区间划分为前后两端中间2）假定一组记录的关键字为(46,79,56,38,40,80)，对其进行快速排序的一次划分的结果为_________________。[3840]46[567984]3）快速排序在________________________________情况下效率最低，在_____________________________________________