数据结构与10排序4 .ppt

10.1.2 折半(二分)插入排序 例：初始关键字如下：n=11， d1=5，d2=3，d3=1 49 38 65 97 76 13 27 49 55 04 10 基本思想：有n个记录存在数组r[1 .. n]中，将相邻元素的关键字进行比较交换，必要时两元素交换。 即：若r[i].keyr[i+1].key，则r[i] r[i+1]， (i=1…n-1) 一趟起泡后，最大的元素就落在最底部。 第二趟起泡排序的范围是r[1 .. n-1]；…… 直到没有任何交换；最多需要n-1趟冒泡排序 10.2.2 快速排序 基本思想： 在待排序列中选一个关键字，按某一规律进行多次比较交换后，它移到某一位置，此元素将记录分割成独立的两部分，它左边的关键字都小于或等于它，右边的关键字都大于或等于它。之后对这两部分分别进行快速排序 10.3.2 树型选择排序 又称锦标赛排序。 基本思想：首先对n个记录的关键字进行两两比较，然后在其中 ?n/2? 个较小者之间再进行两两比较，如此重复，直到选出最小关键字的记录为止。 这个排序过程可用一棵有n个叶子结点的完全二叉树表示。 10.3.3 堆排序 第1趟：在r[1..n]中进行n-1次比较，选择最小的r[k]，让r[k] ? r[1]； …… 第i趟：在r[i..n]中进行n-i次比较，选择最小的r[k]，让r[k] ? r[i]； …… 第n-1趟：在r[n-1..n]中进行1次比较，选择最小的r[k]，让r[k] ? r[n-1]； 第i趟：在n-i+1(i=1，2，…n-1)个记录中选择值最小的记录作为有序序列的第i个记录。 10.3.1 直接选择排序 例：数组：（37，18，64，14，96，48，42） 第1 趟结果 14 [18，64，37，96，48，42](i=2，k=2) 第2趟结果 14 18 [64，37，96，48，42](i=3,k=4) 第3趟结果 14 18 37 [64，96，48，42] (i=4，k=7) 第4趟结果 14 18 37 42 [96，48，64](i=5，k=6) 当i=1时 : [37，18，64，14，96，48，42](i=1，k=4) 第5趟结果 14 18 37 42 48 [96，64](i=6，k=7) 第6趟结果 14 18 37 42 48 64 [96] void selectsort(SqList L){ for(i=1；i≤L.length；i++) { k=i； for(j=i+1；j≤L.length；j++) if(L.r[j].keyL.r[k].key) k=j； if(k≠i) L.r[k]? L.r[i] } } //selectsort 时间： 性能分析： (1) 时间： 该算法不受初始序列特征的影响。 T(n)= O(n2) (2) 空间： 一个记录空间：S(n)= O(1） (3) 稳定性： 不稳定的排序方法。例：（6，6，4） 输出最小关键字之后，将该关键字对应的叶子结点中的关键字改为最大值，然后从该叶子结点开始，和其左（右）兄弟的关键字进行比较，… 49 38 97 65 13 27 76 49 38 65 13 27 38 13 13 含n个叶子结点的完全二叉树的深度为 ?log2n? +1， 除了最小的关键字之外，每选择一个次小关键字需进行?log2n?次比较。 缺点： (1) 辅助存储空间较多，对n个记录需2n-1个存储单元。 (2) 和最大值的比较是多余的。 T(n) = O(nlog2n) 49 38 97 65 13 27 76 49 38 65 13 27 38 13 13 ? 76 27 27 堆：n个元素的序列{k1，k2，…，kn}，当且仅当满足以下关系时，称之为堆。 ki ≤k2i ki ≥k2i ki ≤k2i +1 ki ≥k2i +1 或 i=1，2，… ，?n/2? 小根堆 大根堆 若将此序列看成是完全二叉树的按层次遍历的序列，则完全二叉树中所有非终端结点的值均不大于(或不小于)其左右孩子的值。 2i 2i+1 i 例：序列{96，83，27，38，11，09} 对应的完全二叉树为： 大根堆 96