哈希結構      摘要: 哈希結構

C++博客 Alex-Lee 2009-10-21

哈希結構在處理大量數據時具有很好的優勢，在插入，查詢，刪除等操作上具有常量的時間復雜度O(1)。使用范圍是數據集具有自然數上的關鍵字域（不是自然數也需要能夠轉為自然數域），通過哈希函數將關鍵字映射到尋址數組的槽。由于關鍵字域U[0...n]與尋址數組[0...m]中，總是n>m，也就是說，總有多個關鍵字對應一個槽。這個碰撞就需要通過一些方法改變。可以通過拉鏈法（鏈表法）和開放地址法。對于拉鏈法中，鏈表不能太長，否則影響速度，最好控制在10個元素之內，這樣就要去尋址數組長度m>= n/10，這樣就會多消耗些空間。為了讓每個鏈表長度基本一致，就需要  閱讀全文

快速排序算法、計數排序算法      摘要: 快速排序算法、計數排序算法

C++博客 Alex-Lee 2009-10-20

快速排序是分治算法，將數組分為幾部分，在各部分內完成排序，遞歸排序。算法時間復雜度O(nlgn)。這是比較排序算法中速度最快的一個算法了。計數排序、基數排序、桶排序算法是非比較排序算法，他們的算法復雜度是O(n)。快速排序算法在選取支點上要有技巧，最好能達到隨即要求。
  閱讀全文

優先級隊列      摘要: 優先級隊列

C++博客 Alex-Lee 2009-10-18

上篇隨筆談到了堆結構的一個應用就是堆排序算法，雖然堆排序算法性能不錯，但是比起快速排序算法還是有些差距。但是堆結構的另外一個應該就比較廣泛了，就是優先級隊列。
優先級隊列有3中操作：插入(O(lgn))，最大最小值(O(1)),刪去最大最小值(O(lgn))。其算法性能很好，在優先級調度作業上應用比較廣泛。基于優先級的調度算法中，基于堆結構的實現算法是一個比較好選擇。在事件驅動的仿真器中也有應用。  閱讀全文

堆排序算法      摘要: 堆排序算法

---------- C++博客 Alex-Lee 2009-10-15

（二叉）堆結構是一種數組對象，它可以被視為一顆完全二叉樹。算法時間復雜度O(nlgn)，具有插入排序和合并排序的優點。堆結構滿足堆性質：對除根以外的每個節點i,滿足A[PARENT(i)] >= A[i]。

堆排序算法實現有三個部分完成：
1，保持堆性質函數heap_ify;
2,構建堆函數build_heap;
3,堆排序函數 heap_sort;
另外，在優先級隊列中有extract-max 過程和insert過程，在作業隊列中常用，比如消息隊列。這部分在優先級排序中說明。
  閱讀全文