数据结构第十章排序要点.ppt

10.2 插入排序 10.3 交换排序 10.4 选择排序 10.1 概述 10.5 归并排序 10.6 基数排序 10.7 各种内部排序方法的比较 基数排序 排序思想：基数排序是按组成关键字的各位的值进行分配和收集，与前面介绍的排序方法不同，它无需进行关键字之间的比较。 设关键字有d 位，每位的取值范围为 r (称为基数)，则需要进行d 趟分配与收集，需要设立 r 个队列。 例如，关键字是4位字符串，需要26个队列，4趟分配与收集；关键字3位十进制数，需要10个队列，3趟分配与收集 基数排序过程 278—109—063—930—589—184—505—269—008—083 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 278 p p 109 p 063 p 930 p 589 p 184 p 505 p 269 p 008 p 083 930—063—083—184—505—278—008—109—589—269 505—008—109—930—063—269—278—083—184—589 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 505 008 109 930 269 063 278 589 184 083 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 008 063 083 109 184 269 278 505 589 930 008—063—183—109—184—269—278—505—589—930 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.1 概述 10.5 归并排序 10.6 基数排序 10.7 各种内部排序方法的比较 各种排序方法的比较 对排序算法应该从以下几个方面综合考虑： ⑴时间复杂性； ⑵空间复杂性； ⑶稳定性； ⑷算法简单性； ⑸待排序记录个数n的大小； ⑹记录本身信息量的大小； ⑺关键码的分布情况。 排序方法 最好时间 平均时间 最坏时间 辅助空间 稳定性 直接插入排序 O(n) O(n2) O(n2) O(1) 稳定 希尔排序 O(n1.3) O(1) 不稳定 直接选择排序 O(n2) O(n2) O(n2) O(1) 稳定 堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定 冒泡排序 O(n) O(n2) O(n2) O(1) 稳定 快速排序 O(nlog2n) O(nlog2n) O(n2) O(log2n) 不稳定 归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定 基数排序 O(mn) O(mn) O(mn) O(n) 稳定 各种排序算法的性能比较 本章小结 排序的基本概念 排序的基本概念 关键字、初始关键字排列 关键字比较次数、数据移动次数 稳定性 附加存储 插入排序 直接插入排序、折半插入排序的过程 直接插入排序和折半插入排序的算法 排序的性能分析 当待排序的关键字序列已经基本有序时，用直接插入排序最快 选择排序