哈希結(jié)構(gòu)      摘要: 哈希結(jié)構(gòu)

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

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

快速排序算法、計數(shù)排序算法      摘要: 快速排序算法、計數(shù)排序算法

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

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

優(yōu)先級隊列      摘要: 優(yōu)先級隊列

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

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

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

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

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

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