第9章内排序2讲述.ppt

时间复杂度：若每个关键码有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对所有对象进行一趟排序，再依据次低位关键码Kd-1对上一趟排序的结果再排序，依次重复，直到依据关键码K1最后一趟排序完成，就可以得到一个有序的序列。使用这种排序方法对每一个关键码进行排序时，不需要再分组，而是整个对象组都参加排序。 * * 与前面介绍的排序算法不同，前面是通过排序码之间的比较和移动操作来进行的。 * * * 练习：已知序列{503，87，512，61，908，170，897，275，653，462}，写出采用堆排序法对该序列作升序排列的第一趟结果。 * 第一趟结果：{908,653,897,503,462,170,512,275,61,87} 9.4.2 堆排序 * 5、堆排序算法分析： 时间效率： O(nlog2n)。因为整个排序过程中需要调用n-1次堆顶点的调整，而每次堆排序算法本身耗时为log2n； 空间效率：O(1)。仅在第二个for循环中交换记录时用到一个临时变量temp。 稳定性： 不稳定。 优点：对小文件效果不明显，但对大文件有效。 9.4.2 堆排序 主要内容 * 9.1 排序的基本概念 9.2 插入排序 9.3 交换排序 9.4 选择排序 9.5 归并排序 9.6 分配排序 9.7 性能比较 9.5 归并排序 * 1、基本思想：将若干有序序列逐步归并，最终得到一个有序序列。 （归并