Data Structures and Algorithms

Data Structure Sort Search Permutation Combination

All classical, beautiful, and amazing algorithms of computer science

###Sort

• Bubble sort - exchanging values.
• Selection sort - Selection.
• Insertion sort - Insertion.
• Merge sort - Merge.
• Inplace merge sort - Inplace merge.
• Quick sort - Quick.
• Heap sort - Heap.

Analysis of sort algorithms

Name	Best	Average	Worst	Memory	Stable
Bubble sort	n			1	Yes
Selection sort				1	No
Insertion sort	n			1	Yes
Merge sort	nlogn	nlogn	nlogn	worst n	Yes
Inplace merge sort	--	--		1	Yes
Quick sort	nlogn	nlogn		average logn worst n	typical No
Heap sort	nlogn	nlogn	nlogn	1	No
Radix sort	Nil	O(d(n+radix))	Nil	2*radix	Yes

Permutations and Combinations

• full_permutation - recursive method.
• combination - recursive method.

---

数论

• Euclidean algorithm wiki - 欧几里得算法（辗转相除法）An algorithm for the Greatest Common Divisor (GCD).
• Extended Euclidean algorithm wiki - 扩展欧几里得算法 维基

字符串处理

• Edit Distance - 字符串编辑距离 csdn Ref
• atof - ascii to floating point number

Others

• 线段相交 - 参考算法导论
• 八皇后问题
• 数制转换 - Decimal to BinHexOct
• Bitmap - 位图