【读书笔记】数据结构与算法之美 第3章 递归、排序、二分查找

《数据结构与算法之美》，王争 著

标签：数据结构、算法

第3章 递归、排序、二分查找

一、递归

作者在队列这个小节，介绍下面的内容：

• 什么是递归

• 递归需要满足的三个条件

• 如何编写递归代码

• 编写递归的难点

• 警惕递归代码出现堆栈溢出

• 警惕递归代码的重复计算问题

• 将递归代码改写为非递归代码

• 递归产生堆栈溢出的原因

• 什么样的递归代码可以改写为尾递归

• 尾递归真的可以避免堆栈溢出吗

点评：递归部分，作者从应用的角度介绍了一些经典数据结构或算法教科书没有介绍的东西，可惜作者在这里举例的代码都是很简单的数值问题，这对数据结构中使用递归没有什么帮助，因为非数值问题的递归算法比数值问题的递归算法要难得多。

 二、排序

作者在排序这个小节，介绍下面的内容：

• 排序算法基础：从哪几个方面分析排序算法？

•        最好时间复杂度、最坏时间复杂度和平均时间复杂度

•        时间复杂度的系数、常数和低阶

•        比较次数和移动（交换）次数

•        排序算法的内存消耗：原地排序算法和非原地排序算法

•        排序算法的稳定性

• O(n2)排序：冒泡排序、插入排序、选择排序

• O(nlogn)排序：归并排序、快速排序

• O(n)排序：桶排序、计数排序和基数排序

• 排序优化：如何实现一个高性能的通用的排序函数

点评：排序部分，选的排序算法都是教材中经典常见的，这一节，特别的地方有两个，一是分析排序算法的性能这里更加直接。二是作者在文中指出“对于排序算法，除学习算法原理、代码实现之外，更重要的是学习每个算法的特点”，所以作者在这一节中穿插了一些小问题，比一般教材中格式化式的介绍排序算法更加有意思一些。如为什么插入排序比冒泡排序更受欢迎；如何在O(n)的时间复杂度内查找一个无序数组中的第K大元素；如何根据年龄给100万用户排序？如何实现一个高性能的通用的排序函数？

 三、二分查找

作者在二分查找这个小节，介绍下面的内容：

• 二分查找

• 二分查找的变体问题

 点评：二分查找部分，作者从更加应用的角度来介绍，和经典教材完全不同。

二分查找应用场景的局限性；二分查找是最省内存的方式实现快速查找功能；二分查找的变体问题（这个小节很有特色，值得推荐，不剧透了）