排序算法之合并排序

  合并排序可以说是应用分治技术的一个相当perfect的例子，这我感觉有点像中国古代的大事小，小事化了的思想。所以说算法还是与我们日常的生活是息息相关的。
 好了。其实，简单来说，合并排序就是把一个需要排序的 数组一分为二，让字数组分别递归排序。最后再合并起来。

public class MergeSort {
    // 合并排序，时间复杂度为nlogn
    public static void  mergeSort(int num[]){
        int n = num.length;
        if(n>1){
            int a[] = new int[n/2];
            int b[] = new int[n-n/2];
         System.arraycopy(num, 0, a, 0, n/2);
         System.arraycopy(num, n/2, b, 0, n-n/2); //复制到新的数组里面
         mergeSort(a);
         mergeSort(b);//分治排序
         merge(a,b,num); //合并
        }

    }
    public static void merge(int a[],int b[],int c[]){
        int i = 0;
        int j = 0;
        int k = 0;
        while((i<a.length)&&(j<b.length)){ //将元素按照大小顺序排序
            if(a[i]>=b[j]){
                c[k++] = a[i++];
            }else{
                c[k++] = b[j++];
            }
        }
        if(i<a.length)
            System.arraycopy(a, i, c, k, a.length-i);
            else
                System.arraycopy(b, j, c, k, b.length-j);//复制剩下的元素
    }

    public static void main(String[] arg){
        int n[]={1,23,45,3,3,2,6};
        mergeSort(n);
            for(int num:n)
            System.out.println(num);



    }

}

这是我写的合并排序的算法，其实，老实说，合并排序在最坏的情况下的键值比较次数十分接近任何基于比较的排序算法在理论上能够达到的最少次数。当是，合并排序每次都需要额外的空间。但是，合并排序却很好的体现了分治思想的内涵，以后的快排就是基于这种思想而来的。另外，合并排序是一中稳定的排序算法。