本文共 397 字,大约阅读时间需要 1 分钟。
利用归并的思想实现的排序方法,用经典的(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起,即分而治之)。
- 归并排序的效率是比较高的,设数列长为N,将数列分开成小数列一共要logN步,每步都是一个合并有序数列的过程,时间复杂度可以记为O(N),故总的时间复为O(N*logN)。
- 归并排序中的比较次数是所有排序中最少的。因为它一开始是不断地划分,比较只发生在合并各个有序的子数组时。
- 数组的初始顺序会影响到排序过程中的比较次数,但是总的而言,对复杂度没有影响。平均情况 or 最坏情况下 它的时间复杂度都是O(NlogN)
- 归并排序在O(N*logN)的几种排序方法(快速排序,归并排序,希尔排序,堆排序)是效率比较高的。
- 归并排序要用一个同等大小的数组作为存储空间保存结果,辅助存储为O(n),是空间复杂度最高的排序。