数据结构与算法分析第8讲排序

《数据结构与算法分析第8讲排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter8Sort什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,97一般情况下，假设含n个记录的序列为{R1,R2,…，Rn}其相应的关键字序列为{K1,K2,…，Kn}这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：Kp1≤Kp2≤…≤Kpn按此固有关系将上式记录序列重新排列为{Rp1,Rp2,…，

2、Rpn}的操作称作排序。内部排序和外部排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。三、内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：插入类交换类选择类归并类其它方法1.插入类将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度

3、。2.交换类通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。3.选择类从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。4.归并类通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。5.其它方法数据类型插入排序有序序列entry[1..i-1]entry[i]无序序列entry[i..n]一趟直接插入排序的基本思想：有序序列entry[1..i]无序序列entr

4、y[i+1..n]实现“一趟插入排序”可分三步进行：3．将entry[i]插入(复制)到entry[j+1]的位置上。2．将entry[j+1..i-1]中的所有记录均后移一个位置；1．在entry[1..i-1]中查找entry[i]的插入位置，entry[1..j].keyentry[i].key

5、-1]中查找entry[i]的插入位置”算法的实现要点：从entry[i-1]起向前进行顺序查找，监视哨设置在entry[0]；entry[0]=entry[i];//设置“哨兵”循环结束表明entry[i]的插入位置为j+1entry[0]jentry[i]for(j=i-1;entry[0].key

6、].key;--j);entry[j+1]=entry[j]entry[0]jentry[i]j=i-1上述循环结束后可以直接进行“插入”插入位置令i=2，3，…,n,实现整个序列的排序。for(i=2;i<=n;++i)if(entry[i].keyvoidSortable_list::insertion_sort(){//对顺序表L作直接插入

7、排序。for(i=2;i<=size();++i)if(entry[i].key

8、：“比较”的次数：最坏的情况（关键字在记录序列中逆序有序）：“比较”的次数：0“移动”的次数：“移动”的次数：因为entry[1..i-1]是一个按关键字有序的有序序列，则可以利用折半查找实现“在entry[1..i-1]中查找entry[i]的插入位置”，如此实现的插入排序为折半插入排序。二、折半插入排序Templ