归并排序（JAVA）

算法

---

  归并排序和快速排序算法一样都是基于分治算法，都把大规模问题划分成更小规模的子问题。归并排序的内容就是按中点切割表，划分成左右两个子表，再继续对左右两个子表分别进行划分，直到无法划分为止。在无法划分时（即左右表都只含一个元素），将左右两表合并成一个有序表，之后不断左右两两合并，直到最终整体有序。
  根据其算法，划分的时间复杂度为o(log2(n))，合并的时间复杂度为o(n)，所以时间复杂度为o(n*log2(n))。但由于合并时有用到辅助表，故空间复杂度为o(n)。总体来看，归并排序不如快速排序。

例子

---

归并排序

Codes

---

package com.fairy.InnerSort;

import java.util.Scanner;
/**
 * 归并排序
 * @author Fairy2016
 *
 */
public class MergeSort {
    static int b[] = new int[100];//辅助数组，帮助合并
    public static void Merge(int a[], int low, int high, int mid) {
        int i,j,k;
        for(i = low; i <= high; i++) {
            b[i] = a[i];
        }
        //将mid前半部分和后半部分合并成一个有序表
        for(i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
            //谁小要谁
            if(b[i] < b[j]) {
                a[k] = b[i++];
            } else {
                a[k] = b[j++];
            }
        }
        //两部分可能并不一样长，多余的直接赋值
        while(i <= mid) {
            a[k++] = b[i++];
        }
        while(j <= high) {
            a[k++] = b[j++];
        }
    }
    
    public static void sort(int a[], int low, int high) {
        if(low < high) {
            //分治算法，划分成更小规模的左右有序表，两两合并
            int mid = (low + high)/2;
            sort(a, low, mid);
            sort(a, mid+1, high);
            Merge(a, low, high, mid);
        }
    }

    public static void Print(int a[], int n) {
        for(int i = 1; i <= n; i++) {
            System.out.print(a[i]+" ");
        }
    }

    public static void main(String args[]) {
        int n;
        int a[];
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            n = scanner.nextInt();
            if(n > 0) {
                a = new int[n+1];
                for(int i=1; i <= n; i++) {
                    a[i] = scanner.nextInt();
                }
                sort(a, 1, n);
                Print(a, n);
            }
        }
        scanner.close();
    }
}