排序算法高级篇

距离上次的排序算法文章已经过了蛮久了，今天终于有时间来写写高级的排序，如有不当请多指教！

• 归并排序
• 快速排序
• 堆排序、

归并排序

定义

• 要将一个数组排序，可以先(递归地)将它分成两半分别排序，然后将结果归并起来

特性

• 归并排序的时间复杂度是O(N*lgN)
• 归并排序是稳定的

public class MergeSort {

    private static int[] temp;//临时数组
    
    public static void sort(int[] a) {    
        temp=new int[a.length];//避免在递归中频繁新建数组
        sort(a,0,a.length-1);    
  }
    
    private static void sort(int[] a,int low,int hig) {
        
        if (hig<=low)  return;
        int mid=low+(hig-low)/2;
        sort(a, low, mid);//左边排序
        sort(a, mid+1, hig);//右边排序
        merge(a,low,mid,hig);//将两个有序子数组归并
    }
    //归并
    public static void merge(int[] a,int low,int mid,int hig) {
        //i为左序列索引、j为右序列索引
        int i=low,j=mid+1;
        //将a[low..hig]复制到temp[low..hig]
        for (int k = low; k <= hig; k++) {
            temp[k]=a[k];
        }
        
        for (int k = low; k <= hig; k++) {
            if (i>mid)                     a[k]=temp[j++];   //左边用尽则取右边元素
            else if (j>hig)             a[k]=temp[i++];   //右边用尽则取左边元素
            else if (temp[i]<temp[j])     a[k]=temp[i++];   //比较左右取小值
            else                        a[k]=temp[j++];            
        }
    }
}