ppt 数结构.pptVIP

第九章　内部排序;第一节　概述;　稳定的排序方法和非稳定的排序方法 　　当以记录的次关键字为排序依据时，由于可能存在关键 字值相同的记录，因而排序结果不唯一。 　　若用某方法进行排序时，对任意两个关键字值相同的记 录Ri和Rj，当原序列中Ri在Rj之前时，必有排序后Ri在Rj之前， 则称所用排序方法为稳定的排序方法，否则称不稳定的排序 方法。 ;　内部排序和外部排序 　　当待排记录数量较少时，可将其一次全部调入内存进行 排序，即称内部排序； 　　当待排记录数量较大时，在排序过程中尚需对外存进行 访问，则称外部排序。;　内部排序方法分类 　　按排序原则分：　　　　按工作量分： 　　插入排序　　　　　　　简单的排序方法　O(n2) 　　交换排序　　　　　　　先进的排序方法　O(nlogn) 　　选择排序　　　　　　　基数排序方法　　O(d·n) 　　归并排序 　　计数排序;　用顺序表保存待排记录，排序时直接移动记录； 　用静态链表保存待排记录，记录间次序关系由指针指 　　示，排序时不移动记录，而只修改指针值，排序结束 　　后，再对静态链表进行调整； 　用顺序表保存待排记录，另设向量保存各记录地址， 　　排序时不移动记录，而只移动地址向量中与该记录对 　　应的地址，排序结束后再按地址向量中的值调整记录 　　存储位置。;第二节　插入排序;【方法】 　　设对记录序列R1,R2,…,Rn进行排序，则： ⑴仅含R1的记录序列就是长度为１的按关键字有序的记录 　序列； ⑵依次逐个将Ri（i=2,3,…,n）插入已有的 长度为 i-1 的按 　关键字有序的记录序列，插入后应使记录序列仍按关键 　字有序且长度增１，为此需先通过查找以确定记录的插 　入位置； ⑶全部记录插入完毕所得长为ｎ的按关键字有序的记录序 　列即为排序结果。;【例】设有关键字序列(49,38,65,97,76,13,27,49)，写出用 　　　直接插入排序法进行排序的过程。 【分析】　　　　　　　　　　　　　　比较　　移动 初　始： ｉ＝２：　　　　　　　　　　　　　　３次　　３次 ｉ＝３：　　　　　　　　　　　　　　１次　　０次 ;38;【存储结构】用顺序表保存待排记录。 #define MAXSIZE 100　//定义待排记录的最多个数 typedef int KeyType; typedef struct{ 　KeyType key;　//待排记录关键字域 　…　//待排记录其它域 }RcdType; typedef struct{ 　RcdType r[MAXSIZE+1];　//下标为０的单元未用 　int length;　//待排记录个数 }SqList;　//顺序表类型;void InsertSort(SqList L){ 　for(i=2;i=L.length;++i) 　　if LT(L.r[i].key,L.r[i-1].key){ 　　　L.r[0]=L.r[i]; 　　　for(j=i-1;LT(L.r[0].key,L.r[j].key);--j) 　　　　L.r[j+1]=L.r[j]; 　　　L.r[j+1]=L.r[0]; 　　}//if }//InsertSort;【算法分析】 　　原记录序列已为正序时需比较ｎ－１次，移动０次，原 记录为逆序时需比较　　　　　　　　　　　　　次，移动 　　　　　　　　次，取两者平均值，约需比较　　　次， 移动　　　次。 　　算法时间复杂度为O(n2)，需一个记录的辅助空间。;【方法】 　　先将整个待排记录序列分割成若干子序列分别进行直接 插入排序，待整个序列中的记录基本有序时，再对全体记录 进行一次直接插入排序。其中子序列的构成不是简单地逐段 分割，而是将相隔某个“增量”的记录组成一个子序列。;【例】设有关键字序列(49,38,65,97,76,13,27,49,55,04)，取增 量序列为5,3,1，写出用希尔排序法进行排序的过程。 【分析】 初始 第一趟排序：增量为５ 子列一 ｉ＝６：; 子列二 ｉ＝７： 子列三 ｉ＝８： 子列四 ｉ＝９：; 子列五 ｉ＝１０： 第二趟排序：增量为３ 子列一 ｉ＝４： ｉ＝７： ｉ＝１０：; 子列二 ｉ＝５： ｉ＝８： 子列三 ｉ＝６： ｉ＝９：;第三趟排序：增量为１ ｉ＝２： ｉ＝３： ｉ＝４： ｉ＝５：; ｉ＝６： ｉ＝７： ｉ＝８： ｉ＝９： ｉ＝１０：;void ShellInsert(SqList L,int dk){ 　//以增量dk完成一次希尔排序 　for(i=dk+1;i=L.length;++i) 　　if LT(L.r[i].key,L.r[i-dk].key){ 　　　L.r[0]=L.r[i]; 　　　for(j=i-dk ; j0LT(L.r[0