⚠
基于插入排序的，每一趟不一定有一个元素在其最终位置
插入排序
：直接插入、折半插入、希尔排序（不稳定）；
交换排序
：冒泡排序、快速排序；
选择排序
：简单选择、堆排序；
归并排序
、
基数排序
；
排序
简介
代码
直接插
入排序
最好
最坏
平均
空间
稳定性
适用于
O(n)
O(n*n)
O(n*n)
O(1)
稳定
顺、链
⚠
分为
比较和移动
两种操作
⚠
最后一趟开始之前，所有元素都不一定在其最终位置上
折半插
入排序
最好
最坏
平均
空间
稳定性
适用于
O(nlogn)
O(n*n)
O(n*n)
O(1)
稳定
顺序表
⚠
与直接插入排序相比，只是减少了比较次数，移动次数不
变
希尔排
序
最好
最坏
平均
空间
稳定性
适用于
O(n)
O(n*n)
O(n1.3)
O(1)
稳定不
顺序表
⚠
每次的步长为dk，除了步长变化之外，其他类似于直接插
入排序，要类比记忆
⚠
关键：dk的选取
冒泡排
序
最好
最坏
平均
空间
稳定性
适用于
O(n)
O(n*n)
O(n*n)
O(1)
稳定
顺、链
⚠
每次都会有一个元素在其最终位置上
快速排
序
最好
最坏
平均
空间
稳定性
适用于
O(logn)
O(n)
O(nlogn)
O(n)
O(logn)
不稳定
顺序表
•
⚠
平均性能最优的算法、每次都把基准元素放在其最终位
置上
•
关键：
⚠
划分操作
•
⚠
要排序的序列基本有序的时候最不利于发挥其长处，提
高效率的算法是：1）当规模较少时，不再递归调用快速排
序，而是直接插入排序；2）尽量选取可以将数据中分的枢
轴元素；
•
每次的枢轴都把表等分为长度相近的两个子表时，速度最
块；当本表已经有序或逆序时，速度最慢；
•
递归次数与各元素的初始排列有关，如果每次划分后分区
平衡，递归次数少；如果不平衡，递归次数多。递归次数
与处理顺序没有关系。
•
如果对算法不理解，可以找个例子手动模拟一下就明白了
•
简单选
择排序
最好
最坏
平均
空间
稳定性
适用于
O(n*n)
O(n*n)
O(n*n)
O(1)
不稳定
顺、链
•
⚠
每一次都有一个元素在其最终位置上
（类似于冒泡）
•
移动次数很少，最好是有序；但是比较次数与初始状态无
关
•
堆排序
需要注
意
⚠
最好
最坏
平均
空间
稳定性
适用于
O(nlogn)
O(nlogn)
O(nlogn)
O(1)
不稳定
顺序表
大根堆：最大元素为根节点；小根堆：最小元素为根节
点
•
关键在与建立大根堆，第n个节点的双亲是第」n/2」个
节点
•
⚠
每一个根节点都大于其左右字节点
•
大根堆构造：自下往上调整，
•
大根堆删除：删除堆顶元素时，将堆顶元素与最后一个元素交
换，此时结点向下调整；
•
大根堆插入：插入在最后一个结点，然后向上调整。
•
归并排
序
最好
最坏
平均
空间
稳定性
适用于
O(nlogn)
O(nlogn)
O(nlogn)
O(n)
稳定
⚠
每一趟不一定有一个元素在最终位置上
⚠
比较次数与初始状态无关
基数排
序
分为MSD最高为排序和LSD最低位排序
•
按照低位》高位的次序排序，必须要稳定
•
数据结构-第七章：排序
2019年10月21日 星期一
16:25
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
补充：堆排序
1:⾃上⽽下调整为⼤根堆，从n/2下取整开始，然后i- - ；
2:⼤根堆插⼊操作：插⼊在尾部，然后逐次调整对应的根结点；
3、删除元素时，将该元素与最后⼀个元素交换，破坏堆堆性质；
!
插⼊排序：直接插⼊、折半插⼊、希尔排序
"
交换排序：冒泡排序、快速排序
#
选择排序：简单选择排序、堆排序
$
归并排序、基数排序
补充：外部排序
通常采⽤归并排序
版权所有，侵权必究，举
报请联系hzyjob@qq.com
版权所有，侵权必究，举
报请联系hzyjob@qq.com
版权所有，侵权必究，举报请联系hzyjob@qq.com
版权所有，侵权必究，举报
请联系hzyjob@qq.com
