数据结构(C++版)第8章-排序技术.pptVIP

第八章排序技术;概述;;排序前(56,34,47,23,66,18,82,47);排序的根本概念;排序的根本概念;多关键字排序;“高位优先”排序法：其中一种是先按花色分成有序的四类〔分别放入4个桶中〕，然后再按面值对每一类从小到大排序〔分别放入13个桶中〕。

两次分配，一次收集;“低位优先”排序法：

首先按面值从小到大把牌摆成13叠〔每叠4张牌〕，

然后将每叠牌按面值的次序收集到一起，

再对这些牌按花色摆成4叠，每叠有13张牌，

最后把这4叠牌按花色的次序收集到一起

是分配与收集交替进行。分配与收集的次数等于排序码的数目;排序的分类

内排序：在排序的整个过程中，待排序的所有记录全部被放置在内存中

2.外排序：由于待排序的记录个数太多，不能同时放置在内存，而需要将一局部记录放置在内存，另一局部记录放置在外存上，整个排序过程需要在内外存之间屡次交换数据才能得到排序的结果。;排序的分类

1.基于比较：根本操作——关键码的比较和记录的移动，其最差时间下限已经被证明为Ω〔nlog2n〕。

2.不基于比较：根据关键码的分布特征。;1.根本操作。内排序在排序过程中的根本操作：

⑴比较：关键码之间的比较；

⑵移动：记录从一个位置移动到另一个位置。

2.辅助存储空间。

辅助存储空间是指在数据规模一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。

3.算法本身的复杂程度。;排序算法的存储结构;8.2插入排序;根本思想：在插入第i〔i＞1〕个记录时，前面的i-1个记录已经排好序。;根本思想：在插入第i〔i＞1〕个记录时，前面的i-1个记录已经排好序。;直接插入排序过程例如;解决方法：

将第1个记录看成是初始有序表，然后从第2个记录起依次插入到这个有序表中，直到将第n个记录插入。;关键问题(2)如何查找待插入记录的插入位置?;voidinsertSort(intr[],intn){

for(i=2;i=n;i++){

r[0]=r[i];j=i-1;

while(r[0]r[j]){

r[j+1]=r[j];

j=j-1;

}

r[j+1]=r[0];

}

};直接插入排序算法性能分析;直接插入排序算法性能分析;平均情况下〔随机排列〕：

;空间性能：需要一个记录的辅助空间。

直接插入排序算法是一种稳定的排序算法。;插入排序;希尔排序;〔1〕应如何分割待排序记录，才能保证整个序列逐步向根本有序开展？

〔2〕子序列内如何进行直接插入排序？;根本有序：接近正序，例如{1,2,8,4,5,6,7,3,9}；

局部有序：局部有序，例如{6,7,8,9,1,2,3,4,5}。

局部有序不能提高直接插入排序算法的时间性能。;希尔插入排序过程例如;解决方法：

将相隔某个“增量”的记录组成一个子序列。

增量应如何取？

希尔最早提出的方法是d1=n/2，di+1=di/2。;解决方法：

在插入记录r[i]时，自r[i-d]起往前跳跃式〔跳跃幅度为d〕有哪些信誉好的足球投注网站待插入位置，并且r[0]只是暂存单元，不是哨兵。当有哪些信誉好的足球投注网站位置＜0，表示插入位置已找到。

在有哪些信誉好的足球投注网站过程中，记录后移也是跳跃d个位置。

在整个序列中，前d个记录分别是d个子序列中的第一个记录，所以从第d+1个记录开始进行插入。;希尔插入排序过程例如;算法描述：;希尔排序算法的时间性能;交换排序的主要操作是交换，其主要思想是：在待排序列中选两个记录，将它们的关键码相比较，如果反序〔即排列顺序与排序后的次序正好相反〕，那么交换它们的存储位置。;起泡排序;05;⑴在一趟起泡排序中，假设有多个记录位于最终位置，应如何记载？

⑵如何确定起泡排序的范围，使得已经位于最终位置的记录不参与下一趟排序？

⑶如何判别起泡排序的结束？;解决方法：

设变量exchange记载记录交换的位置，那么一趟排序后，exchange记载的一定是这一趟排序中记录的最后一次交换的位置，且从此位置以后的所有记录均已经有序。;关键问题⑴：如何记载一趟排序过程中交换的多个记录？;解决方法：

设bound位置的记录是无序区的最后一个记录，那么每趟起泡排序的范围是r[1]~r[bound]。

在一趟排序后，从exchange位置之后的记录一定是有序的，所以bound=exchange。;解决方法：

设bound位置的记录是无序区的最后一个记录，那么每趟起泡排序的范围是r[1]~r[bound]。

在一趟排序后，从exchange位置之后的记录一定是有序的，