数据结构c课件第九章内部排序.ppt

《数据结构c课件第九章内部排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十章排序9.1排序的基本概念9.2插入类排序9.3交换类排序法9.4选择类排序法9.5归并排序9.6分配类排序9.7各种排序方法的综合比较9.1排序的基本概念排序：有n个记录的序列{R1，R2，…，Rn}，其相应关键字的序列是{K1，K2，…，Kn}，相应的下标序列为1，2，…，n。通过排序，要求找出当前下标序列1，2，…，n的一种排列p1，p2，…，pn，使得相应关键字满足如下的非递减（或非递增）关系，即：Kp1≤Kp2≤…≤Kpn，这样就得到一个按关键字有序的记录序列：{Rp1，Rp2，…，Rpn}。排序：是计算机内经常进行的一种操作，其目的是将一组无序的记录序列调

2、整为有序的记录序列。内部排序：整个排序过程完全在内存中进行，称为内部排序。外部排序：由于待排序记录数据量太大，内存无法容纳全部数据，排序需要借助外部存储设备才能完成，称为外部排序。稳定排序和不稳定排序：假设Ki=Kj(1≤i≤n，1≤j≤n，i≠j)，若在排序前的序列中Ri领先于Rj(即i

3、地存储方式，即向量结构(顺序结构)、链表结构以及记录向量与地址向量结合的表示方法。内部排序分类思想：逐步扩大有序子序列的长度：插入类排序、交换类排序选择类排序、归并类排序其它方法有序序列区无序序列区无序序列区有序序列区一趟排序1、插入类将无序子序列中的一个或几个记录插入到有序序列中，从而增加记录的有序子序列的长度。2、交换类通过交换无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。4、归并类从记录的无序子序列中选择关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录有序子序列的长度。通过归并两个

4、或两个以上的有序子序列，逐步增加记录有序子序列的长度。3、选择类9.2插入类排序基本思想：在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。9.2.1直接插入排序基本操作是将第i个记录插入到前面i-1个已排好序的记录中，具体过程为：将第i个记录的关键字Ki顺次与其前面记录的关键字Ki-1，Ki-2，…K1进行比较，将所有关键字大于Ki的记录依次向后移动一个位置，直到遇见一个关键字小于或者等于Ki的记录Kj，此时Kj后面必为空位置，将第i个记录插入空位置即可。一趟直接插入排序的基本思想：有序序列R[1

5、,….i-1]无序序列R[i,….n]R[i]有序序列R[1,….i]无序序列R[i+1,….n]实现一趟插入排序分三步进行：1、在R[1…i-1]中查找R[i]的插入位置j，使得R[1…j]≤R[i]

6、8{143548556277}3598{14353548556277}98{1435354855627798}直接插入排序算法假设待排序记录存放在r[1..n]之中，为了提高效率，我们附设一个监视哨r[0]，使得r[0]始终存放待插入的记录。voidInsSort(RecordTyper[],intlength)/*对记录数组r做直接插入排序，length为数组的长度*/{for(i=2;i<=length;i++){r[0]=r[i];j=i-1;/*将待插入记录存放到r[0]中*/while(r[0].key

7、[j];j=j-1;}r[j+1]=r[0];/*将待插入记录插入到已排序的序列中*/}}/*InsSort*/该算法的要点是：①使用监视哨r[0]临时保存待插入的记录。②从后往前查找应插入的位置。③查找与移动用同一循环完成。直接插入排序算法分析：从空间角度来看，它只需要一个辅助空间r[0]。从时间耗费角度来看，主要时间耗费在关键字比较和移动元素上。直接插入排序方法是稳定的排序方法。(待插入的元素的比较是从后向前进行的)最好的情况(关键字在记录序列中顺序有序)：“比较”的次数：“移动”的次数：最坏的情况(关键字在记录序列中逆序