S10.1基本概念 。排序： ◆输入：n个记录R,R2,R,相应的key为K,K2,,K ◆输出：RR2,Rn,使得K,≤K2≤.≤K(或≥) Ch.10排序 稳定性：相同的k©ys经排序后相对次序不变 童内排和外排： ■分类： ①按方法分：插入，选择，交换，归井，分配 @按存贮方式分：顺序表、链表、辅助表 童就地排序：辅助空间O(1) "执用普鑫热条凳ReTypeh同前- 童以下只讨论增序 S10.2插入排序 §10.2.1直接插入排序（续） 基本思想：每次将待排序的记录，依ky大小插入到前面已 ■怎样将R叮插到有序区，使其扩充呢？ 排好序的子文件中的适当位重。 510.21直接播入排序 ①先找到正确的插入位置k(1≤k≤)：然后将 Rk.1-1]中记录后移1位，再插入 思想：待排序记录存于R1小中，排序过程中某一刻，R被 分为两子区间： ②从有序区尾向前查找插入位置，同时做后移操作 R1-1] R[L.n可 (二者交替进行)，直到找到第一个不大于 有序区 无序区（未排） R叮.key的记录为止，并将R叮插入其后。 当前无序区的第1个记录R可插入有序区R[1.i-1们中合适的位 量，使R[1变为有序区 初始时，因为R[1们自然有序，R[2.n为无序区，故只须从 R[2]开始播入 此过程类似于理牌 §10.2.1直接插入排序（续） §10.2.1直接插入排序（续） void InsertSort(SeqList R){ int i,j; 就地排序、稳定的排序 for(=2;i=n;i+)依次播入R2☒，Rn,共进行n-1脑排序 if(R可.key<R-1们key){香刚，R可在原位量上 例子略 RO]=R门：R0]既是喇兵，又起保存R可的作用 时间分析 j=i-1: dof ①最好情况：初始正序 从后向前在有序区R11]中找到第1个不大于R可.k@y的记录 每趟播入R门时，因为它都大于等于R-]的k©y,无须 Rj+1]=R[j]大于Ri】k@y的记录后移 移动，不进入内循环Cmin=n-1,Mm=0 ②最坏情况：韧始反序 while(R0.key<R[j.keyi刚兵防止魅界 ◆比较：每慧排序均需比较R[0.-1]中所有keys(f比较1 R[j+1]=R0:R叮擂入正璃位置循环线止于R[j】.key≤R0.key 次，do中比较1-1次)即比较次 Mendif C-=∑i=01 Ch.10 排序 2 §10.1 基本概念 „ 排序： ™输入：n个记录R1, R2, …, Rn，相应的key为K1, K2, …, Kn ™输出：Ri1, Ri2, …, Rin，使得Ki1≤Ki2 ≤ …≤ Kin(或≥) „ 稳定性：相同的keys经排序后相对次序不变 „ 内排和外排： „ 分类： ①按方法分：插入，选择，交换，归并，分配 ②按存贮方式分：顺序表、链表、辅助表 „ 就地排序：辅助空间O(1) „ 存贮结构说明：设n预先有定义。设RecType同前一章 NodeType。 SeqList为n+1个单元 „ 以下只讨论增序 3 §10.2 插入排序 基本思想：每次将待排序的记录，依key大小插入到前面已 排好序的子文件中的适当位置。 §10.2.1 直接插入排序 „ 思想：待排序记录存于R[1..n]中，排序过程中某一刻，R被 分为两子区间： R[1..i-1] R[i..n] 有序区 无序区（未排） 当前无序区的第1个记录R[i]插入有序区R[1..i-1]中合适的位 置，使R[1..i]变为有序区 初始时，因为R[1]自然有序，R[2..n]为无序区，故只须从 R[2]开始插入 此过程类似于理牌 4 §10.2.1 直接插入排序（续） „ 怎样将R[i]插到有序区，使其扩充呢？ ① 先找到正确的插入位置k（1≤k ≤ i）；然后将 R[k..i-1]中记录后移1位，再插入 ② 从有序区尾向前查找插入位置，同时做后移操作 （二者交替进行），直到找到第一个不大于 R[i].key的记录为止，并将R[i]插入其后。 5 §10.2.1 直接插入排序（续） void InsertSort(SeqList R){ int i, j; for (i=2; i<=n; i++) //依次插入R[2],..R[n]，共进行n-1趟排序 if (R[i].key<R[i-1].key) {//否则，R[i]在原位置上 R[0] = R[i]; //R[0]既是哨兵，又起保存R[i]的作用 j = i-1; do{ //从后向前在有序区R[1..i-1]中找到第1个不大于R[i].key的记录 R[ j+1] = R[ j ]; //大于R[ i ].key的记录后移 j--; }while (R[0].key<R[ j ].key); //哨兵防止越界 R[ j+1] = R[0];//R[i]插入正确位置,循环终止于R[ j ].key≤R[0].key }//endif } 6 §10.2.1 直接插入排序（续） „ 就地排序、稳定的排序 „ 例子略 „ 时间分析 ① 最好情况：初始正序 每趟插入R[i]时，因为它都大于等于R[i-1]的key，无须 移动，不进入内循环Cmin=n-1，Mmin=0 ② 最坏情况：初始反序 ‹ 比较：每趟排序均需比较R[0..i-1]中所有keys（if比较1 次，do中比较i-1次）即比较i次 2 max 2 ( ) n i C i On = = = ∑