排序算法之归并（Java语言）

2018-07-01

　　归并排序也可以叫合并排序,英文单词叫做merge它是与插入排序、交换排序、选择排序不同
的一类排序方法，不同之处在于：它要求：待排序序列是由若干个有序子序列组成。

一、基本思想：

　　归并排序是将两个或两个以上的有序序列合并成一个新的有序序列。本篇文章介绍的就是归并排序主要是将两个有序数据序列合并成一个新的有序序列。

　　合并的方法是比较各子序列的第一个记录的键值，最小的一个就是排序的第一个记录的键值。取出这个记录，继续比较各子序列现有的第一个记录的键值，便可以找出排序后的第二个键值。然后开始递归，最终得到排序结果。所以归并排序的基础就是合并。

1）有序序列的合并

归并排序的核心是：两个有序子序列的合并。

此算法的执行时间为：O(n-h+1)。

2）二路归并排序

二路归并排序是将两个有序表合并成一个有序表的排序方法。

二路归并排序是稳定的。

　　归并排序算法的时间复杂度为O（nlog2n）。（其过程需要ｌｏｇｎ趟，每趟的复杂度Ｏ（ｎ）因此时间的复杂度为O（nlog2n））

二、Java代码如下：

public class guiBingpaixu2 {
	static int number=0;
    public static void main(String[] args) {
        int[] a = {24, 5, 98, 28, 99, 56, 34, 2 };
        printArray("排序前：",a);
        System.out.println("开始排序");
        Sort(a, 0, a.length - 1);
        printArray("排序后：",a);
    }
 
    private static void printArray(String pre,int[] a) {//打印输出
        System.out.print(pre+"\n");
        for(int i=0;i<a.length;i++)
            System.out.print(a[i]+"\t");    
        System.out.println();
    }
    private static void Sort(int[] a, int left, int right) {
        if(left>=right)
            return;    
        int mid = (left + right) / 2;//二路归并排序里面有两个Sort，多路归并排序里面写多个Sort就可以了
        Sort(a, left, mid);
        Sort(a, mid + 1, right);
        merge(a, left, mid, right);
 
    }
    private static void merge(int[] a, int left, int mid, int right) {
    
        int[] tmp = new int[a.length];
        int r1 = mid + 1;
        int Index = left;
        int flag=left;
// 逐个归并。意思：将拿到的2个数组（每个数组元素可能是1，2个或者4个等等。将这2个数组排序，小的放在左边，大的放在右边）
//以下这个判断，左右2部分，只有一部分存入数组；剩余的是排好序的，会在40行或者44行的语句进行存入
        while(left <=mid && r1 <= right) {
            if (a[left] <= a[r1]) //小的放在临时数组左边
                tmp[Index++] = a[left++];
            else				//大的放在右边
                tmp[Index++] = a[r1++];
        }
//看上情况，可能将左边剩余的归并。
        while (left <=mid) {
            tmp[Index++] = a[left++];
        }
 //看上情况，可能将右边剩余的归并
        while ( r1 <= right ) {
            tmp[Index++] = a[r1++];
        } 
            System.out.println("第"+(++number)+"趟排序:");
//从临时数组拷贝到原数组
        while(flag<=right){
             a[flag]=tmp[flag];
             //输出中间归并排序结果
             System.out.print(a[flag]+"\t");
             flag++;
        }
        System.out.println();
     }
}

　　运行结果如下：