1、普通归并排序

归并排序算法的基本思想是将待排序元素分成大小大致相同的两个子序列，分别对这两个字序列进行排序，最终将排好序的子序列合并为所要求的序列。归并排序算法完全依照下面3个步骤进行。

（1）分解。将n个元素分成各含n/2个元素的子序列。

（2）求解。用归并排序对两个子序列递归地排序。

（3）合并。合并两个已经排好序的子序列以得到排序结果。

核心代码如：

void MergeSort(int a[],int p,int r){
        int q;
        if(p<r){
            q=(p+r)/2;
            MergeSort(a, p, q);
            MergeSort(a,q+1,r);
            Merge(a,p,q,r);
        }
    }

完工代码如下：

​import java.util.Arrays;
import java.util.Scanner;
public class MergeSort1 {
    public static void main(String args[]) {
        MergeSort1 mer = new MergeSort1();
        Scanner input = new Scanner(System.in );
        System.out.print("请输入要排序的个数：");
        int n = input.nextInt();
        int [] array = new int [n];
        System.out.print("请输入排序数：");
        for(int i=0;i<n ;i++)
            array[i] = input.nextInt();
        System.out.println("原数据:" + Arrays.toString(array));
        mer.MergeSort(array,0,n-1);
        System.out.println("排序以后:" + Arrays.toString(array));
    }
    void Merge(int a[],int p,int q ,int r){
        int n1=q-p+1;
        int n2=r-q;
        int i,j ,k;
        int L [] = new int [n1+1];
        int R [] = new int [n2+1];
        for(i=0;i<n1;i++){
            L[i]=a[p+i];
        }
        for(j=0;j<n2;j++){
            R[j]=a[q+j+1];
        }
       L[n1]=R[n2]=1000;
        i= 0;
        j= 0;
        for(k=p;k<r+1;k++){
            if(L[i]<R[j]){
                a[k]=L[i];
                i++;
            }
            else{
                a[k]=R[j];
                j++;
            }
        }
    }
    void MergeSort(int a[],int p,int r){
        int q;
        if(p<r){
            q=(p+r)/2;
            MergeSort(a, p, q);
            MergeSort(a,q+1,r);
            Merge(a,p,q,r);
            System.out.println("分治递归排序以后:" + Arrays.toString(a));
        }
    }
}
​

结果截图

2、自然归并排序

算法描述:对于初始给定的数组,通常存在多个长度大于1的已自然排好序的子数组段.例如,若数组a中元素为{4,8,3,7,1,5,6,2},则自然排好序的子数组段有{4,8},{3,7},{1,5,6},{2}.用一次对数组a的线性扫描就足以找出所有这些排好序的子数组段.然后将相邻的排好序的子数组段两两合并,构成更大的排好序的子数组段({3,4,7,8},{1,2,5,6}).继续合并相邻排好序的子数组段,直至整个数组已排好序。

核心代码如下：

public void mergeSort(int[] a) {
        int len = 0;
        while(indexLen(0,a)<a.length){
            for (int i = 0,k1=0,k2=0; i < a.length; ) {
                k1=indexLen(i,a);
                k2=indexLen(k1,a);
                merge(a, i, k1,k2);
                i=i+k1+k2;
            }
        }
    }

完工代码如下：

import java.util.Arrays;
import java.util.Scanner;
public class Sort {
    public static void main(String args[]) {
        Sort mer = new Sort();
        Scanner input = new Scanner(System.in );
        System.out.print("请输入要排序的个数：");
        int n = input.nextInt();
        int [] array = new int [n];
        System.out.print("请输入排序数：");
        for(int i=0;i<n ;i++)
            array[i] = input.nextInt();
        System.out.println("原数据:" + Arrays.toString(array));
        mer.mergeSort(array);
        System.out.println("排序以后:" + Arrays.toString(array));
    }
//判断数组有序子序段的长度
    int indexLen(int j,int [] a) {

        int k=j+1;
        int len=1;
        for (; ;) {
            if(k>=a.length)
                break;
            if(a[j]<a[k]) {
                len++;
                j++;
                k++;
            }
            else break;
        }
        return len;
    }
    int index=0;
    public void Printf(int a[]){
        index=indexLen(index,a);
    }
    public void mergeSort(int[] a) {
        int len = 0;
        while(indexLen(0,a)<a.length){
            for (int i = 0,k1=0,k2=0; i < a.length; ) {
                k1=indexLen(i,a);
                k2=indexLen(k1,a);
                merge(a, i, k1,k2);
                i=i+k1+k2;
                System.out.println("相邻两组合并排序以后:" + Arrays.toString(a));
            }
        }
    }
    public void merge(int[] a, int i, int len1,int len2) {
        int start = i;
        int X = i + len1;// 归并的前半部分数组
        int j = i + len1;
        int Y = j + len2;// 归并的后半部分数组
        int[] temp = new int[len1+len2];
        int count = 0;
        while (i < X && j < Y && j < a.length) {
            if (a[i] <= a[j]) {
                temp[count++] = a[i++];
            }
            else {
                temp[count++] = a[j++];
            }
        }
        while (i < X && i < a.length) {
            temp[count++] = a[i++];
        }
        while (j < Y && j < a.length) {
            temp[count++] = a[j++];
        }
        count = 0;
        while (start < j && start < a.length) {
            a[start++] = temp[count++];
        }
    }
}

结果截图

自然归并排序

（1）思路：

1、找出需要排序数组中的所有有序子数组，将每个子数组的起始下标存在一个辅组数组中，假设为mark[]。

2、将有序字数组两两归并，最后得到有序数组。

3、需要注意被排序数组的长度N<=2的特殊情形。

（2）代码

public class NatureMerge extends Sort {
	public static <T extends Comparable<? super T>> int pass(T[] arr, int[] mark) {
		int j = 0;
		T temp = arr[0];
		mark[j++] = 0;
		for(int i = 1; i < arr.length; i++) {
			if(temp.compareTo(arr[i]) <= 0) temp = arr[i];
			else mark[j++] = i;
		}
		mark[j] = arr.length;
		return j;
	}
	
	public static <T extends Comparable<? super T>> void natureMerge(T[] arr, T[] aux, int[] mark) {
		int max = pass(arr, mark);
		
		for(int sz = 1; sz < max; sz += sz) {
			for(int i = 0; i < max - sz; i += sz + sz) {
				merge(arr, aux, mark[i], mark[i + sz] - 1, mark[Math.min(i + sz + sz, max)] - 1);
			}
		}
	}
	
	//要检查N<=2时的特殊境况
	@SuppressWarnings("unchecked")
	public static <T extends Comparable<? super T>> void sort(T[] a) {
		int N = a.length;
		if(N <= 1) return ;
		if(N == 2) if(less(a[1], a[0])) exch(a, 0, 1);
		int[] mark = new int[N];
		T[] aux = (T[])new Comparable[N];
		natureMerge(a, aux, mark);
	}
	
	private static <T extends Comparable<? super T>> void merge(T[] a, T[] aux, int lo, int mid, int hi) {
		for(int i = lo; i <= hi; i++) {
			aux[i] = a[i];
		}
		int j = lo;
		int k = mid + 1;
		for(int i = lo; i <= hi; i++) {
			if(j > mid) a[i] = aux[k++]; 
			else if(k > hi) a[i] = aux[j++];
			else if(less(aux[j], aux[k])) a[i] = aux[j++];
			else a[i] = aux[k++];
		}		
	}
	
	protected static <T extends Comparable<? super T>> boolean less(T v, T w) {
        return v.compareTo(w) < 0;
    }
	
	protected static <T extends Comparable<? super T>> void exch(T[] a, int i, int j) {
        T swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
}

单链表归并排序

public static <T extends Comparable<? super T>> Node<T> sort(Node<T> list) {
		if(list == null || list.next == null) return list;
		Turple<Node<T>, Node<T>> t = getTwoLists(list);
		Node<T> l = sort(t.e1);
		Node<T> r = sort(t.e2);
		return merge(l, r);
	}
	
	public static <T extends Comparable<? super T>> Node<T> merge(Node<T> left, Node<T> right) {
		if(left == null) return right;
		if(right == null) return left;
		if(less(right.data, left.data)) {
			Node<T> temp = left;
			left = right;
			right = temp;
		}
		Node<T> lf = left;
		Node<T> rg = right;
		Node<T> temp = null;
		while(lf.next != null) {
			if(less(right.data, lf.next.data)) {
				while(rg.next != null && less(rg.next.data, lf.next.data)) {
					rg = rg.next;
				}
				temp = right;
				right = rg.next;
				rg.next = lf.next;
				lf.next = temp;
				if(right == null) break;
			}
			lf = lf.next;
		}
		if(lf.next == null) {
			lf.next = right;
		}
		return left;
	}
	
	public static <T extends Comparable<? super T>> Turple<Node<T>, Node<T>> getTwoLists(Node<T> list) {
		if(list.next == null) throw new ArrayIndexOutOfBoundsException();
		Node<T> p1 = list;
		Node<T> p2 = list;
		Node<T> temp = null;
		
		while(p2.next != null) {
			p2 = p2.next;
			if(p2.next != null) {
				p2 = p2.next;
			}
			temp = p1;
			p1 = p1.next;
		}
		temp.next = null;
		return new Turple<Node<T>, Node<T>>(list, p1);
	}

例：a[]={4,8,3,7,1,5,6,2}
自然归并排序指的是对数组先进行一次线性扫描，得到自然排好序的子数段{4，8}，{3，7}，{1，5，6}，{2}。在对其进行两两合并成更大的排好序的数组。

#include <stdio.h>
#define N 8
int GetIndex(int a[N],int index[N]){
int i,j=0;
index[j++]=0;
for(i=0;i<N-1;i++)
 {
   if(a[i]>a[i+1])
    index[j++]=i+1;
 }
 index[j++]=N;//后面mergesort中合并需要判断i的范围，否则index[i+2]-1无法表示。合并两个需要三个数组下标
 return j;

}
void merge(int a[N], int left, int mid, int right) {
    int i=left,j=mid+1,k=left;
    int t;
    int d[N];
    while(i <= mid && j <= right) {
        if(a[i] < a[j]){
            d[k++] = a[i++];
        } else {
            d[k++] = a[j++];
        }
    }
    if(i!=mid+1){
        for(t=i;t<=mid;t++){
            d[k++]=a[t];
        }
    }
    if(j != right+1) {
        for(t = j; t <= right; t++){
            d[k++] = a[t];
        }
    }
    for(i = left; i <= right; i++){   //把此次进行合并后的元素拷贝到原数组
        a[i] = d[i];				  //没有参与合并的数组元素不变.为了进行下一次自然分组。
    }
}
void mergeSort(int a[N],int index[N]){
    int length=GetIndex(a,index);
    int i;
    while(length!=2){
        for(i=0;i<length-2;i+=2){//      i+=2是每次合并两个 向右移动两个
            merge(a,index[i],index[i+1]-1,index[i+2]-1);
        }
        length=GetIndex(a,index);
    }
}
void print(int n,int a[])
{   int i;
    for(i=0;i<n;i++)
    {if (i!=n-1)  printf("%d, ",a[i]);
    else  printf("%d", a[i]);
}
printf("\n");

}
int main()
{
    int a[N]={4,8,3,7,1,5,6,2};
    int index[N];
    print(N,a);
    mergeSort(a,index);
    print(N,a);
    return 0;
}

运行结果：