《数据结构》-第十章a插入排序

1,第十章 内部排序,10.1 概述,10.2 插入排序,10.2.1 直接插入排序,10.2.2 其他插入排序,10.2.3 希尔排序,10.3 快速排序,10.4 选择排序,10.4.1 简单选择排序,10.4.2 树形选择排序,10.4.3 堆排序,10.5 归并排序,10.6 基数排序,10.6.1 多关键字的排序,10.6.2 链式基数排序,10.7 各种内部排序方法的比较讨论,2,（1）相关术语 假设含有n个记录的序列为R1, R2, , Rn（10 1）其相应的关键字序列为K1, K2, , Kn需确定1, 2, , n的一种排列p1, p2, , pn，使其相应的关键字满足如下的非递减（或非递增）关系,（10 2）,即使式（101）的序列成为一个按关键字有序的序列,（10 3）,这样一种操作称为排序。,10.1 概述,3,例如：将下列关键字序列52, 49, 80, 36, 14, 58, 61, 23, 97, 75调整为14, 23, 36, 49, 52, 58, 61 ,75, 80, 97,4,假设Ki = Kj(1in, 1jn, ij)(此时Ki和Kj是记录的次关键字)，且在排 序前的序列中Ri领先于Rj（即i = high + 1; j)/记录后移 L.rj + 1 = L.rj;L.rhigh + 1 = L.r0;/插入 / for / BInertSort,时间复杂度为：O(n2)。,18,（2）2-路插入排序,主要思想 2-路插入排序是在折半排序的基础上再改进之，其目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。 在2-路插入排序中，移动记录的次数约为n2/8。,算法实现,另设一个和L.r同类型的数组d，首先将L.r1赋值给d1，并将d1看成是在排好序的序列中处于中间位置的记录，然后从L.r中第2个记录起依次插入到d1之前或之后的有序序列中。先将待插记录的关键字和d1的关键字进行比较，若L.ri.key i的分量，则互换SL.ri和SL.rp，且令SL.ri中的指针域的值改为p；由于此时数组中所有小于i的分量中已是“到位”的记录，则当pi时，应顺链继续查找直到pi为止。,表插入排序的结果只是求得一个有序链表，则只能对它进行顺序查找，不能进行随机查找，为了能实现有序表的折半查找，尚需对记录进行重新排列。,24,2算法实现 算法10.3如下： void Arrange (SLinkList / for / Arrange,25,3例子,例如，图10.4所示为重排记录的全部过程。,26,图12.4 重排静态链表数组中记录的过程,27,10.2.3 希尔排序,希尔排序（Shells Sort）又称“缩小增量排序”(Diminishing Increment Sort)，它是一种属插入排序类的方法。,（1）主要思想 主要思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排 序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。,28,10.2.3 希尔排序,（2）算法实现,void ShellInsert (SqList /插入 / ShellInsert,29,算法10.5如下：void ShellSort (SqList /一趟增量为dltak的插入排序 / ShellSort,30,初始关键字序列如图10.5的第1行所示。首先将该序列分成5个子序列：R1, R6, R2, R7, , R5, R10，分别对每个子序列进行直接插入排序。然后将第1趟希尔排序的结果分成3个子序列：R1, R4, R7, R10, R2, R5, R8和R3, R6, R9，并对它们进行直接插入排序。最后对整个序列进行一趟直接插入排序。至此，希尔排序结束，整个序列的记录已按关键字非递减有序排列。,31,图10.5 希尔排序示例,32,例如，在上例中，第一趟排序