Skynet

發(fā)現(xiàn) 自己寫個(gè)小程序 - 文本存儲(chǔ)二叉結(jié)構(gòu)的hashMap。 那個(gè)費(fèi)勁！ 痛下決心 仔細(xì)學(xué)習(xí) 算法 。
（如果大家有興趣就跟我一起 - 《算法導(dǎo)論》，也望大家監(jiān)督我能每天拿出一小時(shí)和大家分享算法,算法代碼我會(huì)盡量使用 py 和 解決一些分析日志的應(yīng)用上靠 （其實(shí)，上面費(fèi)勁的 二叉hash 是為了分析日志中 - 希望能實(shí)現(xiàn) 多個(gè)大文件不需要合并就能根據(jù)某列排序輸出! 目前的解決辦法 find .. -exec cat {} \; | perl |sort 的笨方法 ）

1. 算法在計(jì)算中的作用 （筆記） :
   算法(algorithm):就是定義良好的計(jì)算過(guò)程，它取一個(gè)或一組作為輸出，并產(chǎn)生一個(gè)或一組自作為輸出。

一些函數(shù)運(yùn)行級(jí)別  # http://www.wolframalpha.com/ 函數(shù)都可在網(wǎng)站里運(yùn)行
這里 n=一億條數(shù)據(jù) :
log_2(n)     30
n^0.5        31622
n            10^9
n*log_2(n)   2.9^10
n^2          10^18
n^3          10^27
2^n          無(wú)窮
n!           10^362880


需要知道的復(fù)雜度 - 在某一個(gè)臨界點(diǎn)后 合并會(huì)別插入要快的
  插入排序  復(fù)雜度 n^2    http://www.wolframalpha.com/input/?i=n^2
  合并排序  復(fù)雜度 n*log_2(n)  http://www.wolframalpha.com/input/?i=n*log_2%28n%29+

網(wǎng)上的查找到的一些名稱：參考 http://www.51testing.com/?uid-130868-action-viewspace-itemid-66729
1.1穩(wěn)定排序  非穩(wěn)定排序 -
  穩(wěn)定排序是所有相等的數(shù)經(jīng)過(guò)某種排序方法后，仍能保持它們?cè)谂判蛑暗南鄬?duì)次序，。反之，就是非穩(wěn)定的排序。
1.2內(nèi)排序  外排序
  在排序過(guò)程中，所有需要排序的數(shù)都在內(nèi)存，并在內(nèi)存中調(diào)整它們的存儲(chǔ)順序，稱為內(nèi)排序； 在排序過(guò)程中，只有部分?jǐn)?shù)被調(diào)入內(nèi)存，并借助內(nèi)存調(diào)整數(shù)在外存中的存放順序排序方法稱為外排序。
1.3算法的時(shí)間復(fù)雜度  空間復(fù)雜度
  所謂算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量。 一個(gè)算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。


幾種常見(jiàn)的算法復(fù)雜度：
2.1冒泡排序 （Bubble Sort）    O(n^2)
2.2選擇排序 （Selection Sort） O(n^2 )
2.3插入排序 （Insertion Sort） O(n^2)
2.4堆排序    O( nlog(n) )
2.5歸并排序  O( nlog_2(n)  )
2.6快速排序  最好 O( nlog_2(n) ) 最壞 O(n^2)




wiki 參考 ：http://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95
穩(wěn)定的

• 冒泡排序（bubble sort） — O(n²)
• 雞尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O(n²)
• 插入排序 （insertion sort）— O(n²)
• 桶排序 （bucket sort）— O(n); 需要 O(k) 額外空間
• 計(jì)數(shù)排序 (counting sort) — O(n+k); 需要 O(n+k) 額外空間
• 合併排序 （merge sort）— O(n log n); 需要 O(n) 額外空間
• 原地合併排序 — O(n²)
• 二叉排序樹(shù)排序 （Binary tree sort） — O(n log n)期望時(shí)間; O(n²)最壞時(shí)間; 需要 O(n) 額外空間
• 鴿巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 額外空間
• 基數(shù)排序 （radix sort）— O(n·k); 需要 O(n) 額外空間
• Gnome sort — O(n²)
• Library sort — O(n log n) with high probability, 需要 (1+ε)n 額外空間

[編輯] 不穩(wěn)定

• 選擇排序 （selection sort）— O(n²)
• 希爾排序 （shell sort）— O(n log n) 如果使用最佳的現(xiàn)在版本
• Comb sort — O(n log n)
• 堆排序 （heapsort）— O(n log n)
• Smoothsort — O(n log n)
• 快速排序 （quicksort）— O(n log n) 期望時(shí)間, O(n²) 最壞情況; 對(duì)於大的、亂數(shù)串列一般相信是最快的已知排序
• Introsort — O(n log n)
• Patience sorting — O(n log n + k) 最壞情況時(shí)間，需要 額外的 O(n + k) 空間，也需要找到最長(zhǎng)的遞增子序列（longest increasing subsequence）

[編輯] 不實(shí)用的排序演算法

• Bogo排序 — O(n × n!) 期望時(shí)間，無(wú)窮的最壞情況。
• Stupid sort — O(n³); 遞迴版本需要 O(n²) 額外記憶體
• Bead sort — O(n) or O(√n), 但需要特別的硬體
• Pancake sorting — O(n), 但需要特別的硬體

整理 www.aygfsteel.com/Good-Game