Algorithms

算法，數(shù)據(jù)結(jié)構(gòu)相關(guān)的東東

摘要: 前面寫了好些排序，紅黑樹，B 樹算法的文章，還剩下查找這一大塊沒有寫，查找相關(guān)的算法代碼已經(jīng)實現(xiàn)，但是卻沒有寫查找算法日志的閑情了，只好先在這里放出代碼來，以后有空有閑情再補上吧。

算法代碼 Google 倉庫：點擊這里
閱讀全文

posted @ 2011-04-10 12:11 羅朝輝閱讀(901) | 評論 (0) 編輯

【樹】樹算法之紅黑樹

摘要: 紅黑樹本質(zhì)是二叉查找樹的一種，它的性能高于普通的二叉查找樹，即使是在最壞的情況下也能保證時間復(fù)雜度為O(lgn)。紅黑樹在每個結(jié)點上增加一個存儲位表示結(jié)點的顏色（或紅或黑，故稱紅黑樹）。通過對任何一條從根到葉子的路徑上各個結(jié)點著色方式的限制，紅黑樹可以保證沒有一條路徑會比其他路徑長出兩倍，因而是接近平衡的。

紅黑樹的每個結(jié)點至少包含五個域：color，key，left，right 和 parent（一般我們都會在結(jié)點中存儲額外的數(shù)據(jù) data，但前面的五個域是必不可少的），如果某個結(jié)點沒有子結(jié)點或者結(jié)節(jié)點，則將相應(yīng)的指針設(shè)置為空值（NIL，注意不是 NULL，NIL是一個特定的空結(jié)點對象，類似于Obj-C 中 Nil對象）。我們將這些 NIL 當(dāng)作葉子結(jié)點（在實際處理過程中，往往將最底層的孩子結(jié)點和根結(jié)點的父親都指向同一個 NIL 結(jié)點，以便于處理紅黑樹代碼中的邊界條件），而將其它結(jié)點當(dāng)作內(nèi)結(jié)點。
閱讀全文

posted @ 2011-04-03 11:21 羅朝輝閱讀(1898) | 評論 (0) 編輯

【樹】樹算法之 B 樹

摘要: B 樹是一種被設(shè)計成專門存儲在磁盤上的平衡查找樹。因為磁盤的操作速度要大大慢于隨機存取存儲器，所以在分析B 樹的性能時，不僅要看動態(tài)集合操作花了多少計算時間，還要看執(zhí)行了多少次磁盤存儲操作。 B 樹與紅黑樹（下一篇介紹）類似，但在降低磁盤I/O 操作次數(shù)方面要更好一些。許多數(shù)據(jù)庫系統(tǒng)就使用 B 樹或 B 樹的變形來存儲信息，想象一下一棵每個節(jié)點包含 1001 個 key 的高度為 2 的 B 樹能容納多少數(shù)據(jù)啊，而在內(nèi)存中我們只存儲了一個節(jié)點，在需要的時候再從磁盤中讀取所需的節(jié)點。

閱讀全文

posted @ 2011-03-21 23:10 羅朝輝閱讀(4185) | 評論 (5) 編輯

【排序】排序算法之分配排序

摘要: 前面講了插入排序，交換排序，選擇排序，歸并排序，下面接著來講桶排序，基數(shù)排序。

桶排序和基數(shù)排序均屬于分配排序。分配排序的基本思想：排序過程無須比較關(guān)鍵字，而是通過用額外的空間來"分配"和"收集"來實現(xiàn)排序，它們的時間復(fù)雜度可達到線性階：O(n)。簡言之就是：用空間換時間，所以性能與基于比較的排序才有數(shù)量級的提高！閱讀全文

posted @ 2011-03-18 23:47 羅朝輝閱讀(899) | 評論 (0) 編輯

【排序】排序算法之歸并排序

摘要: 前面講了插入排序，交換排序，選擇排序，下面接著來講歸并排序。

歸并排序(Merge Sort)是利用"歸并"技術(shù)來進行排序。歸并是指將若干個已排序的子文件合并成一個有序的文件。

其基本思想為：設(shè)兩個有序的子序列(相當(dāng)于輸入序列)放在同一序列中相鄰的位置上：array[low..m]，array[m + 1..high]，先將它們合并到一個局部的暫存序列 temp (相當(dāng)于輸出序列)中，待合并完成后將 temp 復(fù)制回 array[low..high]中，從而完成排序。
閱讀全文

posted @ 2011-03-13 15:19 羅朝輝閱讀(8237) | 評論 (0) 編輯

【排序】排序算法之選擇排序

摘要: 前面講了插入，交換排序，下面接著來講選擇排序。閱讀全文

posted @ 2011-03-09 21:37 羅朝輝閱讀(1477) | 評論 (0) 編輯

【排序】排序算法之交換排序

摘要: 前面我們講了插入排序，下面接著來講交換排序。

交換排序的基本思想是：兩兩比較待排序記錄的關(guān)鍵字，發(fā)現(xiàn)兩個記錄的次序相反時即進行交換，直到?jīng)]有反序的記錄為止。應(yīng)用交換排序基本思想的主要排序方法有：冒泡排序和快速排序。
閱讀全文

posted @ 2011-03-04 23:47 羅朝輝閱讀(1613) | 評論 (0) 編輯

【排序】排序算法之插入排序

摘要: 排序是數(shù)據(jù)處理中經(jīng)常使用的一種重要運算，在計算機及其應(yīng)用系統(tǒng)中，花費在排序上的時間在系統(tǒng)運行時間中占有很大比重，其重要性無需多言。下文將介紹常用的如下排序方法，對它們進行簡單的分析和比較，并提供 C/C++ 語言實現(xiàn)。

所謂排序，就是要將一堆記錄，使之按關(guān)鍵字遞增(或遞減)次序排列起來。根據(jù)排序所采用的策略，可以分為如上五種：

1、插入排序（直接插入排序、希爾排序）；
2、交換排序（冒泡排序、快速排序）；
3、選擇排序（直接選擇排序、堆排序）；
4、歸并排序；
5、桶排序（桶排序，基數(shù)排序）；

其中插入排序、交換排序、選擇排序、選擇排序、歸并排序都是基于關(guān)鍵字比較的排序，比較排序的平均時間復(fù)雜度好不過 O(nlogn)。
而桶排序是基于映射的排序，其平均時間復(fù)雜度可達到 O(n)，但桶排序需要額外的空間來存儲經(jīng)過映射的記錄。

通常在待排序記錄較多的時候，基于映射的排序 O(n) 比基于比較的排序 O(nlogn) 的效率要高得多，這很好理解：用空間換時間。（查找算法其實也是如閱讀全文

posted @ 2011-03-03 22:07 羅朝輝閱讀(1971) | 評論 (0) 編輯

【Android】Android 上實現(xiàn)水波特效二--優(yōu)化

摘要: 在上一篇文章《Android 上實現(xiàn)水波特效》中對水波波幅的計算是針對每一個像素的，效率比較低，尤其是在手機上運行，相當(dāng)緩慢。我們可以利用線性插值進行優(yōu)化，這樣可以將計算減少一半（MeshSize 為 2）或減少四分之三（MeshSize 為 4），效率得以大大提升，即使是在手機上也能較為流暢地運行。
閱讀全文

posted @ 2010-09-28 11:49 羅朝輝閱讀(1418) | 評論 (0) 編輯

【Android】Android 上實現(xiàn)水波特效

摘要: 本文中的水波特效算法部分整理自 GameRes 上的資料，原作者 Imagic。我只是在學(xué)習(xí) Android 的過程中，想到這個特效，然后就在Android 上實現(xiàn)出來，并在源算法的基礎(chǔ)上添加了雨滴滴落特效，以及劃過水面時的漣漪特效。該程序在模擬器和真機上運行速度都較慢，需要進一步優(yōu)化或使用 JNI 實現(xiàn)，如果你想到好的優(yōu)化算法，請聯(lián)系我：kesalin@gmail.com。閱讀全文

posted @ 2010-09-01 13:19 羅朝輝閱讀(3692) | 評論 (0) 編輯

羅朝輝（飄飄白云）

常用鏈接

留言簿(18)

隨筆分類(105)

隨筆檔案(85)

3D圖形學(xué)

window相關(guān)

那些牛人

綜合型

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

Algorithms