排序算法(一)

从哪几个方面选择排序算法

1.时间复杂度

2.空间复杂度

3.比较次数,交换次数

4.稳定性,相同元素排序前后相对位置不变

稳定排序的意义在哪里? 

从订单系统来的数据已经按时间和排序了,现在需要按金额排序,金额相同时按时间排序,这个时候需要稳定的排序算法

一.插入排序

把一个无序的数列一个个插入到有序的数列中,时间复杂度o(n^2) ,最好的情况o(n) 空间复杂度s(n)

二.希尔排序

希尔排序是插入排序的优化版本,在插入排序前将数组分成若干个小数组先进行插入排序,然后再重新组合排序

希尔排序时间复杂度是 O(n^(1.3 − 2)) ，空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n ( log ⁡ n ) 排序算法快 ，因此对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择，总之比一般 O(n^2) 复杂度的算法快得多。

三.归并排序