数据结构-从概念到C++实现（第4版）课件 7-3交换排序

7-3交换排序v第七章排序技术学什么？起泡（冒泡）排序快速排序提出关键问题给出解决方法写出算法描述得到完整算法运行实例7-3-1起泡排序v第七章排序技术基本思想无序区r1r2ri-1…有序区rirnri+1…起泡排序的基本思想：两两比较相邻记录，如果反序则交换，直到没有反序的记录为止。反序则交换类似水中的气泡，体积大的浮到上面，起泡排序（冒泡排序）因而得名运行实例2420101812待排序序列第一趟排序结果第二趟排序结果第三趟排序结果第四趟排序结果1210201824241012182024101218202410121820第二趟排序有必要吗？88888第五趟排序结果24101218208第四、五趟排序有必要吗？关键问题2420101812待排序序列第一趟排序结果1210182024如果有多个记录位于最终位置，如何不参加下一趟排序？if(data[j]>data[j+1]){temp=r[j];r[j]=r[j+1];r[j+1]=temp;exchange=j;}设置变量exchange记载交换的位置，一趟排序后exchange记载的就是最后交换的位置，从exchange之后的记录不参加下一趟排序。解决方法：算法描述：交换交换2420101812待排序序列第一趟排序结果2024下一趟排序的范围是多少？bound=exchange;exchange=0;for(j=0;j<bound;j++)if(data[j]>data[j+1]){temp=r[j];r[j]=r[j+1];r[j+1]=temp;exchange=j;}设置变量bound表示一趟起泡排序的范围[1,bound]，并且bound与上一趟起泡排序的最后交换的位置exchange之间的关系是bound=exchange。解决方法：算法描述：交换交换121018关键问题某趟排序结果下一趟排序结果2024如何判别起泡排序的结束？while(exchange!=0){

执行一趟起泡排序；}一趟排序没有交换，则表明整个序列已经有序。解决方法：算法描述：1210182024121018关键问题算法实现voidSort::BubbleSort(){ intj,exchange,bound,temp;exchange=length-1;while(exchange!=0){bound=exchange;exchange=0；

for(j=0;j<bound;j++)if(data[j]>data[j+1]){temp=data[j];data[j]=data[j+1];data[j+1]=temp;

exchange=j；//记载每一次记录交换的位置

}}}比较语句？执行次数？移动语句？执行次数？取决于待排序序列的初始状态时间性能性能分析比较次数：n-1

移动次数：0

12345最好情况：正序O(n)最坏情况：逆序O(n2)比较次数：

移动次数：平均情况：随机排列O(n2)51432

空间性能：O(1)

稳定性：稳定if(data[j]>data[j+1]){

temp=r[j];r[j]=r[j+1];r[j+1]=temp

exchange=j；}7-3-2快速排序v第七章排序技术改进的着眼点5143245352551记录的比较在相邻单元中进行每次交换只能右移一个单元总的比较次数和移动次数较多较大记录从前面直接移到后面，较小记录从后面直接移到前面？基本思想快速排序的基本思想：选一个轴值，将待排序记录划分成两部分，左侧记录均小于或等于轴值，右侧记录均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。均≤ri'r1'ri-1'…ri'rn'ri+1'…r1ri-1…rirnri+1…均≥ri'运行实例10283216242030待排序序列第一趟排序结果第二趟排序结果第三趟排序结果102832162420301028321620301028322010283216242030最终排序结果关键问题如何选择轴值？选取不同轴值有什么后果?决定两个子序列的长度决定排序的时间性能解决方法：（1）第一个记录；（2）随机选取；（3）三数取中：取三个记录的中值；不失一般性，取第一个记录作为轴值10283216242030待排序序列10283216242030一次划分结果一次划分：以轴值为基准将无序序列划分为两部分如何实现一次划分——较大的记录移到后面，较小记录移到前面？记录的比较和移动从两端向中间进行较小的记录一次就能从后面移到前面（较大的记录？）减少了总的比较次数和移动次数关键问题10283216242030待排序序列10283216242030一次划分结果运行实例10283216242030待排序序列jij从后向前扫描直到r[j]<r[i]10283216242030ji交换r[j]和r[i]，i++10283216242030待排序序列j从后向前扫描直到r[j]<r[i]10283216242030ji交换r[j]和r[i]，i++i从前向后扫描直到r[j]<r[i]交换r[j]和r[i]，j--10283216242030ji重复上述过程，直到i等于j运行实例算法实现intSort::Partition(intfirst,intlast){ inti=first,j=last,temp;while(i<j) {}retutni;/*i为轴值记录的最终位置*/}为什么设置形参first和last？表示什么？1028321624203010283216242030表示待划分区间[first,last]，是变化的jiintSort::Partition(intfirst,intlast){ inti=first,j=last,temp;

while(i<j) {}

retutni;

}

while(i<j&&data[i]<=data[j])j--；if(i<j){temp=data[i];data[i]=data[j];data[j]=temp;i++;}

while(i<j&&data[i]<=data[j])i++；if(i<j){temp=data[i];data[i]=data[j];data[j]=temp;j--;}算法实现时间性能时间复杂度是多少？下标i和j共同将数组扫描一遍比较语句？执行次数？移动语句？执行次数？取决于待排序序列的初始状态O(n)10283216242030待排序序列10283216242030如何处理一次划分得到的两个待排序子序列？解决方法：递归执行快速排序一次划分结果voidSort::QuickSort(intfirst,intlast){intpivot=Partition(first,last);QuickSort(first,pivot-1);QuickSort(pivot+1,last);}算法描述：关键问题10283216242030待排序序列第一趟排序结果第二趟排序结果10283216242030102832162030何时结束递归？解决方法：若待排序序列只有一个记录，即待划分区间长度为1if(first>=last)return;关键问题voidSort::QuickSort(intfirst,intlast){ }else{intpivot=Partition(first,last);QuickSort(first,pivot-1);QuickSort(pivot+1,last);}if(first>=last)return;算法实现性