初始正序每趟插入Ri.PPT

* * * * * * * * * * * * * * * * * * * * * Ch.10 排序 * §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个单元 以下只讨论增序 * §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]开始插入 此过程类似于理牌 * §10.2.1 直接插入排序（续） 怎样将R[i]插到有序区，使其扩充呢？ 先找到正确的插入位置k（1≤k ≤ i）；然后将R[k..i-1]中记录后移1位，再插入 从有序区尾向前查找插入位置，同时做后移操作（二者交替进行），直到找到第一个不大于R[i].key的记录为止，并将R[i]插入其后。 * §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].keyR[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].keyR[ j ].key); //哨兵防止越界 R[ j+1] = R[0];//R[i]插入正确位置,循环终止于R[ j ].key≤R[0].key }//endif } * §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次 * §10.2.1 直接插入排序（续） 移动：内循环中R[1..i-1]均后移，外加设置哨兵和将R[i]插到最终位置共移动i-1+2=i+1. 平均： 若记录随机分布。比较、移动平均为n2/4 §10.2.2 希尔排序 希尔排序(Shell Sort，又称缩小增量法)是一种分组插入排序方法。 1 排序思想 ① 先取一个正整数d1(d1n)作为第一个增量，将全部n个记录分成d1组，把所有相隔d1的记录放在一组中，即对于每个k(k=1, 2, … d1)，R[k], R[d1+k], R[2d1+k] , …分在同一组中，在各组内进行直接插入排序。这样一次分组和排序过程称为一趟希尔排序； ② 取新的增量d2d1，重复①的分组和排序操作；直至所取的增量di=1为止，即所有记录放进一个组中排序为止。 2 排序示例 设有10个待排序的记录，关键字分别为9, 13, 8, 2, 5, 13, 7, 1, 15, 11，增量序列是5, 3, 1，希尔排序的过程如图所示。 9 7 1 2 5 13 13 8 15 11 第一趟排序后: 2 5 1 9 7 13 11 8 15 13 第二趟排序后: 1 2 5 7