第9章内排序2试卷.ppt

* 第二趟收集的结果： 530 790 921 101 614 485 215 306 637 738 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 614 738 921 485 637 101 215 530 790 306 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 第三趟分配（按最高位 i = 1 ） 第三趟收集（让队尾指针e[i] 链接到下一非空队首指针f[i+1 ] ） 530 790 921 101 614 485 215 306 637 738 r[0]→ r[0]→ 排序结束！ 时间复杂度：若每个关键码有d 位，需要重复执行d 趟“分配”与“收集”。每趟对 n 个对象进行“分配”，对radix个队列进行“收集”。总时间复杂度为O(d*n)。 空间复杂度：算法中需要d次使用n个结点临时存放n个数据元素，所以空间复杂度为O（n）。 稳定性：基数排序是稳定的排序方法。 9.6.3 基数排序算法分析 * 主要内容 * 9.1 排序的基本概念 9.2 插入排序 9.3 交换排序 9.4 选择排序 9.5 归并排序 9.6 分配排序 9.7 性能比较 9.7 性能比较 * 排序方法 最好情况 平均时间 最坏情况 辅助存储 稳定性 直接插入 O(n) O(n2) O(n2) O(1） 稳定 冒泡 O(n) O(n2) O(n2) O(1） 稳定 简单选择 O(n2) O(n2) O(n2) O(1） 不稳定 希尔排序 O(n1.3） O(nlog2n )～ O(n2) O(n2) O(1) 不稳定 快速排序 O(nlog2n ) O(nlog2n ) O(n2) O(log2n ) 不稳定 堆排序 O(nlog2n ) O(nlog2n ) O(nlog2n ) O(1） 不稳定 二路归并 O(nlog2n ) O(nlog2n ) O(nlog2n ) O(n） 稳定 1．从时间复杂度选择 对元素个数较多的排序，可以选快速排序、堆排序、归并排序，元素个数较少时，可以选简单的排序方法。 2．从空间复杂度选择 尽量选空间复杂度为O(1)的排序方法，其次选空间复杂度为O(log2n)的快速排序方法，最后才选空间复杂度为O(n)的二路归并排序的排序方法。 * 9.7 性能比较 * （3）当待排序元素的个数n大，排序码分布可能会出现正序或逆序的情形，且对稳定性不做要求时，则采用堆排序或二路归并排序为宜。 （4）当待排序元素的个数n小，元素基本有序或分布较随机，且要求稳定时，则采用直接插入排序为宜。 （5）当待排序元素的个数n小，对稳定性不做要求时，则采用直接选择排序为宜，若排序码不接近逆序，也可以采用直接插入排序。冒泡排序一般很少采用。 9.7 性能比较 3．一般选择规则 （1）当待排序元素的个数n较大，排序码分布随机，而对稳定性不做要求时，则采用快速排序为宜。 （2）当待排序元素的个数n大，内存空间允许，且要求排序稳定时，则采用二路归并排序为宜。 * 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 简单选择排序没有把前一趟比较结果保留下来，在后一趟比较时，又重复比较一次，因此比较次数较多。而堆排序则是利用每次排序的结果，找出最小的值，也找出较小的记录。 * 叶子结点是没有孩子结点，无需调整 * * 注意 ：升序排列应建立大根堆还是小根堆？ * 每次筛选进行双亲和孩子的的比较和移动都不会超过完全 二叉树的深度，所以每次的时间复杂度为对数阶。 * * * 最高位优先法通常是一个递归的过程： 先根据最高位关键码K1排序,得到若干对象组，对象组中每个对象都有相同关键码K1。 再分别对每组中对象根据关键码K2进行排序，按K2值的不同，再分成若干个更小的子组，每个子组中的对象具有相同的K1和K2值。 依此重复，直到对关键码Kd完成排序为止。 最后，把所有子组中的对象依次连接起来，就得到一个有序的对象序列。 最低位优先法首先依据最低位关键码Kd对所有对象进行一趟排序