第9章排序 91概述 1、排序 ●排序是计算机程序设计中的一种重要操作,它的功能是将一个 数据元素(或记录)的任意序列,重新排列成一个按关键字有 序序列。 ●假设含n个记录的序列为:·其相应的关键字序列为 ●{R1,R2,……,Rn}(9.1) {K1,K 2 njs 需确定1,2,…,n的一种排列P1,P2,…,Pn,使其相 应的关键字满足如下的非递减(或非递增)关系 Kp1≤Kp2≤…Kpn,即使(91)式的序列成为一个按关键字 有序的序列{Rp1,Rp2,……,Rpn},这样一种操作称为排序。 北京邮电大学自动化学院
北京邮电大学自动化学院 1 第9章 排序 ⚫ 9.1 概述 ⚫ 1、排序 ⚫ 排序是计算机程序设计中的一种重要操作，它的功能是将一个 数据元素（或记录）的任意序列，重新排列成一个按关键字有 序序列。 ⚫ 其相应的关键字序列为 ⚫ {K1，K2，……，K n }， ⚫ 假设含n个记录的序列为： ⚫ {R1，R2，……，R n } (9.1） ⚫ 需确定1，2，……， n的一种排列P1，P2，……，P n，使其相 应的关键字满足如下的非递减（或非递增）关系 KP1KP2……KP n，即使（9.1）式的序列成为一个按关键字 有序的序列{RP1，RP2，……，RPn}，这样一种操作称为排序
●2、稳定的、非稳定的 假设K产K(1m,1jn,词)且在排序前的序列中 R领先R(即j)。 ●若在排序后的序列中R仍领先R,则称所用的排序方法是稳 定的; ●反之,若可能使排序后的序列中R领先于R,则称所用的 排序方法是不稳定的。 3、内部排序、外部排序 ●内部排序:指的是待排序记录存放在计算机随机存储器中 进行的排序过程。 外部排序:指的是排序记录的数量很大,以致内存一次 不能容纳全部记录,在排序过程中尚需对外存进行访问 的排序过程。 北京邮电大学自动化学院
北京邮电大学自动化学院 2 ⚫ 2、稳定的、非稳定的 ⚫ 3、内部排序、外部排序 ⚫ 假设Ki=Kj（1 i n，1 j n，ij）且在排序前的序列中 Ri领先Rj（即i<j）。 ⚫ 内部排序：指的是待排序记录存放在计算机随机存储器中 进行的排序过程。 ⚫ 外部排序：指的是排序记录的数量很大，以致内存一次 不能容纳全部记录，在排序过程中尚需对外存进行访问 的排序过程。 ⚫ 反之，若可能使排序后的序列中Rj领先于Ri，则称所用的 排序方法是不稳定的。 ⚫ 若在排序后的序列中Ri仍领先Rj，则称所用的排序方法是稳 定的；
°4、排序方法 入排序:直接插入排序、折半插入排序、希尔排序 交换排序:冒泡排序、快速排序 选择排序:简单选择排序、树形选择排序、堆排序 归并排序:2-路归并排序 ●基数排序:多关键字排序、链式基数排序 ●如果按内部排序过程中所需的工作量来区分,可分为: (1)简单排序,其时间复杂度为Tn)=O(n2) (2)先进的排序方法,其时间复杂度为Tn)= o(nlogn (3)基数排序,其时间复杂度为T(m)=O(dn) 5、排序基本操作: (1)比较两个关键字大小; (2)将记录从一个位置移动到另一个位置。 北京邮电大学自动化学院
北京邮电大学自动化学院 3 ⚫ 4、排序方法 ⚫ 插入排序：直接插入排序、折半插入排序、希尔排序 ⚫ 交换排序：冒泡排序、快速排序 ⚫ 选择排序：简单选择排序、树形选择排序、堆排序 ⚫ 归并排序：2-路归并排序 ⚫ 基数排序: 多关键字排序、链式基数排序 ⚫ 如果按内部排序过程中所需的工作量来区分，可分为： ⚫ （1）简单排序，其时间复杂度为T(n)=O(n²) ⚫ （2）先进的排序方法，其时间复杂度为T(n)=O(nlogn) ⚫ （3）基数排序，其时间复杂度为T(n)=O(d.n) ⚫ 5、排序基本操作 ： ⚫ （1）比较两个关键字大小； ⚫ （2）将记录从一个位置移动到另一个位置
91插入排序 ●插入排序的基本思想是:每一步将一个待排序的记录,按 其主关键字的大小插入到前面已经排序的文件中适当位置 上,直至全部插完为止。 ●1、直接插入排序 直接插入排序是一种最简单的排序方法,它的基本操作 是将一个记录插入到已排好的有序表中,从而得到一个 新的、记录数增加1的有序表。 例如:已知待排序的一组记录的初始排列如下所示:R (49),R(38),R(65),R(97),R(76),R (13),R(27),R(19)。 北京邮电大学自动化学院 4
北京邮电大学自动化学院 4 ⚫ 插入排序的基本思想是：每一步将一个待排序的记录，按 其主关键字的大小插入到前面已经排序的文件中适当位置 上，直至全部插完为止。 9.1 插入排序 ⚫ 1、直接插入排序 ⚫ 直接插入排序是一种最简单的排序方法，它的基本操作 是将一个记录插入到已排好的有序表中，从而得到一个 新的、记录数增加1的有序表。 ⚫ 例如：已知待排序的一组记录的初始排列如下所示：R （49），R（38），R（65），R（97），R（76），R （13），R（27），R（19）
1、直接插入排序 很设在排序过程中,前四个记录已按关键字递增的次序,重 新排列,构成一个含4个记录的有序序列: ●{38,49,65,97} (93) ●现要将第5个(关键字为76)的记录插入上述序列,可以得 到一个新的含5个记录的有序序列,则首先要找到插入的位 置,然后进行插入。 ●假设从R(97)起向左进行顺序查找,由于65≤76≤97,则 R(76)应插入在R(65)和R(97)之间,从而得到下列新 的有序序列: {R(38),R(49),R(65),R(76),R(97)}(9.4) ●称从式(93)到式(94)的过程为一趟直接插入排序。 北京邮电大学自动化学院
北京邮电大学自动化学院 5 1、直接插入排序 ⚫ 假设在排序过程中，前四个记录已按关键字递增的次序，重 新排列，构成一个含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）} (9.4) ⚫ 称从式（9.3）到式（9.4）的过程为一趟直接插入排序。 ⚫ {38，49，65，97} (9.3)