归并排序指的是什么？
归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。 若将两个有序表合并成一个有序表，称为二路归并。归并排序归并操作归并操作，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。如 设有数列{6，202，100，301，38，8，1}初始状态：6,202,100,301,38,8,1第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；第二次归并后：{6,100...全部
归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为二路归并。归并排序归并操作归并操作，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。如 设有数列{6，202，100，301，38，8，1}初始状态：6,202,100,301,38,8,1第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；第三次归并后：{1,6,8,38,100,202,301},比较次数：4；总的比较次数为：3+4+4=11；逆序数为14；归并排序算法描述归并操作的工作原理如下：第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置重复步骤3直到某一指针超出序列尾将另一序列剩下的所有元素直接复制到合并序列尾归并排序比较归并排序是稳定的排序。
即相等的元素的顺序不会改变。如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序。
这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要。归并排序的比较次数小于快速排序的比较次数，移动次数一般多于快速排序的移动次数。归并排序用途归并排序排序速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列，应用见2011年普及复赛第3题“瑞士轮”的标程。
归并排序求逆序对数具体思路是，在归并的过程中计算每个小区间的逆序对数，进而计算出大区间的逆序对数（也可以用树状数组来求解）scala代码：objectMainextendsApp{ varreverse_pairs = 0//逆序数 defmsort(cmp:(T, T) => Boolean)(l:List):List = { defmerge(l1:List, l2:List):List=(l1, l2)match{ case(Nil, _) => l2 case(_, Nil) => l1 case(x：left1, y：left2) => if(cmp(x, y)) x：merge(left1, l2) else{ reverse_pairs += l1。
length y：merge(l1, left2) } } valn = l。length / 2 if(n == 0) return l else{ val(l1, l2) = l。
splitAt(n) merge(msort(cmp)(l1), msort(cmp)(l2)) } } println(msort((x:Int, y:Int) => x<y)(List(5, 4, 3, 2, 7,6 ))) println(reverse_pairs)}//采用自上而下的递归方法public class MergeSort { private int Sort(intarr){ //若待排序数组长度<2，则直接返回 if (arr。
length<2) return arr; int mid=arr。length/2; return process(Sort(Arrays。
copyOfRange(arr,0,mid)),Sort(Arrays。copyOfRange(arr,mid,arr。length))); } //合并两个有序数组 private int process(int arr1,intarr2){ int re=new int; //i为arr1的index,j为arr2的index,k为re的index int i=0,j=0,k=0; //获取两个数组较小元素，填入re内 while (i<arr1。
length&&j<arr2。length) re=(arr1<arr2)?arr1:arr2; //若arr1有元素剩余，全部填入re内 if(i!=arr1。
length) for(int p=i;p<arr1。length;p++) re=arr1; //若arr2内有元素剩余，全部填入re内 if(j!=arr2。
length) for(int p=j;p<arr2。length;p++) re=arr2; return re; }。
收起
