# 算法

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。

# 经典排序算法

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

常见的内部排序算法有：冒泡排序、插入排序、选择排序、快速排序、堆排序、基数排序等。

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	排序方式	稳定性
冒泡排序	O($n^2$)	O(n)	O($n^2$)	O(1)	`In-place`	稳定
选择排序	O($n^2$)	O($n^2$)	O($n^2$)	O(1)	`In-place`	不稳定
插入排序	O($n^2$)	O(n)	O($n^2$)	O(1)	`In-place`	稳定
希尔排序	O(n $\log{n}$)	O(n$log^2{n}$)	O(n$log^2{n}$)	O(1)	`In-place`	不稳定
归并排序	O(n $\log{n}$)	O(n $\log{n}$)	O(n $\log{n}$)	O(n)	`Out-place`	稳定
快速排序	O(n $\log{n}$)	O(n $\log{n}$)	O($n^2$)	O($\log{n}$)	`In-place`	不稳定
堆排序	O(n $\log{n}$)	O(n $\log{n}$)	O(n $\log{n}$)	O(1)	`In-place`	不稳定
计数排序	O(n + k)	O(n + k)	O(n + k)	O(k)	`Out-place`	稳定
桶排序	O(n + k)	O(n + k)	O($n^2$)	O(n + k)	`Out-place`	稳定
计数排序	O(n x k)	O(n x k)	O(n x k)	O(n + k)	`Out-place`	稳定

名词解释：