《數(shù)據(jù)結(jié)構(gòu)與算法之美》，王爭 著

標簽：數(shù)據(jù)結(jié)構(gòu)、算法

第3章 遞歸、排序、二分查找

一、遞歸

作者在隊列這個小節(jié)，介紹下面的內(nèi)容：

• 什么是遞歸

• 遞歸需要滿足的三個條件

• 如何編寫遞歸代碼

• 編寫遞歸的難點

• 警惕遞歸代碼出現(xiàn)堆棧溢出

• 警惕遞歸代碼的重復(fù)計算問題

• 將遞歸代碼改寫為非遞歸代碼

• 遞歸產(chǎn)生堆棧溢出的原因

• 什么樣的遞歸代碼可以改寫為尾遞歸

• 尾遞歸真的可以避免堆棧溢出嗎

點評：遞歸部分，作者從應(yīng)用的角度介紹了一些經(jīng)典數(shù)據(jù)結(jié)構(gòu)或算法教科書沒有介紹的東西，可惜作者在這里舉例的代碼都是很簡單的數(shù)值問題，這對數(shù)據(jù)結(jié)構(gòu)中使用遞歸沒有什么幫助，因為非數(shù)值問題的遞歸算法比數(shù)值問題的遞歸算法要難得多。

?二、排序

作者在排序這個小節(jié)，介紹下面的內(nèi)容：

• 排序算法基礎(chǔ)：從哪幾個方面分析排序算法？

• ?????? 最好時間復(fù)雜度、最壞時間復(fù)雜度和平均時間復(fù)雜度

• ?????? 時間復(fù)雜度的系數(shù)、常數(shù)和低階

• ?????? 比較次數(shù)和移動（交換）次數(shù)

• ?????? 排序算法的內(nèi)存消耗：原地排序算法和非原地排序算法

• ?????? 排序算法的穩(wěn)定性

• O(n2)排序：冒泡排序、插入排序、選擇排序

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

• O(n)排序：桶排序、計數(shù)排序和基數(shù)排序

• 排序優(yōu)化：如何實現(xiàn)一個高性能的通用的排序函數(shù)

點評：排序部分，選的排序算法都是教材中經(jīng)典常見的，這一節(jié)，特別的地方有兩個，一是分析排序算法的性能這里更加直接。二是作者在文中指出“對于排序算法，除學習算法原理、代碼實現(xiàn)之外，更重要的是學習每個算法的特點”，所以作者在這一節(jié)中穿插了一些小問題，比一般教材中格式化式的介紹排序算法更加有意思一些。如為什么插入排序比冒泡排序更受歡迎；如何在O(n)的時間復(fù)雜度內(nèi)查找一個無序數(shù)組中的第K大元素；如何根據(jù)年齡給100萬用戶排序？如何實現(xiàn)一個高性能的通用的排序函數(shù)？

?三、二分查找

作者在二分查找這個小節(jié)，介紹下面的內(nèi)容：

• 二分查找

• 二分查找的變體問題

?點評：二分查找部分，作者從更加應(yīng)用的角度來介紹，和經(jīng)典教材完全不同。

二分查找應(yīng)用場景的局限性；二分查找是最省內(nèi)存的方式實現(xiàn)快速查找功能；二分查找的變體問題（這個小節(jié)很有特色，值得推薦，不劇透了）

?

?