07 2009 檔案
摘要: 希爾排序實際上是一種分組插入排序，它的執行時間依賴于增量序列，而且是不穩定的。其基本思想是：先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然后，取第二個增量d2
閱讀全文
摘要: 歸并算法的核心操作就是將一維數組中前后相鄰的兩個兩個有序序列合并成一個有序序列。合并算法也可以采用遞歸算法來實現，形式上較為簡單,但實用性很差。合并算法的合并次數是一個非常重要的量,根據計算當數組中有3到4個元素時,合并次數是2次,當有5到8個元素時,合并次數是3次,當有9到16個元素時,合并次數是4次，按照這一規律,當有N個子序列時可以推斷出合并的次數是X(2 >=N,符合此條件的最小那個X)。
閱讀全文
摘要: 異步IO中也有高效低效之分，但主要還是要看具體的應用到底需要什么樣機制。比如大家熟知的select就是個非常通用且跨平臺的方法，由于select中需要把大量的時間花在維護IO句柄上，導致其效率大打折扣，一般來說，對于小并發的異步IO操作，比如普通的客戶端或者是小并發量的服務器，它的效率可能也足夠了。關于select的效率問題其實從各平臺上對于FD_SETSIZE的定義就能看出一些來，在windows平臺上，FD_SETSIZE是64，在Linux平臺上是1024，也就是說，對于平臺提供商來說也不指望他們提供的select能給你多大的并發吞吐能力。
閱讀全文
摘要: 所謂的同步和異步，在這里指的是應用程序和內核之間的交互方式。如果應用程序不需要等待內核的回應，那么它就是異步的。如果應用程序提交完IO請求后，需要等待“回執”，那么它就是同步的。而阻塞和非阻塞，指的是應用程序是否等待IO操作的完成。如果應用程序必須等到IO操作實際完成以后再執行下面的操作，那么它是阻塞的。反之，如果不等待IO操作的完成就開始執行其它操作，那么它是非阻塞的。
閱讀全文
摘要: 在當前無序區R[1..H]中任取一個數據元素作為比較的"基準"(不妨記為X)，用此基準將當前無序區劃分為左右兩個較小的無序區：R[1..I-1]和R[I+1..H]，且左邊的無序子區中數據元素均小于等于基準元素，右邊的無序子區中數據元素均大于等于基準元素，而基準X則位于最終排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，當R[1..I-1]和R[I+1..H]均非空時，分別對它們進行上述的劃分過程，直至所有無序子區中的數據元素均已排序為止。
閱讀全文
摘要: 兩兩比較待排序數據元素的大小，發現兩個數據元素的次序相反時即進行交換，直到沒有反序的數據元素為止。
閱讀全文
摘要: 每次將一個待排序的數據元素，插入到前面已經排好序的數列中的適當位置，使數列依然有序；直到待排序數據元素全部插入完為止。
閱讀全文
摘要: 每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最后，直到全部待排序的數據元素排完。
閱讀全文