第八章排序 基本概念 排序是计算机程序设计中的一种重要运算,其功能是将 个数据元素或记录)的任意序列,重新排列成一个按关键字有 序的序列 排序的确切定义为:设含有n个记录的序列为R,R2…,R} 其相应的关键字序列为{1K2…K,需确定一种排列 PH2使其相应的关键字满足如下的非递减关系 {Kn≤K2≤…≤Km},或非递增关系{n≥K2≥…≥Km 即使原来的序列R,R2…,R}成为一个按关键字有序的序列 {Rn1,R2…Rmn},这样的一种操作称为排序 定义中的关键字K可以是记录R(=1,2,…,n)主关键字 此时任何一个记录的无序序列经排序后得到的结果是唯一的
第 八 章 排 序 基本概念 排序是计算机程序设计中的一种重要运算, 其功能是将一 个数据元素(或记录)的任意序列, 重新排列成一个按关键字有 序的序列. 排序的确切定义为: 设含有n个记录的序列为 R1 ,R2 , ,R n 其相应的关键字序列为 K1 ,K2 , ,K n , 需确定一种排列 p1, p2, , pn, 使其相应的关键字满足如下的非递减关系 K p1 K p2 K pn , 或非递增关系 K p1 K p2 K pn 即使原来的序列 R1 ,R2 , ,R n 成为一个按关键字有序的序列 R p1 ,R p2 , ,R pn , 这样的一种操作称为排序. 定义中的关键字 Ki 可以是记录 R (i 1,2, ,n) i = 主关键字 此时任何一个记录的无序序列经排序后得到的结果是唯一的
当K,是记录R的次关键字时,则排序的结果不唯一,因待 排序的记录序列中可能存在两个或两个以上关键字相等的 记录.关键字K可以是记录中的单个数据项,也可是若干 数据项的组合 假设K=K,(1≤i≤n2l≤j≤n,i≠j),且在排列前的 序列中R领先于R(即i<j),若在排序后的序列中R仍领 领先于R,则称所用的排序方法是稳定的;反之,若可能使 排序后的序列中R领先于R,则称所用的排序方法是不稳 定的 由于待排序的记录数量不同,使排序过程中涉及的存 储器不同,由此排序方法分为两大类: 1.内部排序:待排序记录存放在计算机随机存储器中进行 的排序过程 2.外部排序:当待排序记录数量很大,以至内存一次无法 容纳全部记录,排序过程中需对外存进行访问的排序过程
当 Ki 是记录 Ri 的次关键字时, 则排序的结果不唯一, 因待 排序的记录序列中可能存在两个或两个以上关键字相等的 记录. 关键字 Ki 可以是记录中的单个数据项, 也可是若干 数据项的组合. 假设 K K (1 i n,1 j n,i j) i = j , 且在排列前的 序列中 Ri 领先于 Rj (即 i j ), 若在排序后的序列中 Ri 仍领 领先于 Rj , 则称所用的排序方法是稳定的;反之, 若可能使 排序后的序列中 Rj 领先于 Ri , 则称所用的排序方法是不稳 定的. 由于待排序的记录数量不同, 使排序过程中涉及的存 储器不同, 由此排序方法分为两大类: 1. 内部排序: 待排序记录存放在计算机随机存储器中进行 的排序过程. 2. 外部排序: 当待排序记录数量很大, 以至内存一次无法 容纳全部记录, 排序过程中需对外存进行访问的排序过程
本章只讨论内排序.在排序过程中需进行两种操作: (1)比较两个关键字的大小,这对大多数排序方法都是必 要的 (2)将记录从一个位置移动到另一个位置,并非必需,可 通过改变记录的存储方式予以避免 待排序的记录序列可有三种存储方式: (1)以一维数组作为存储结构,排序过程是对记录本身进 行物理重排,即通过比较和判定,把记录移到合适的 位置. (2)以链表(动态链表或静态链表)作为存储结构,排序过程 中无需移动记录,仅需修改指针即可. (3)有的排序方法难于在链表上实现,若仍需避免排序过程 中记录的移动,可建立一辅助表(如包括关键字和指向 记录的指针组成的索引表,从而排序过程中只需对
本章只讨论内排序. 在排序过程中需进行两种操作: (1)比较两个关键字的大小, 这对大多数排序方法都是必 要的. (2)将记录从一个位置移动到另一个位置, 并非必需, 可 通过改变记录的存储方式予以避免. 待排序的记录序列可有三种存储方式: (1)以一维数组作为存储结构, 排序过程是对记录本身进 行物理重排, 即通过比较和判定, 把记录移到合适的 位置. (2)以链表(动态链表或静态链表)作为存储结构, 排序过程 中无需移动记录, 仅需修改指针即可. (3)有的排序方法难于在链表上实现, 若仍需避免排序过程 中记录的移动, 可建立一辅助表(如包括关键字和指向 记录的指针组成的索引表), 从而,排序过程中只需对
辅助表的表目进行物理重排,只移动辅助表的表目,而 不移动记录本身 81插入排序 811直接插入排序 这是一种最简单的排序方法,具体做法是在插入第i 个记录时,[R,R2…,R1]已排好序,这时将关键字K依 次与关键字[K1,K2…K进行比较,从而找到应插入 的位置,然后将K对应的记录R插入,原位置的记录向后 顺推.下面举例说明其手工操作的过程 要求将下面一组以其关键字值表示的初始排列无序的 记录,用直接插入法排序成非递减有序序列 在手工操作的过程中,值表示第几趟插入,Ⅱ中的 序列表示已排好序的记录序列
辅助表的表目进行物理重排, 只移动辅助表的表目, 而 不移动记录本身. 8.1 插入排序 8.1.1直接插入排序 这是一种最简单的排序方法, 具体做法是在插入第i 个记录时, 1 2 1 , , , R R Ri− 已排好序, 这时将关键字 Ki 依 次与关键字 1 2 1 Ki− ,Ki− , ,K 进行比较, 从而找到应插入 的位置, 然后将 Ki 对应的记录 Ri 插入, 原位置的记录向后 顺推. 下面举例说明其手工操作的过程. 要求将下面一组以其关键字值表示的初始排列无序的 记录, 用直接插入法排序成非递减有序序列. 在手工操作的过程中, i的值表示第几趟插入, [ ]中的 序列表示已排好序的记录序列
序列的初始状态为[473361827212547 i=1B347]618272112547 i=23347618272 2547 下面给出直 接插入排序i=3[33476182]7 2547 的C函数,其 功能是对以1=4B34761282]12547 维数组存 储的一组无 1=533476172822547 序记录排列=6[1253347617282]47 成非递减有 序序列 25334747617282]
序列的初始状态为: 下面给出直 接插入排序 的C函数,其 功能是对以 一维数组存 储的一组无 序记录排列 成非递减有 序序列. 47 33 61 82 72 11 25 47 i =1 33 47 61 82 72 11 25 47 i = 2 33 47 61 82 72 11 25 47 i = 3 33 47 61 82 72 11 25 47 i = 4 33 47 61 72 82 11 25 47 i = 5 11 33 47 61 72 82 25 47 i = 6 11 25 33 47 61 72 82 47 i = 7 [11 25 33 47 47 61 72 82]