20220527数据结构绿皮书读书笔记
8 排序
各种排序算法来咯
插入排序、选择排序、希尔排序、快排、堆排
8.1 简介
和搜索一样,排序的主流算法也都是主要基于key的比较
8.2 插入排序
两个不是基于index的基本操作
retrieval by key,通过key查找record
insertion by key,通过key插入record
注意插入并不是唯一的,如果key相同,其中一个可能靠后
第一个操作就是搜索,没什么好说的,可以利用各种已知的搜索操作
第二个操作的关键是找到需要插入的位置,这个位置一定处于有序和无序的界限之前
学习个好的变量命名,position=first_unsorted
对于基于数组实现的列表,需要移动后面所有元素后再插入,对于基于链表实现的列表直接修改指针即可
8.3 选择排序
从所有的中找出极值,放到有序范围内的对应端点位置,每轮仅需要一次插入,移动次数相比插入排序大大降低
8.4 希尔排序
也叫增量递减排序
结合了前两种排序的优点,每轮遍历进行多次比较和交换,当比较的跨度减小到1的那次遍历结束,整个排序算法完成
增量的跨度从最大值开始迭代increment = increment/3 + 1
增量的选择并没有什么人能证明一个好的方式,唯一的限制就是最后要是1(待查证,不知道如今有没有理论突破)
8.5 下界分析
结论,比较次数最少为 lg(n!)向上取整,最坏情况下至少也是lg(n!)
套路还是画比较树,然后计算树的高度,显然和树有关的情况下都是大概率结果都是lg
8.6 分治排序
递归切分,切到最后大小是2分出结果
8.7 链表的归并排序
归并排序在外排中非常有用,在低速磁盘中排序效率比较好
二路归并是练习
多路归并需要用到多叉树
8.8 快排
核心思想,pivot入中位,让pivot找到合适的位置。然后分支左右两侧递归这个过程
8.9 堆排
完全二叉树或者二叉树,因节点位置和2的幂次有固定的公式关系,因此可以通过数组直接存储,通过公式运算还原实际的节点位置
这里注意区分物理实现和逻辑位置的关系,物理上可能是数组的第k个,但逻辑上并不一定是树上的k
满足固定顺序的二叉树,就可以称作堆
下周继续第九章
mark 目前是379页 ,pdf是396页
0 Comments