归并排序(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)
稳定性:是稳定的排序算法
网友评论