天津科技大学数据结构 排序

《天津科技大学数据结构 排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章排序概述插入排序交换排序选择排序归并排序分配排序外排序排序是计算机中经常遇到的操作。第十章　排序10.1 概述排序计算机内经常进行的一种操作，将一组“无序”的记录序列调整为“有序”的记录序列。例如：将下列关键字序列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,…，Rpn}的操作称作排序

2、。排序算法的稳定性判断标准：关键字相同的数据对象在排序过程中是否保持前后次序不变。如2,2*,1，排序后若为1,2*,2，则该排序方法是不稳定的。内部排序和外部排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。有序序列区无序序列区使有序区中记录的数目增加一个或几个的操作称为一趟排序。逐步扩大记录有序序列长度的方法大致有下列几类：插入类将无序序列中的

3、一个或几个记录“插入”到有序序列中；交换类通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加到有序子序列中;选择类从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中;归并类通过“归并”两个或两个以上的记录有序序列;其它方法10.2插入排序假设在排序过程中，记录序列R[1..n]的状态为：有序序列R[1..i-1]R[i]无序序列R[i+1..n]则一趟直接插入排序的基本思想：将记录R[i]插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i]。完成一趟“插入”需分三步进行：1．查找R[i]的插入位置j+1

4、；2．将R[j+1..i-1]中的记录后移一个位置；3．将R[i]复制到R[j+1]的位置上。一、直接插入排序利用顺序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。直接插入排序算法的三个要点：1、从R[i-1]起向前顺序查找，监视哨设置在R[0]；R[0]=R[i];//设置“哨兵”for(j=i-1;R[0].key

5、3．i=2，3，…,n,实现整个序列的排序。算法描述如下:voidInsertionSort(ElemR[],intn){//对记录序列R[1..n]作直接插入排序。for(i=2;i<=n;++i){R[0]=R[i];//复制为监视哨for(j=i-1;R[0].key

6、)=n-1“移动”的次数：0最坏的情况(关键字在记录序列中逆序有序)：“比较”的次数“移动”的次数直接插入排序所需进行关键字间的比较次数和记录移动的次数均为n2/4，所以直接插入排序的时间复杂度为O(n2)。直接插入排序是一种稳定的排序方法。原因：关键字相同的两个对象，在整个排序过程中，不会通过比较而相互交换。二、折半插入排序由于R[1..i-1]是一个按关键字有序的有序序列，则可利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。折半插入排序比直接插入排序明显地减少了关键字间的“比较”次数，但记录“移动”的次数不变。voidBInserti

7、onSort(ElemR[]，intn){//对记录序列R[1..n]作折半插入排序。for(i=2;i<=L.length;++i){R[0]=R[i];//将R[i]暂存到R[0]low=1;high=i-1;while(low<=high){//在R[low..high]中折半查找插入的位置m=(low+high)/2;//折半if(R[0].key