归并排序
我们先看一下归并排序是怎么归并的
两个有序列表,有low指针指向2,high指针指向6,mid指针指向9
再建一个新列表,1<2,所以1放到列表,右指针右移一位,再比较2和3,2放入列表,左指针右移一位...i+=1
while j<=high:
ltmp.append(li[j])
j+=1
li[low:high+1]=ltmp
对于一个数组,我们将其归并排序的步骤...>终止条件:一个元素是有序的。
>合并:讲两个有序列表归并,列表越来越大。..., 5, 9, 0, 14, 15]
[4, 7, 2, 8, 10, 13, 12, 6, 1, 11, 3, 5, 9, 0, 14, 15]
我们可以看出递归排序是从小到大执行,且从左向右
且归并排序时间复杂度...O(nlogn),空间复杂度O(n)
快排,归并,堆排序对比:
一般情况下:快速排序并排序<堆排序
三种排序方法的缺点:
快速排序:极端情况下排序效率低
归并排序:需要额外的内存开销
堆排序:在快的排序算法中相对较慢