算法（一）

"进步的每一步都步履维艰"

http://www.mashibing.com

排序算法：

big O :算法的时间或者空间，随着问题规模的扩大，而变化的规律

10 种常见的排序算法：选择，冒泡，插入，堆，希尔，归并，快速，桶，计数，基数

希尔排序：

希尔排序为什么比普通的插入排序效率高？因为：在间隔大的时候，移动的次数少，在间隔小的时候，移动的距离短了，从两个方面提高了效率。

希尔排序最优的间隔序列：Knuth 序列  { h = 1; h = 3h +1 }

希尔排序没有用到其他的空间，所以它的空间复杂度是 big O(1)

归并排序： 

在递归的时候一定有一个条件停止返回：base case

 空间复杂度是 big O(n)，为什么不是n方？因为在递归的时候，函数每次调用完，temp数组的空见就会被销毁，所以最多也就是n

TimSort，改进的归并排序

快速排序：

 

 上述代码有两处bug

双轴快排:

java源码里面也是双轴快排

思想：找两个轴，将数组分成三份，加上正在处理的区域，应该是四个区域