排序-归并排序

问题

描述

给指定n个数排序（归并排序）

思路

归-递归，并-合并；对度为n的数递归拆分，然后在每次递归中合并排序；两侧非空桶中；差最大的为空桶数最多的右侧相邻非空桶的最小值与最左侧非空桶的最大值之差！

Code

public class MergerSort {

    public static void main(String[] args) {
        Scanner as=new Scanner(System.in);
        int i,n;
        n=as.nextInt();
        int a[]=new int[n];
        for(i=0;i<n;i++) a[i]=as.nextInt(); if(n>2) {
            merge(a,0,n-1);
        }
        for(i=0;i<n;i++)
            System.out.print(a[i]+" ");

    }
    private static void merge(int[] a, int i, int j) {
        if(i==j) {
            return;
        }else {
            int m=i+(j-i)/2;
            merge(a,i,m);
            merge(a,m+1,j);
            toOne(a,i,m,j); 
        }
    }
    private static void toOne(int[] a, int i, int m, int j) {
        int s[]=new int[j-i+1];
        int x=i,y=m+1,k=0;
        while(x<=m&&y<=j&&k<j-i+1) { if(a[x]>a[y]) {
                s[k]=a[y];
                y++;k++;
            }else {
                s[k]=a[x];
                x++;k++;
            }
        }
        if(x>m) {
            while(k<j-i+1&&y<=j) {
                s[k]=a[y];
                y++;k++;
            }
        }else {
            while(k<j-i+1&&x<=m) {
                s[k]=a[x];
                x++;k++;
            }
        }
        for(k=0;k<j-i+1;k++) {
            a[i+k]=s[k];
        }
 }

解析

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。