发现 自己写个小程序 - 文本存储二叉结构的hashMap。 那个费劲！ 痛下决心 仔细学习 算法 。
（如果大家有兴趣就跟我一起 - 《算法导论》 ，也望大家监督我能每天拿出一小时和大家分享算法,算法代码我会尽量使用 py 和 解决一些分析日志的应用上靠 （其实，上面费劲的 二叉hash 是为了分析日志中 - 希望能实现 多个大文件不需要合并就能根据某列排序输出! 目前的解决办法 find .. -exec cat {} \; | perl |sort 的笨方法 ）
1. 算法在计算中的作用 （笔记） :
算法(algorithm):就是定义良好的计算过程，它取一个或一组作为输出，并产生一个或一组自作为输出。
一些函数运行级别 # http://www.wolframalpha.com/ 函数都可在网站里运行
这里 n=一亿条数据 :
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 无穷
n! 10^362880
需要知道的复杂度 - 在某一个临界点后 合并会别插入要快的
插入排序 复杂度 n^2 http://www.wolframalpha.com/input/?i=n^2
合并排序 复杂度 n*log_2(n) http://www.wolframalpha.com/input/?i=n*log_2%28n%29+
网上的查找到的一些名称：参考 http://www.51testing.com/?uid-130868-action-viewspace-itemid-66729
1.1 稳定排序 非稳定排序 -
稳定排序是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，。反之，就是非稳定的排序。
1.2 内排序 外排序
在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序； 在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。
1.3 算法的时间复杂度 空间复杂度
所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。
几种常见的算法复杂度：
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
穩定的
（如果大家有兴趣就跟我一起 - 《算法导论》 ，也望大家监督我能每天拿出一小时和大家分享算法,算法代码我会尽量使用 py 和 解决一些分析日志的应用上靠 （其实，上面费劲的 二叉hash 是为了分析日志中 - 希望能实现 多个大文件不需要合并就能根据某列排序输出! 目前的解决办法 find .. -exec cat {} \; | perl |sort 的笨方法 ）
1. 算法在计算中的作用 （笔记） :
算法(algorithm):就是定义良好的计算过程，它取一个或一组作为输出，并产生一个或一组自作为输出。
一些函数运行级别 # http://www.wolframalpha.com/ 函数都可在网站里运行
这里 n=一亿条数据 :
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 无穷
n! 10^362880
需要知道的复杂度 - 在某一个临界点后 合并会别插入要快的
插入排序 复杂度 n^2 http://www.wolframalpha.com/input/?i=n^2
合并排序 复杂度 n*log_2(n) http://www.wolframalpha.com/input/?i=n*log_2%28n%29+
网上的查找到的一些名称：参考 http://www.51testing.com/?uid-130868-action-viewspace-itemid-66729
1.1 稳定排序 非稳定排序 -
稳定排序是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，。反之，就是非稳定的排序。
1.2 内排序 外排序
在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序； 在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。
1.3 算法的时间复杂度 空间复杂度
所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。
几种常见的算法复杂度：
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
穩定的
- 冒泡排序（bubble sort） — O(n2)
- 雞尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O(n2)
- 插入排序 （insertion sort）— O(n2)
- 桶排序 （bucket sort）— O(n); 需要 O(k) 額外空間
- 計數排序 (counting sort) — O(n+k); 需要 O(n+k) 額外空間
- 合併排序 （merge sort）— O(n log n); 需要 O(n) 額外空間
- 原地合併排序 — O(n2)
- 二叉排序樹排序 （Binary tree sort） — O(n log n)期望時間; O(n2)最壞時間; 需要 O(n) 額外空間
- 鴿巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 額外空間
- 基數排序 （radix sort）— O(n·k); 需要 O(n) 額外空間
- Gnome sort — O(n2)
- Library sort — O(n log n) with high probability, 需要 (1+ε)n 額外空間
[編輯] 不穩定
- 選擇排序 （selection sort）— O(n2)
- 希爾排序 （shell sort）— O(n log n) 如果使用最佳的現在版本
- Comb sort — O(n log n)
- 堆排序 （heapsort）— O(n log n)
- Smoothsort — O(n log n)
- 快速排序 （quicksort）— O(n log n) 期望時間, O(n2) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序
- Introsort — O(n log n)
- Patience sorting — O(n log n + k) 最壞情況時間，需要 額外的 O(n + k) 空間，也需要找到最長的遞增子序列（longest increasing subsequence）
[編輯] 不實用的排序演算法
- Bogo排序 — O(n × n!) 期望時間，無窮的最壞情況。
- Stupid sort — O(n3); 遞迴版本需要 O(n2) 額外記憶體
- Bead sort — O(n) or O(√n), 但需要特別的硬體
- Pancake sorting — O(n), 但需要特別的硬體
本文转自博客园刘凯毅的博客，原文链接：算法 复杂度分析图
，如需转载请自行联系原博主。
