入门算法：归并排序

上手难度：★★☆

算法复杂度：O(nlogn)

mergeSort.gif

排序思想：

将数组采用二分法，不断的递归分割，直至分割到单个元素，再进行比较，将每一小段都进行排序，然后回归到上一层，逐步完成排序过程；
之所以是n乘以logn，是因为在排序的过程中，将数组通过二分法分成了logn层，每一层级用O(n)级别的算法来做事情，下图就是展示logn层排序的流程

代码实现：

public class MergeSort {

    //归并排序算法实现
    public static void mergeSort(int[] arr, int left, int middle, int right){
        
        int[] temp = new int[right + 1 - left];//临时的辅助数组
        for(int i = left; i <= right; i++){
            temp[i - left] = arr[i];
        }

        int i = left;
        int j = middle + 1;//两个数组的索引
        
        for(int k = left; k <= right; k ++){
            if(i > middle){//如果k在这种情况下还没有遍历完，那说明此时i已经遍历到最大值了，而j索引指向的数组元素还没有完全归并回去
                arr[k] = temp[j - left];
                j++;
            }else if(j > right){
                arr[k] = temp[i - left];
                i++;
            }else if(temp[i - left] > temp[j - left]){//上面的条件都不满足再走这里的判断，先判断索引的合法性
                arr[k] = temp[j - left];//但是从逻辑思维上来思考，从这里开始比较好理解
                j++;
            }else{
                arr[k] = temp[i - left];
                i++;
            }
        }
    }

    //递归使用归并排序，对arr[left...right]的范围进行排序
    public static void merge(int[] arr, int left, int right){
        if(left >= right){
            return;
        }

        int middle = left + (right-left)/2;
    
        merge(arr, left, middle);
        merge(arr, middle + 1, right);
  //    if(arr[middle] <= arr[middle+ 1])//如果出现这种情况，那么说明已经是有序的了，无需进行下面的归并操作
        if(arr[middle] > arr[middle + 1]){//反之就需要进行归并
            mergeSort(arr, left, middle, right);
        }
    }

    public static void merge(int[] arr, int length){
        merge(arr, 0, length - 1);
    }

    public static void main(String[] args) {

        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        merge(arr, arr.length);

        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }
    }
}

优点：

O(nlogn)算法比O(n^2)算法快多了，引入了树型结构后，不需要像之前那样挨个比较

缺点：

需要开辟一个同样大小的临时空间来辅助我们完成这个过程，多使用了存储的空间，只不过在现在的计算机中，时间的效率比空间的效率重要的多

补充：
当递归的一层元素量比较少的时候，整个数组近乎有序的概率就会比较大，此时插入排序有优势，对merge可以做如下改动

    //递归使用归并排序，对arr[left...right]的范围进行排序
    public static void merge(int[] arr, int left, int right){
        if(right - left <= 15){
            insertionSort(arr, l, r);
            return;
        }
        int middle = (left + right)/2;
        merge(arr, left, middle);
        merge(arr, middle + 1, right);
  //    if(arr[middle] <= arr[middle+ 1])//如果出现这种情况，那么说明已经是有序的了，无需进行下面的归并操作
        if(arr[middle] > arr[middle + 1]){//反之就需要进行归并
            mergeSort(arr, left, middle, right);
        }
    }

最后编辑于：2020.08.31 10:03:06