摘要:回顧一下我們學過的選擇排序,在無序區找到一個最?。ù螅┑脑匦枰容^n 1次,找到第二小的元素需要比較n 2次,直到最后比較1次。而堆排序因為二叉堆的性質,堆頂就是最大的元素,查找次數只有一次,但是將無序轉成有序中間還需要一個預處理過程:構造堆有序。 堆有序并不代表數組有序,堆有序是滿足二叉堆性質的 閱讀全文
posted @ 2019-12-19 15:41 我脫下短袖 閱讀(359) 評論(0) 推薦(3) 編輯
摘要:希爾排序屬性 上篇寫的直接插入排序算法時間復雜度是O(n^2),如果要令此排序算法的時間復雜度要低于O(n^2),必須是“遠距離的元素交換”使得這組元素能提高有序的程度,然后進行直接插入排序的時候可以減少交換的工作量。 那通過什么減少交換的工作量呢?希爾排序可以解決這個問題。 希爾排序在做直接插入排 閱讀全文
posted @ 2019-12-17 13:04 我脫下短袖 閱讀(358) 評論(0) 推薦(1) 編輯
摘要:學過上一篇文章的計數排序之后,特別是歸約化分治處理的計數排序(適用于較離散的非負整數序列)。計數排序的局限比較多,在排序之前需要解決負數和小數的問題,而桶排序不需要考慮這些。 桶排序和計數排序一樣,不受O(nlogn)時間復雜度下限的影響,它將待排序序列通過遍歷方式分到有限數量的桶中,然后每個桶被單 閱讀全文
posted @ 2020-01-27 14:46 我脫下短袖 閱讀(24) 評論(0) 推薦(0) 編輯
摘要:我們知道快速排序的時間復雜度期望值是O(nlogn),其中O(logn)是利用了二分法進行遠距離比較和交換元素的位置。如果不去做比較交換計算,有沒有可能有一種算法,它的時間復雜度期望值能降低到O(n)線性時間呢? 我們可以有這樣的思路,對于任何一個待排序數組的元素x,如果知道了待排序數組中有多少個元 閱讀全文
posted @ 2020-01-27 14:44 我脫下短袖 閱讀(21) 評論(0) 推薦(0) 編輯
摘要:歸并排序的歸并這兩個字和遞歸沒有關系,歸并是將兩個有序的數組歸并成一個更大的有序數組,但整個排序算法是有可能跟遞歸有關系的。因為歸并排序算法可以按照遞歸方式去解決,也可以按照迭代方式去解決。 遞歸方式是自頂向下的歸并排序,迭代方式是自底向上的歸并排序。這兩種歸并排序雖然實現方式不同,但是都是調用了核 閱讀全文
posted @ 2020-01-27 14:40 我脫下短袖 閱讀(27) 評論(0) 推薦(0) 編輯
摘要:基數排序和計數排序一樣無需進行比較和交換,和桶排序一樣利用分布和收集兩種基本操作進行排序?;鶖蹬判蚴前衙恳粋€元素拆成多個關鍵字,一個關鍵字可以在每一個元素上同等的位置進行計數排序,一個元素拆成多個關鍵字可以看作是要進行幾輪分桶,以一個元素最長的長度為準。 基數排序可以看成多(單)關鍵字的排序,可以想 閱讀全文
posted @ 2020-01-27 11:12 我脫下短袖 閱讀(44) 評論(0) 推薦(0) 編輯
摘要:二分搜索樹又名有序二叉查找樹,它有一個特點是左子樹的節點值要小于父節點值,右子樹的節點值要大于父節點值?;谶@樣的特點,我們在查找某個節點的時候,可以采取二分查找的思想快速找到這個節點,時間復雜度期望值是為O(log n),但是它有最壞的的情況下。 例如,輸入數組[9,7,5,3,1],如果要滿足二 閱讀全文
posted @ 2020-01-27 10:57 我脫下短袖 閱讀(55) 評論(0) 推薦(0) 編輯
摘要:我們回憶一下AVL樹,它在插入和刪除節點時,總要保證任意節點左右子樹的高度差不超過1。正是因為有這樣的限制,插入一個節點和刪除一個節點都有可能調整多個節點的不平衡狀態。頻繁的左旋轉和右旋轉操作一定會影響整個AVL樹的性能,除非是平衡與不平衡變化很少的情況下,否則AVL樹所帶來的搜索性能提升不足以彌補 閱讀全文
posted @ 2020-01-26 14:28 我脫下短袖 閱讀(52) 評論(0) 推薦(0) 編輯
摘要:學習過2 3樹之后就知道應怎樣去理解紅黑樹了,如果直接看「算法導論」里的紅黑樹的性質,是看不出所以然。我們也看看一顆二分搜索樹滿足紅黑的性質: 1.每個節點或是紅色的,或是黑色的; 2.根節點是黑色的; 3.每個葉子節點(NIL)是黑色的; 4.如果一個節點是紅色的,則它的兩個子節點都是黑色的; 5 閱讀全文
posted @ 2020-01-26 14:24 我脫下短袖 閱讀(56) 評論(0) 推薦(0) 編輯
摘要:畫了一系列樹的動畫,從二分搜索樹,到AVL樹,再到2 3樹,再到基于2 3樹的紅黑樹,都可以發現這些樹都跟二叉查找樹很像啊。 嘿嘿!二分搜索樹就是二叉查找樹;AVL樹也是一顆二分搜索樹,只多了高度差的限制;2 3樹雖滿足二分搜索樹的性質,但不是一顆二分搜索樹,2 3樹由2 節點和3 節點組成的,滿足 閱讀全文
posted @ 2020-01-26 14:16 我脫下短袖 閱讀(25) 評論(0) 推薦(0) 編輯
摘要:今天分享一個LeetCode題,題號是1038,標題是:從二分搜索樹到更大和數。 題目描述 給出二叉搜索樹的根節點,該二叉樹的節點值各不相同,修改二叉樹,使每個節點 node 的新值等于原樹中大于或等于 node.val 的值之和。 提醒一下,二叉搜索樹滿足下列約束條件: 1)節點的左子樹僅包含鍵小 閱讀全文
posted @ 2020-01-23 13:14 我脫下短袖 閱讀(219) 評論(1) 推薦(0) 編輯
摘要:創建與輸入數組相等長度的新數組,作為直接尋址表。兩數之和的期望是Target,將Target依次減輸入數組的元素,得到的值和直接尋址表比較,如果尋址表存在這個值則返回;如果不存在這個值則將輸入數組中的元素插入尋址表,再進行輸入數組中的下一個元素。 再進一步優化可以將輸入數組直接作為直接尋址表,控制對 閱讀全文
posted @ 2020-01-23 12:55 我脫下短袖 閱讀(344) 評論(2) 推薦(3) 編輯
ag二分彩