归并排序

归并排序算法和快速排序算法是java.util.Arrays中使用的排序算。对于一般的基本数据类型，Arrays.sort函数使用双轴快速排序算法，而对于对象类型使用归并排序（准确的说使用的是TimSort排序算法，它是归并排序的优化版本）。这样做的原因有两点，第一个原因，归并排序是稳定的，而快速排序不是稳定的。第二个原因，对于基本数据类型，排序的稳定性意义不大，但对于复合数据类型（比如对象）排序的稳定性就能帮助我们保持排序结果的某些性质。
j

• 自底向上排序
  自底向上的归并排序算法的思想就是数组中先一个一个归并成两两有序的序列，两两有序的序列归并成四个四个有序的序列，然后四个四个有序的序列归并八个八个有序的序列，以此类推，直到，归并的长度大于整个数组的长度，此时整个数组有序。需要注意的是数组按照归并长度划分，最后一个子数组可能不满足长度要求，这个情况需要特殊处理。自顶下下的归并排序算法一般用递归来实现，而自底向上可以用循环来实现。

1.png

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

    public void merge(int[] a, int i, int len){
        int start = i;
        int len_i = i + len;//归并的前半部分数组[0,1)
        int j = i + len;
        int len_j = j +len;//归并的后半部分数组[1,2)
        int[] temp = new int[2*len];
        int count = 0;
        while(i < len_i && j < len_j && j < a.length){
            if(a[i] <= a[j]){
                temp[count++] = a[i++];
            }
            else{
                temp[count++] = a[j++];
            }
        }
        while(i < len_i && i < a.length){//注意：这里i也有可能超过数组长度
            temp[count++] = a[i++];
        }
        while(j < len_j && j < a.length){
            temp[count++] = a[j++];
        }
        count = 0;
        while(start < j && start < a.length){
            a[start++] = temp[count++];
        }
    }

• 自顶向下

2.jpg

    private static void mergeSort(int[] arr, int left, int right) {
        if (left<right) {
            int middle=(left+right)/2;
            mergeSort(arr, left, middle);
            mergeSort(arr, middle+1, right);
            merge(arr,left,middle,right);
        }
    }

    private static void merge(int[] arr, int left, int middle, int right) {
        int [] tempArray=new int[arr.length];
        int rightStart=middle+1;
        int temp=left;
        int third=left;
        while(left<=middle&&rightStart<=right){
            if (arr[left]<=arr[rightStart]) {
                tempArray[third]=arr[left];
                third++;
                left++;
            }else {
                tempArray[third]=arr[rightStart];
                third++;
                rightStart++;
            }
        }
        while(left<=middle){
            tempArray[third]=arr[left];
            third++;
            left++;
        }
        while (rightStart<=right) {
            tempArray[third]=arr[rightStart];
            third++;
            rightStart++;
        }
        while (temp<=right) {
            arr[temp]=tempArray[temp];
            temp++;
        }
    }