归并排序（JAVA）

128kj

并归排序：
将两个或两个以上的有序数组组合成一个新的有序数组，叫并归排序

排序过程
1、 设初始数组有n个数据，则可看成n个有序的子数组， 每个子数组长度为1；
2、 两两合并，得到n/2或n/2+1 个长度为2 或1 的有序子数组；
3、 再两两合并，…… 如此重复，直至得到一个长度为n 的有序数组为止。

下面是归并排序的一个简单的例子:

初始值 【49】 【38】 【65】 【97】 【76】 【13】 【27】



public class MergeSort {        public static void sort(int[] arr) {       //创建临时数组        int[] tempArr =new int[arr.length];        msort(arr, tempArr, 0, arr.length);    }       private static void msort(int[] arr, int[] tempArr, int first,int last) {         if (first+1  < last) {                       int midpt = (last + first) / 2;            msort(arr, tempArr, first, midpt);            msort(arr, tempArr, midpt, last);                       if (arr[midpt - 1]<=arr[midpt])//如果前半部分与后半部分正好形成了顺序                return;                       int indexA, indexB, indexC;//前半部分的索引,后半部分的索引,临时数组的索引            indexA = first;            indexB = midpt;            indexC = first;            while (indexA < midpt && indexB < last) {                if (arr[indexA]<arr[indexB]) {                    tempArr[indexC] = arr[indexA]; //copyto tempArr                    indexA++;                 } else {                    tempArr[indexC] = arr[indexB]; //copyto tempArr                    indexB++;                 }                indexC++;             }            //copy the tail of the sublist that is not exhausted            while (indexA < midpt) {                tempArr[indexC++] = arr[indexA++];             } while (indexB < last) {                tempArr[indexC++] = arr[indexB++];             }                        将临时数组的所有元素复制到原数组            for (int i = first; i < last; i++)                arr = tempArr;        }    }    public static void main(String[] args){     int  a[]={100,7,10,19,56,25,12,7,17,21,-1,30,48};           sort(a);      for(int i:a)        System.out.print(i+",");   }}