第八章排序 基本概念 排序是计算机程序设计中的一种重要运算,其功能是将 个数据元素或记录)的任意序列,重新排列成一个按关键字有 序的序列 排序的确切定义为:设含有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]
struct node f int key; int data; typedef struct node node void insertsort(r, n) NODE rl l;intn;/*r为具有n+1个单元的数组,n为记录个数* f int i, j; for(i=2; i<=n; i++) {r|0=r[i;*将待排序记录赋予下监视哨* while(r10key< rIjn. key)/待排序记录的关键字值与有序子序列*/ /的各记录的关键字值进行比较/ r计+1rj-;/若条件真,则rj记录后移* ri+1-r|0];/若条件假,则待排序记录插入到相应位置*
struct node { int key; int data; }; typedef struct node NODE; void insertsort(r,n) NODE r[ ]; int n; /* r[ ]为具有n+1个单元的数组, n为记录个数*/ { int i,j; for(i=2;i<=n;i++) { r[0]=r[i]; /* 将待排序记录赋予下监视哨*/ j=i-1; while(r[0].key<r[j].key) /*待排序记录的关键字值与有序子序列*/ /*的各记录的关键字值进行比较/* r[j+1]=r[j--]; /*若条件真, 则r[j]记录后移*/ r[j+1]=r[0]; /*若条件假, 则待排序记录插入到相应位置*/ } }
算法简洁、容易实现是直接插入排序的两大特点, 下面分析其时间效率 整个排序过程中只有比较关键字和移动记录两种运 算.当原始记录已按关键字非递减有序,即为正序时, 时间效率最高,因完成每趟排序仅需进行一次比较及两 次移动记录操作(即开始时将记录移至监视哨中和最后将 记录移入适当位置,整个排序过程总的比较次数为n-1, 记录总的移动次数为(m-1,故其时间复杂度为Omn); 反之,如果原始记录是按关键字非增减有序的,即为 逆序时,时间效率最低,因要插入的第个记录,均要与 前i-1个记录及监视哨的关键字进行比较,即每趟要进行 i次比较,总的比较次数为: ∑i=(n+2)(n-1)/2
算法简洁﹑容易实现是直接插入排序的两大特点, 下面分析其时间效率. 整个排序过程中只有比较关键字和移动记录两种运 算. 当原始记录已按关键字非递减有序, 即为正序时, 时间效率最高, 因完成每趟排序仅需进行一次比较及两 次移动记录操作(即开始时将记录移至监视哨中和最后将 记录移入适当位置), 整个排序过程总的比较次数为n-1, 记录总的移动次数为2(n-1), 故其时间复杂度为O(n); 反之, 如果原始记录是按关键字非增减有序的,即为 逆序时, 时间效率最低, 因要插入的第i个记录, 均要与 前i –1个记录及监视哨的关键字进行比较, 即每趟要进行 i次比较, 总的比较次数为: ( 2)( 1)/ 2 2 = + − = i n n n i
从移动记录的次数来看,每趟排序中除了上面提到的两 次移动外,还需将有序子序列中关键字值大于待排序记 录的关键字值的记录后移一个位置,总的移动次数为: ∑(+1)=(n+4)(n-1)/2 故其时间复杂度为O(n2) 若在随机情况下,设待排序记录序列可能出现的各 种排列的概率相同,则可取上述两种极端情况的平均值 作为比较和移动记录的平均次数,约为n2/4.由此,直 接插入排序的时间复杂度为Omn2) 直接插入排序是稳定的排序方法 对于直接插入排序,补充一C函数,其功能为:将 以带头结点的单链表存储的一组无序记录,排序成非递 减序列
从移动记录的次数来看, 每趟排序中除了上面提到的两 次移动外, 还需将有序子序列中关键字值大于待排序记 录的关键字值的记录后移一个位置, 总的移动次数为: ( 1) ( 4)( 1)/ 2 2 + = + − = i n n n i 故其时间复杂度为 ( ). 2 O n 若在随机情况下, 设待排序记录序列可能出现的各 种排列的概率相同, 则可取上述两种极端情况的平均值 作为比较和移动记录的平均次数, 约为 /4 2 n . 由此, 直 接插入排序的时间复杂度为 ( ). 2 O n 直接插入排序是稳定的排序方法. 对于直接插入排序, 补充一C函数, 其功能为: 将 以带头结点的单链表存储的一组无序记录, 排序成非递 减序列
struct node int key; struct node *next;; typedef struct node node void insertsort(h NODE *h INODE*p, *r* 1, q; int exchang: =h->next;/指向有序子表的表尾 q=l->next;/*q指向待排序的结点 while(q=null) p=h->next;/p指向有序子表的表头,排序过程中可向表尾移动* r=h /*r指向p的直接前趋结点* exchang=0;/标识结点未交换* while(p!=q & exchang==0) fif(p->keykey) r=p;p=r->next;}/结点后移*
struct node { int key; struct node *next; }; typedef struct node NODE; void insertsort(h) NODE *h; { NODE *p,*r,*l,*q; int exchang; l= h->next; /*l指向有序子表的表尾*/ q=l->next; /*q指向待排序的结点*/ while(q!=null) { p=h->next; /* p指向有序子表的表头, 排序过程中可向表尾移动*/ r=h; /* r指向p的直接前趋结点*/ exchang=0;/*标识结点未交换*/ while(p!=q && exchang==0) { if(p->keykey) { r=p; p=r->next; } /*结点后移*/
se RI->next=q->next; q->next=p r->next=q; /待排序的结点前插* exchang-l; /标识结点有交换* if(p=q)l=q;/一趟排序未交换q指向的待排序结点成为有+ /序子表的表尾结点 q=->next;/q指向下一趟排序的待排序结点* 811希尔排序 希尔排序是对直接插入排序法的一种改进,提高了 排序的效率.希尔排序的作法是:先取定一个小于待排 序记录个数n的整数d1作为第一个增量,将待排序的所有
else { l->next=q->next; q->next=p; r->next=q; /*待排序的结点前插*/ exchang=1; /*标识结点有交换*/ } } if(p==q) l=q;/*一趟排序未交换, q指向的待排序结点成为有*/ /*序子表的表尾结点*/ q=l->next; /*q指向下一趟排序的待排序结点*/ } } 8.1.1希尔排序 希尔排序是对直接插入排序法的一种改进, 提高了 排序的效率. 希尔排序的作法是: 先取定一个小于待排 序记录个数n的整数d1 作为第一个增量, 将待排序的所有