说说算法那些事-归并排序

归并排序（mergeSort）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。查看完整代码

1.算法思想：将待排序元素，分成若干子序，然后在将子序排序成有序。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

2.算法步骤：

(1)、比较arr[i]和arr[j]的大小，若arr[i]≤arr[j]，则将第一个有序表中的元素arr[i]复制到temp[k]中，并令i和k分别加上1；否则将第二个有序表中的元素arr[j]复制到temp[k]中，并令j和k分别加上1，

(2)、如此循环下去，直到其中一个有序表取完。

(3)、再将另一个有序表中剩余的元素复制到temp中从下标k开始。

(4)、将temp里面的元素合并到arr中。

归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

3.算法详解

初始状态：6,2,8,10,8,9,1

第一次归并后：{6,2},{8,10},{8,9},{1}

第二次归并后：{2,6,8,10}，{1,8,9}；

第三次归并后：{1,2,6,8,8,9,10}；

排序结束

4.算法分析：

时间复杂度：对一个数组，分成小区间需要logN，每一次都有归并操作，所以归并排序在O(N*logN)

稳定性：是稳定的排序算法