数据结构-排序
2020-06-01 17:07:28 0 举报AI智能生成
自己考研期间画的数据结构框架图，参考了大话数据结构和王道的数据结构的书，希望可以帮到大家
作者其他创作
大纲/内容
排序
基本概念
稳定性
衡量标准
时间复杂度、空间复杂度
内部排序
插入排序
直接插入
不断在后面找数字往有序列表插入
折半插入
希尔排序
以数组长度/2为增量，不断比较交换
从0开始数，刚好分配就最好（如2），不然就一截一截比（如1）
从0开始数，刚好分配就最好（如2），不然就一截一截比（如1）
交换排序
冒泡排序
从前到后，逆序交换，同序不换
快速排序
拿着标准右边走，走到不顺停下来，比标准小变左边，
比标准大变右边，那边变那边走，
比标准大变右边，那边变那边走，
选择排序
简单选择排序
每次找最小(大)的数放到队头
堆排序
构造初始堆
数组层次排序变成树，最后一个非叶子结点开始调整，
左右父找大与父交换，从右往左循环地进行，
左右父找大与父交换，从右往左循环地进行，
排序过程
用筛选法思想建堆必须从第n/2个元素开始进行筛选
一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，
则利用筛选法建立的初始小顶堆为_。
则利用筛选法建立的初始小顶堆为_。
小根堆满足条件
L(i)<=L(2i)&&L(i)<=L(2i+1)
大根堆满足条件
L(i)>=L(2i)&&L(i)>=L(2i+1)
归并排序
两两和合一向前走，多余的元素放一边，越往前越多字
基数排序
个位开始竖着排，后面的序列以前面序列为开始，序列书写从上往下写
内部排序比较
时间复杂度
与序列初始状态无关
简单插入，归并排序
简单选择，直接插入，冒泡平均为o(n^2)，
但直接插入和冒泡最好情况有o(n)
但直接插入和冒泡最好情况有o(n)
堆排序可以在线性时间内建堆，在o(nlogn)内完成排序
快速排序最坏o(n^2)，平均性能o(nlogn)
归并排序，最好最坏都是o(nlogn)
空间复杂度
常数个
简单选择排序，插入排序，冒泡排序，希尔排序，堆排序
快速排序要实现递归，平均大小要o(logn)，最坏要o(n)
二路归并需要较多的空间用于元素复制，o(n)
稳定性
稳定
插入，冒泡，归并，基数
不稳定
简单选择，快排，希尔，堆排
应用
n比较少，选用直接插入和简单选择
直接插入
简单选择：当记录本身信息大用（移动少）
n比较大，选择o(nlogn)的算法
快排：平均时间快
堆排：辅佐空间少
归并：稳定
n很大，记录关键字位数较少，且可以分拆时
基数排序
年数排序
元素初始状态基本有序
直接插入或冒泡
记录信息量较大时
采用链表存储，减少移动
复杂度及稳定性比较
外部排序
多路归并排序
1<= i <n/2
0 条评论
下一页
