.. _sortalgorithm:
Comparison sort
===============
七大比较排序算法
bubble sort/冒泡排序
--------------------
始终是未排序的两个相邻值比较.
用第0个和第1个比较，如果第0个大就交换位置...用倒数第二个和最后一个比较，如果倒数第二个大就交换位置。
第一轮就是从前往后相邻的比较，最大的数就在最后一个位置。
用第0个和第一个比较，如果第0个大就交换位置...用倒数第三个和倒数第二个比较，如果倒数第三个大就交换位置。
第二轮就是从前到倒数第二个相邻的比较，第二大的就在倒数第二位置。
依次类推
...
i表示比较几轮（总共比较len-1轮），j表示每次多少个相邻的数比较（每轮比较len-1-i次）。
* 时间复杂度
平均O(n2)
最好O(n)
最差O(n2)
* 空间复杂度
平均O(1)
* 稳定性
稳定
selection sort/选择排序
-----------------------
始终是假设的最值和后面未排序的值依次比较。
第一轮，默认下标为0的位置是最值,然后用这个位置的值和后面的依次比较,如果发现真的最值,就把这个值所在的下标设置新的最值下标.
如果一轮比较完成，最小值下标不是0，就交换位置，将最小值放到第一。
以此类推。
...
i表示比较几轮(len-1), j表示每轮比较的次数(len - (i+1)).
* 时间复杂度
平均O(n2)
最好O(n2)
最差O(n2)
* 空间复杂度
O(1)
* 稳定性
不稳定
insertion sort/插入排序
-----------------------
插入排序，从第二个元素开始，每次和前面的序列比较，和前面的序列从后往前比较，找到合适的插入位置。
* 时间复杂度
平均 O(n2)
最好 O(n)
最差 O(n2)
* 空间复杂度
O(1)
* 稳定性
稳定
shell sort/希尔排序
-------------------
希尔排序是基于插入排序的，通过逐步缩小插入排序的增量实现。
可以用序列长度的一半作为gap。
基于经验的一组序列：
Marcin Ciura’s gap sequence: gaps = [701, 301, 132, 57, 23, 10, 4, 1]
例如gap=10, 就是0和10比较，1和11比较； gap=4 就是0和4比较，1和5比较。
* 时间复杂度
平均 O(nlog(n)) ~ O(n2)
最好 O(n1.3)
最差 O(n2)
* 空间复杂度
O(1)
* 稳定性
不稳定
quick sort/快速排序
-------------------
快速排序是冒泡排序的升级版,是目前速度最快的排序,采用分治策略。
从数列中取一个数作为基准数，将比这个数大的数放到右边，小于等于的放到左边。
再对左边和右边的做上述同样的操作，直到各个区间只有一个数。
* 时间复杂度
平均 O(nlog(n))
最好 O(nlog(n))
最差 O(n2)
* 空间复杂度
O(log(n)) ~ O(n)
* 稳定性
不稳定
heap sort/堆排序
----------------
堆排序也叫二叉树排序.
* 时间复杂度
平均 O(nlog(n))
最好 O(nlog(n))
最差 O(nlog(n))
* 空间复杂度
O(1)
* 稳定性
不稳定
merge sort/归并排序
-------------------
* 时间复杂度
平均 O(nlog(n))
最好 O(nlog(n))
最差 O(nlog(n))
* 空间复杂度
O(n)
* 稳定性
稳定
Non comparison sort
===================
基数排序,计数排序,桶排序三种排序都是非比较排序.
radix sort/基数排序
-------------------
counting sort/计数排序
----------------------
bucket sort/桶排序
------------------