算法课件--第9章(内排序).ppt

《算法课件--第9章(内排序).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章内排序★基本概念★插入排序★冒泡排序★选择排序★计数排序★希尔排序★堆排序★快速排序★合并排序★基数排序设含有n个记录的文件{R1,R2,…，Rn},其相应的关键字为{K1,K2,…，Kn}，需确定一种排列P(1),P(2),…,P(n),使其相应的关键字满足如下的递增(或递减)关系：KP(1)≤KP(2)≤KP(3)≤…≤KP(n)即，使上述文件成为一个按其关键字线性有序的文件{RP(1),RP(2),…，RP(n)},这样一种运算称为排序。9.1基本概念如果在排序期间具有相同关键字的记录的相对位置不变，则称此方法是稳定的。排序：排序的稳定性：即，1)K(i)≤K(i+1)

2、(1≤i≤n-1)2)若在输入文件中i

3、defstruct{intkey;datatypeotheritem;//其他域}records;typedefstructrecordsList[n+1];逐步扩大记录有序序列长度的方法大致有下列几类：1.插入类:将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度；2.交换类:通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度；3.选择类:从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度；4.归并类:通过“归并”

4、两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度；5.其它方法。内排序插入类排序直接插入排序折半插入排序希尔排序交换类排序冒泡排序快速排序选择类排序选择排序堆排序归并类排序归并排序其他排序计数排序基数排序9.2计数排序对每个记录计算文件中有多少个其它记录的关键字大于该记录的关键字值，从而找到该记录的正确排序位置。keyinfocount设一个记录有三个域：关键字域该记录的其他信息域计数域排序算法的思想：for(i=1;i

5、[j].count=R[j].count+1;}voidcountsort(ListR,intn){for(i=1;i<=n;i++)R[i].count=1;//对所有元素的count域置1；算法如下：设文件有n个记录，则外循环：i=1时，内循环要做n-1次比较；i=2时，内循环要做n-2次比较；…i=n-1时，内循环要做1次比较；总的比较次数为(n-1)+(n-2)+…+1=n(n-1)/2算法性能分析：所以，算法所需时间为O(n2)，由于不需要记录移动和额外空间，同时算法简单，当n较小时，可采用本算法。例关键字序列{46，55，13，42，44，17，05，70}关键字465

6、5134244170570初始化11111111i=131222221i=232333331i=332733341i=432753451i=532754561i=632754671i=7327546819.3直接插入排序假设在排序过程中，记录序列R[1..n]的状态为：则一趟插入排序的基本思想为：将记录R[i]插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i]。显然，完成这个“插入”需分三步进行：1．查找R[i]的插入位置j+1；2．将R[j+1..i-1]中的记录后移一个位置；3．将R[i]复制到R[j+1]的位置上。直接插入排序：利用顺

7、序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。注意直接插入排序算法的三个要点：1.从R[i-1]起向前进行顺序查找，监视哨设置在R[0]；R[0]=R[i]；{设置“哨兵”}j=i-1;while(R[0].key