10.2 10.2 插入排序插入排序v 直接插入排序直接插入排序v 折半插入排序折半插入排序v 2-2-路插入排序路插入排序v 表插入排序表插入排序 v 希尔排序希尔排序4.4.表插入排序表插入排序1 1）基本思想）基本思想 通过改变排序过程中采用的存储结构，减少通过改变排序过程中采用的存储结构，减少在排序过程中进行在排序过程中进行“移动移动”记录的操作。记录的操作。利用静利用静态链表进行排序态链表进行排序，并在排序完成之后，一次性地，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上调整到它们所应该在的位置上。#define MAXSIZE 100 /#define MAXSIZE 100 /静态链表容量静态链表容量TypedefTypedef structstruct RcdTypeRcdType rcrc; /; /记录项记录项 intint next; / next; /指针项指针项 SLNodeSLNode; /; /表结点类型表结点类型TypedefTypedef structstruct SLNodeSLNode rMAXSIZE+1; /0 rMAXSIZE+1; /0号单元为表头结点号单元为表头结点 intint length; / length; /链表当前长度链表当前长度 SLinkListTypeSLinkListType; /; /静态链表类型静态链表类型2 2）待排记录序列的存储结构）待排记录序列的存储结构3 3）具体做法）具体做法 首先将静态链表中数组下标为首先将静态链表中数组下标为“1” 1” 的分的分量（结点）和表头结点构成一个循环链表，然量（结点）和表头结点构成一个循环链表，然后依次将下标为后依次将下标为“2”2”至至“n”n”的分量（结点）的分量（结点）按记录关键字非递减有序插入到循环链表中。按记录关键字非递减有序插入到循环链表中。初始初始状态状态0 01 12 23 34 45 56 67 78 8MAXINTMAXINT494938386565979776761313272749491 10 0- - - - - - - -i=3i=30 01 12 23 34 45 56 67 78 8MAXINTMAXINT494938386565979776761313272749492 20 01 1- - - - - - -key域域next域域i=2i=20 01 12 23 34 45 56 67 78 8MAXINTMAXINT494938386565979776761313272749491 10 0- - - - - - - -38123650i=4i=40 01 12 23 34 45 56 67 78 8MAXINTMAXINT494938386565979776761313272749492 23 31 10 0- - - - - -9740i=5i=50 01 12 23 34 45 56 67 78 8MAXINTMAXINT494938386565979776761313272749492 23 31 14 40 0- - - - -i=6i=60 01 12 23 34 45 56 67 78 8MAXINTMAXINT494938386565979776761313272749492 23 31 15 50 04 4- - - -i=7i=70 01 12 23 34 45 56 67 78 8MAXINTMAXINT494938386565979776761313272749496 63 31 15 50 04 42 2- - -i=8i=80 01 12 23 34 45 56 67 78 8MAXINTMAXINT494938386565979776761313272749496 63 31 15 50 04 47 72 2- -76764 45 513136 62 227277 72 2493 38 84 4）表插入排序性能分析）表插入排序性能分析 从表插入排序的过程可见，表插入排序的基从表插入排序的过程可见，表插入排序的基本操作仍是将一个记录插入到已排好序的有序表本操作仍是将一个记录插入到已排好序的有序表当中。和直接插排序相比，不同之处当中。和直接插排序相比，不同之处仅是以修改仅是以修改2n2n次指针值代替移动记录次指针值代替移动记录，排序过程中所需进行，排序过程中所需进行的关键字间的的关键字间的比较次数相同比较次数相同。因此。因此表插入排序的表插入排序的时间复杂度仍是时间复杂度仍是O(nO(n2 2) )。4 4）表插入排序性能分析）表插入排序性能分析 表插入排序的结果只是求得一个有序链表，表插入排序的结果只是求得一个有序链表，则只能对它进行顺序查找，不能进行随机查找，则只能对它进行顺序查找，不能进行随机查找，为了能实现有序表的折半查找，尚需对记录进行为了能实现有序表的折半查找，尚需对记录进行重新排列。重新排列。5.5.希尔排序希尔排序1 1）基本思想）基本思想 又称为又称为“缩小增量排序缩小增量排序” 。先将整个待排。先将整个待排元素序列分割成若干个子序列（由相隔某个元素序列分割成若干个子序列（由相隔某个“增增量量”的元素组成的）分别进行直接插入排序，待的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序整个序列中的元素基本有序（增量足够小）时，（增量足够小）时，再对全体元素进行一次直接插入排序（再对全体元素进行一次直接插入排序（接近最好接近最好情况，效率很高情况，效率很高），因此希尔排序在时间效率上），因此希尔排序在时间效率上比前两种方法有较大提高。比前两种方法有较大提高。3 31 12 23 34 45 56 66565494997972525252513132 21 12 23 34 45 56 62525252513136565494997971 11 12 23 34 45 56 61313252525256565494997971 12 23 34 45 56 6131325252525494965659797增量增量3 3增量增量2 2增量增量1 1希希尔尔排排序序过过程程void void ShellInsertShellInsert ( ( SqListSqList &L, &L, intint dkdk ) ) /一趟希尔插入排序。本算法对直接插入算法作了以下修改：一趟希尔插入排序。本算法对直接插入算法作了以下修改： /1/1. .前后记录位置的增量是前后记录位置的增量是dkdk，而不是而不是1 1； /2.L.r0/2.L.r0只是暂存单元，不是哨兵。当只是暂存单元，不是哨兵。当j=0j=0时，插入位置已找到时，插入位置已找到 for ( i=dk+1; i=for ( i=dk+1; i=L.lengthL.length; +i ); +i ) if ( if ( L.ri.keyL.ri.key 0 & (L.r0.key0 & (L.r0.key L.rj.key);jL.rj.key);j -= -= dkdk) ) L.rj+dkL.rj+dk = = L.rjL.rj; ; / / 记录后移，查找插入位置记录后移，查找插入位置 L.rj+dkL.rj+dk = L.r0; = L.r0; / / 插入插入 /ShellInsertShellInsert2 2）希尔排序算法描述）希尔排序算法描述void void ShellSortShellSort ( (SqListSqList &L, &L, intint dltadlta , , intint t) t) / / 按增量序列按增量序列dlta0.t-1dlta0.t-1对顺序表对顺序表L L作希尔排序作希尔排序 for (k=0; kt; +k)for (k=0; k1; i-) i=n; i1; i-) /i/i表示趟数，最多表示趟数，最多n-1n-1趟趟 flag=0; flag=0; /开始时元素未交换开始时元素未交换 for (for (intint j=2; j=i; j+) j=2; j=i; j+) if ( if (RjRjRj-1) Rj-1) /发生逆序发生逆序 temp=temp=RjRj; ; RjRj=Rj-1; Rj-1=temp; =Rj-1; Rj-1=temp; flag=1; flag=1; if(flagif(flag=0) return; =0) return; / / BubblesortBubblesort2 2）起泡排序算法描述）起泡排序算法描述正序：正序： 只只需需进进行行一一趟趟排排序序，在在排排序序过过程程中中进进行行n-1n-1次次关关键键字字间的比较，且不移动记录；时间复杂度为间的比较，且不移动记录；时间复杂度为O(nO(n) ) 。逆序：逆序： 需需要要进进行行n-1n-1趟趟排排序序，需需要要进进行行n(n-1)/2n(n-1)/2次次比比较较，并并作等数量级的记录移动。总的时间复杂度为作等数量级的记录移动。总的时间复杂度为O(nO(n2 2) ) 。 起起泡泡排排序序方方法法是是稳稳定定的的。适适合合于于数数据据较较少少的的情况。情况。3 3）起泡排序算法分析）起泡排序算法分析2.2.快速排序快速排序背景背景 起泡排序的过程可见，起泡排序是一个增加起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只度的过程，每经过一趟起泡，无序序列的长度只缩小缩小 1 1。 试设想：若能在经过一趟排序，使无序序列试设想：若能在经过一趟排序，使无序序列的长度缩小一半，则必能加快排序的速度。的长度缩小一半，则必能加快排序的速度。1 1）基本思想）基本思想 通过一趟排序将待排序列以通过一趟排序将待排序列以枢轴枢轴为标准划分为标准划分成成两部分两部分，使其中一部分记录的关键字均比另一，使其中一部分记录的关键字均比另一部分小，再分别对这两部分进行快速排序，以达部分小，再分别对这两部分进行快速排序，以达到整个序列有序。到整个序列有序。 通常取第一个记录的值为基准值或枢轴通常取第一个记录的值为基准值或枢轴。2 2）具体做法具体做法 附设两个指针附设两个指针lowlow和和highhigh，初值分别指向第一，初值分别指向第一个记录和最后一个记录，设个记录和最后一个记录，设枢轴为枢轴为 keykey； (1)(1)从从high high 所指位置起向前搜索，找到第一所指位置起向前搜索，找到第一个不大于基准值的记录与枢轴记录相互交换个不大于基准值的记录与枢轴记录相互交换； (2)(2)从从low low 所指位置起向后搜索，找到第一个所指位置起向后搜索，找到第一个不小于基准值的记录与枢轴记录相互交换。不小于基准值的记录与枢轴记录相互交换。 (3)(3)重复这两步直至重复这两步直至low=highlow=high为止为止。2121 （ 21 03 37 13 91 09 21 03 37 13 91 09 ）lowlowhighhigh枢轴枢轴2121 （ 09 03 1309 03 13 21 21 91 3791 37 ）2121 （ 09 03 09 03 13 13 91 3791 37 ）lowlowhighhigh枢轴枢轴 2121highhigh枢轴枢轴（ 21 03 37 13 91 09 21 03 37 13 91 09 ）lowlow09092121 （ 0909 0303 37 13 37 13 9191 ）lowlow枢轴枢轴highhigh 3737 lowlowhighhighlowlow13133 3）一趟快速排序算法描述一趟快速排序算法描述intint Partition (Elem R , Partition (Elem R , intint low, low, intint high) high) R0 = R0 = RlowRlow; ; pivotkeypivotkey = = Rlow.keyRlow.key; ; while (low high) while (low high) /从两端交替向中间扫描从两端交替向中间扫描 while (low high & while (low = = pivotkeypivotkey) - - high;) - - high; RlowRlow = = RhighRhigh; ; /将比枢轴记录小的移到低端将比枢轴记录小的移到低端 while (low high & while (low high & Rlow.keyRlow.key = = pivotkeypivotkey) + + low;) + + low; RhighRhigh = = RlowRlow; ; /将比枢轴记录大的移到高端将比枢轴记录大的移到高端 RlowRlow = R0; = R0; /枢轴记录到位枢轴记录到位 return low; return low; /返回枢轴位置返回枢轴位置 / Partition/ Partition对记录序列对记录序列RlowRlow.highhigh进行快速排序算法进行快速排序算法void void QSortQSort ( Elem R , ( Elem R , intint low, low, intint high ) high ) if (low high) if (low high) /长度大于长度大于1 1 pivopivo = = PartitionPartition( ( L,low,highL,low,high); ); /将将Rlow.highRlow.high 一分为二一分为二 QSort(L,lowQSort(L,low, pivo-1); , pivo-1); /对低子表递归排序，对低子表递归排序，pivopivo是枢轴是枢轴 QSort(LQSort(L, pivo+1, high); , pivo+1, high); / / 对高子表递归排序对高子表递归排序 / / QSortQSort对记录序列进行快速排序对记录序列进行快速排序void void QuickSort(ElemQuickSort(Elem R, R, intint n) n) QSortQSort(R(R, 1, n);, 1, n); / / QuickSortQuickSort4 4）快速排序分析快速排序分析 最好的情形（左、右子区间的长度大致相等）最好的情形（左、右子区间的长度大致相等）, ,快速排快速排序的最好时间复杂度应为序的最好时间复杂度应为O(nlogO(nlog2 2n)n)。 最坏的情形（每次能划分成两个子区间，但其中一个是最坏的情形（每次能划分成两个子区间，但其中一个是空），快速排序的最坏时间复杂度为空），快速排序的最坏时间复杂度为O(nO(n2 2) )。 对对n n较大的情况，它是平均速度最快的排序算法，但当较大的情况，它是平均速度最快的排序算法，但当n n很小时，此方法往往比其他简单排序方法还要慢。很小时，此方法往往比其他简单排序方法还要慢。 快速排序是快速排序是不稳定不稳定的。的。