排序算法高级篇

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

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

归并排序

定义

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

特性

• 归并排序的时间复杂度是 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++];            
        }
    }
}