排序-(包含各种排序)(数据结构与算法).ppt

第9章 内部排序(internal sorting) 9.1 插入排序 insert sort 9.2 交换排序 exchange sort 9.3 选择排序 select sort 9.4 归并排序 merge sort 9.6 各种内部排序方法的比较讨论 9.1 插入排序insert sort 一、直接插入排序 二、其它插入排序 三、希尔排序 二、其它插入排序 9.2 交换排序 一、起泡排序 （bubble sort） 二、快速排序 (quick sort) 9.3 选择排序selection sort 一、简单选择排序(simple selection sort) 二、树形选择排序--堆排序(heap sort) 9.4 归并排序(merging sort) 重建堆 方法： 输出堆顶元素之后，以堆中最后一个元素替代之； 然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换； 重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选” 例 13 27 38 49 65 76 50 97 97 27 38 49 65 76 50 13 输出：13 27 49 38 97 65 76 50 13 输出：13 97 49 38 27 65 76 50 13 输出：13 27 38 49 50 27 65 76 97 13 输出：13 27 65 49 50 27 38 76 97 13 输出：13 27 38 堆排序举例 49 65 50 27 38 76 97 13 输出：13 27 38 76 65 50 27 38 49 97 13 输出：13 27 38 49 50 65 76 27 38 49 97 13 输出：13 27 38 49 97 65 76 27 38 49 50 13 输出：13 27 38 49 50 65 97 76 27 38 49 50 13 输出：13 27 38 49 50 97 65 76 27 38 49 50 13 输出：13 27 38 49 50 65 * 1、排序 是将一组数据元素（或记录）的任意序列，重新排列成一个按关键字有序序列。 其相应的关键字序列为{K1 ， K2 ，……， Kn}， 假设含n个记录的序列为：{R1，R2，……，R 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（即ij）。 3、内部排序、外部排序 内部排序：指的是待排序记录存放在计算机内存中进行的排序过程。 外部排序：指的是排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。 (2) 若可能使排序后的序列中Rj领先于Ri，则称所用的排序方法是不稳定的。 (1)若在排序后的序列中Ri仍领先Rj，则称所用的排序方法是稳定的； 4、排序方法 插入排序：直接插入排序、折半插入排序、希尔排序 交换排序：冒泡排序、快速排序 选择排序：简单选择排序、树形选择排序(堆排序) 归并排序：2-路归并排序 基数排序: 多关键字排序、链式基数排序 如果按内部排序过程中所需的工作量来区分，可分为： （1）简单排序，其时间复杂度为T(n)=O(n2) （2）先进的排序方法，其时间复杂度为T(n)=O(nlogn) （3）基数排序，其时间复杂度为T(n)=O(d.n) 一、直接插入排序 straight insert sort 直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增加1的有序表。 例如：已知待排序的一组记录的初始排列如下所示：R（49），R（38），R（65），R（97），R（76），R（13），R（27），R（19）。 假设在排序过程中，前四个记录已按关键字递增的次序，重新排列，构成一个含4个记录的有序序列: 现要将第5个（关键字为76）的记录插入上述序列，可以得到一个新的含5个记录的有序序列，则首先要找到插入的位置，然后进行插入。 假设从R（97）起向左进行顺序查找，由于65 ?76 ? 97，则R（76）应插入在R（65）和R（97）之间，从而得到下列新的有序序列: {R（38），R（49），R（65），R（76），R（97