当前课程知识点：数据结构 > 第9章 内部排序 > 9.8 排序方法总结 > 9.8 排序方法总结
同学们大家好
我是云南大学信息学院教师孔兵
这节课我们对各种排序方法进行一个总结比较
先观察一个表
表中对各种排序方法的平均时间
最坏情况和辅助存储的需求量做了一个总结
其中简单排序是除了希尔排序以外的所有插入排序
起泡排序和选择排序
简单排序的平均时间和最坏情况的时间复杂度都是O(n2)
辅助存储空间主要是交换时作为中间变量，一般是常量
快速排序呢，平均时间是O(nlogn)
最坏情况下是O(n2)
那么需要的辅助存储空间是O(logn)
这个主要是递归过程中用到的
堆排序和归并排序平均时间和最快情况都是O(nlogn)
也就是说这两种方法呢
对于待排序序列的初始状况不敏感
堆排序需要的辅助空间为常量
归并排序需要一个和原序列等长的辅助空间
作为归并结果暂存的空间
从基数排序的过程来看
待排序序列的初始状况对排序时间没有任何影响
基数排序没有平均时间和最坏情况的说法
基数排序需要的辅助空间是指针数组的空间rd
下面给出几条结论：
就平均性能而言，快速排序最佳
但快速排序在最坏情况下的时间性能不如堆排序和归并排序
而后两者比较的结果是，归并排序是稳定的
在n较大时，归并排序所需时间较堆排序省
但需要辅助存储较多
“简单排序”方法
序列“基本有序”或n值较小时
它是最佳的排序方法，因此常将它和其它排序方法
如归并排序、快速排序等结合在一起使用
归并排序和快速排序都是采用递归自上而下逐渐减小问题规模
当规模为1的时候递归返回
可以考虑和简单排序方法结合
当缩减的问题规模较小时，不再继续分解
而是通过调理简单排序方法对小规模的序列进行排序
随后返回，这样可以发挥各自的长处
一般来说
基数排序中每位关键字的取值和待排序记录的个数比较都非常小
所以，基数排序时间复杂度可写成O(dn)
因此，它较适合n值很大而关键字较小的情况
基数排序和所有时间复杂度为O(n2)的简单排序方法是稳定的
快速排序、堆排序和希尔排序等时间性能较好的方法是不稳定的
好，同学们，数据结构课程到这里就全部结束了
谢谢大家！
-1.算法概念导入
-2.数据结构课程介绍
-0.1变量、类型和表达式
-0.2 函数
--0.2 函数
-0.3 指针和单链表
-0.4 数组、指向函数的指针
-1.1什么是数据结构
--测试题
-1.2基本概念和术语
--测试题
-1.3数据结构的描述
--测试题
-1.4抽象数据类型的定义和实现
--测试题
-1.5算法和算法分析概念
--测试题
-1.6算法分析示例
--测试题
-2.1 线性表的类型定义
--测试题
-2.2线性表的顺序表示和实现
--测试题
-2.3 线性链表
--2.3 线性链表
--测试题
-2.4 静态链表
--2.4 静态链表
--测试题
-2.5 循环链表和双向链表
--测试题
-3.1 栈
--3.1栈
--测试题
-3.2 栈的实现
--3.2 栈的实现
--测试题
-3.3 栈的应用
--3.3 栈的应用
-3.4 栈与递归的实现
--测试题
-3.5 队列和链队列
--测试题
-3.6 循环队列
--3.6 循环队列
--测试题
-4.1 串
--4.1 串
--测试题
-5.1 数组定义和表示
--测试题
-5.2矩阵的压缩存储
--测试题
-6.1 树的定义和基本术语
-6.2 二叉树和二叉树的性质
--测试题
-6.3 二叉树的存储结构
--测试题
-6.4 遍历二叉树
--测试题
-6.5 线索二叉树
--测试题
-6.6 树的存储
--6.6树的存储
-6.7 树的转换和遍历
--测试题
-6.8 赫夫曼树
--6.8 赫夫曼树
-6.9 赫夫曼编码
--测试题
-7.1 图的定义和术语
--测试题
-7.2 图的存储结构
--测试题
-7.3 图的遍历
--测试题
-7.4 最小生成树
--测试题
-7.5 有向无环图
--测试题
-7.6 最短路径
--测试题
-8.1 查找基本概念和顺序查找
--测试题
-8.2 有序表的查找
--测试题
-8.3 二叉排序树
--测试题
-8.4 平衡二叉树
--测试题
-8.5 哈希表
--测试题
-9.1插入排序
--测试题
-9.2 希尔排序
--9.2 希尔排序
--测试题
-9.3 快速排序
--9.3 快速排序
--测试题
-9.4 选择排序
--9.4 选择排序
--测试题
-9.5 堆排序
--9.5 堆排序
--测试题
-9.6 归并排序
--9.6 归并排序
--测试题
-9.7 基数排序
--9.7 基数排序
--测试题
-9.8 排序方法总结
