计算机软件技术基础第八章排序ppt课件.ppt

《计算机软件技术基础第八章排序ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章排序8.1交换排序8.4归并排序冒泡排序一.二路归并排序快速排序二.文件归并排序8.2插入排序直接插入排序希尔排序对8.3选择排序一.简单选择排序二.堆排序第八章排序排序(sorting)——用某种方法，把元素的无序序列调整为按某数据项有序序列的过程。有序表——排序后的表；无序表——排序前的表;排序项——用于排序的数据项；排序码——排序项中的值。若以主关键字为排序项，排序结果唯一，否则排序结果不唯一。内部排序——排序过程全部在内存中进行。按照排序所采用的策略不同，内部排序可分为多类。本章讨论交换排序、插入排序、选择排序、归并排序四类排序；8.1交换排序交换排序——通过交换元素在

2、表中的位置使其有序的排序方法。一.冒泡排序(bubblesort)1.基本思路经过多遍比较及交换相邻元素实现排序。排序过程：反复扫描待排序表，扫描过程中做：①每一趟(扫描无序表一次)扫描将“最大者沉到底”——依次比较相邻元素并使之有序；②每一趟扫描，记录本趟扫描中最后一次发生元素交换的前一个位置；③记录每一趟扫描是否进行过元素交换；④直到某一趟扫描无元素交换发生，则排序完成。例如，对无序表(4938659776132744)进行冒泡排序（非递减），过程如下：①4938659776132744②3849657613274497③3849651327447697④384913274465

3、7697⑤3813274449657697⑥1327384449657697无交换发生，已排序。2.算法算法分析：时间复杂度：最坏情况，对无序表扫描n趟，每次下沉一个元素。共进行次比较，复杂度为O(n2)动态性能：稳定(在消除逆序过程中没有产生新的逆序)。思考：①算法的C语言描述②该算法扫描过程中，“大者”下沉速度大于“小者”上浮速度；若能加速“上浮”速度，则可提高效率。如何改进？二.快速排序快速排序(QuickSort)——冒泡排序的改进。基本思想：通过一趟排序把待排序表分成前后两部分，其中前一部分元素的排序码均不大于后一部分元素的排序码；然后对每部分元素以同样的方法进行排序，直到

4、全表元素按排序码有序。关键：如何把待排序表分为符合上述要求的两部分—线性表分割。1.线性表分割设待排序表为L，进行非递减排序，一趟排序的分割过程为：①设置指针i、j分别指向线性表的第一个和最后一个元素；②选取一个元素L(k)，做L(k)T，L(i)L(k)；③将j逐渐减小，同时逐次比较L(j)与T，直到L(j)T时，则把L(i)移到L(j)的位置上，即L(i)L(j)；⑤反复做③、④，直到i=j为止，此时令L(i)=T。例如，分割无序表(6538499776132744)，

5、取L(k)=49T653897761327443865977613274444386597761327443897761327654438279776136544382776139765443827137697384438271349769738iiiiiiiijjjjjjjj思考：算法的C语言描述？2.快速排序算法从快速排序的步骤可以看出，快速排序的过程即是对无序表逐层分割的过程。是一个递归的过程。如图：i-1ii+1m'i'n'mn设待排序表为L(m:n)，其中：m——待排序表起始位置，n——待排序表终止位置；split(l,m,n)为一趟分割无序表L的函数，且返回本趟分割点。快

6、速排序递归算法的C语言描述为：qksort(l,m,n)intm,n;eletyl[];{inti;if(n>m)//表长大于2{i=split(l,m,n);//分割表Lqksort(l,m,i-1);//对前半部分做快速排序qksort(l,i+1,n);//对后半部分做快速排序}return;}①关于L(k)的选取问题L(k)的选取直接关系到快速排序的时间效率：•若L(k)为表中最小项或最大项，则其中一子表长度为0，效率最低(每一趟排序只确定一个元素的位置)；复杂度：O(n2)•若L(k)平分线性表，则为最佳状态，效率最高。复杂度：O(nlog2n)实用中采用：•选取L(m)、

7、L()、L(n)值的中项；•在m、n之间产生随机数k(每个子表k不同)；②复杂度：空间复杂度：平均O(log2n)，最坏情况O(n)：时间复杂度：平均O(nlog2n)，最坏情况：O(n2)③动态性能：不稳定。适用于大表的排序。m+n28.2插入排序一.直接插入排序直接插入排序(straightinsertionsort)—简单排序方法之一。基本思想：将无序表中的元素逐个插入到已经有序的表中。问题：初始的有序表从何而来？解决：把无序表中的第一个元素，看作初