[工学]数据结构 ch10 排序

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

1、第十章排序§10.1概述§10.2插入排序§10.3交换排序§10.4选择排序§10.5归并排序§10.6基数排序§10.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}

2、这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Kp1≤Kp2≤…≤Kpn按此固有关系将式(1)的记录序列重新排列为{Rp1,Rp2,…，Rpn}的操作称作排序。二、内部排序和外部排序在本章内先讨论内部排序的各种方法，然后介绍外部排序的基本过程。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。三、内部排序的方法有序序列区无序序列区内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，参与排序的记录序列中

3、存在两个区域：有序区和无序区。使有序区中记录的数目增加一个或几个的操作称为一趟排序。有序序列区无序序列区1.插入类将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度；逐步扩大记录有序序列长度的方法大致有下列几类：2.交换类通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;3.选择类从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;4.归并类通过“归并”两个或两个以上的记录有序子

4、序列，逐步增加记录有序序列的长度;5.其它方法下面将对每一类的排序算法介绍一至两个排序算法。有序序列R[1..i-1]无序序列R[i..n]R[i]假设在排序过程中，记录序列R[1..n]的状态为：有序序列R[1..i]无序序列R[i+1..n]则一趟直接插入排序的基本思想为：将记录R[i]插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i]。§10.2插入排序显然，完成这个“插入”需分三步进行：2．将R[j+1..i-1]中的记录后移一个位置；3．将R[i]复制到R[j+1]的位置上。1．查找R[i]的插

5、入位置j+1；R[1..j]≤R[i]＜R[j+1..i-1]一、直接插入排序二、折半插入排序三、希尔排序§10.2插入排序一、直接插入排序利用顺序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。排序过程：整个排序过程为i-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。算法实现的要点：1.从R[i-1]起向前进行顺序查找,监视哨设置在R[0];R[0]=R[i];//设置“哨兵”for(j=i-1;R[0].key

6、rnj+1;//返回R[i]的插入位置为j+12.对于在查找过程中找到的那些关键字不小于R[i].key的记录，可以在查找的同时实现向后移动；for(j=i-1;R[0].key

7、R[i];//复制为监视哨for(j=i-1;R[0].key

8、657697)排序结果：（1）“比较”序列中两个关键字的大小；时间分析：实现排序的基本操作有两个：（2）“移动”记录。最好的情况：若待排