20220527数据结构绿皮书读书笔记

 

 

 

 

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
Leave a Reply