Comparison sort¶
七大比较排序算法
bubble sort/冒泡排序¶
始终是未排序的两个相邻值比较.
用第0个和第1个比较，如果第0个大就交换位置…用倒数第二个和最后一个比较，如果倒数第二个大就交换位置。 第一轮就是从前往后相邻的比较，最大的数就在最后一个位置。 用第0个和第一个比较，如果第0个大就交换位置…用倒数第三个和倒数第二个比较，如果倒数第三个大就交换位置。 第二轮就是从前到倒数第二个相邻的比较，第二大的就在倒数第二位置。 依次类推 …
i表示比较几轮（总共比较len-1轮），j表示每次多少个相邻的数比较（每轮比较len-1-i次）。
时间复杂度
平均O(n<sup>2</sup>) 最好O(n) 最差O(n<sup>2</sup>)
空间复杂度
平均O(1)
稳定性
稳定
selection sort/选择排序¶
始终是假设的最值和后面未排序的值依次比较。
第一轮，默认下标为0的位置是最值,然后用这个位置的值和后面的依次比较,如果发现真的最值,就把这个值所在的下标设置新的最值下标. 如果一轮比较完成，最小值下标不是0，就交换位置，将最小值放到第一。 以此类推。 …
i表示比较几轮(len-1), j表示每轮比较的次数(len - (i+1)).
时间复杂度
平均O(n<sup>2</sup>) 最好O(n<sup>2</sup>) 最差O(n<sup>2</sup>)
空间复杂度
O(1)
稳定性
不稳定
insertion sort/插入排序¶
插入排序，从第二个元素开始，每次和前面的序列比较，和前面的序列从后往前比较，找到合适的插入位置。
时间复杂度
平均 O(n<sup>2</sup>) 最好 O(n) 最差 O(n<sup>2</sup>)
空间复杂度
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(n<sup>2</sup>) 最好 O(n<sup>1.3</sup>) 最差 O(n<sup>2</sup>)
空间复杂度
O(1)
稳定性
不稳定
quick sort/快速排序¶
快速排序是冒泡排序的升级版,是目前速度最快的排序,采用分治策略。
从数列中取一个数作为基准数，将比这个数大的数放到右边，小于等于的放到左边。 再对左边和右边的做上述同样的操作，直到各个区间只有一个数。
时间复杂度
平均 O(nlog(n)) 最好 O(nlog(n)) 最差 O(n<sup>2</sup>)
空间复杂度
O(log(n)) ~ O(n)
稳定性
不稳定
merge sort/归并排序¶
时间复杂度
平均 O(nlog(n)) 最好 O(nlog(n)) 最差 O(nlog(n))
空间复杂度
O(n)
稳定性
稳定
