欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法与数据结构(3)—— 归并排序

程序员文章站 2022-06-04 17:15:07
...

前言:

前面介绍的几个时间复杂度为 O(n^2)的几个排序算法(选择、插入、冒泡、希尔排序),其中尤为需要注意的是插入排序,在近乎有序的测试用例条件下,此算法的效率会高于O(n*logn)的排序算法,几乎是O(n),

 一、O(n*logn) 和 O(n^2)算法比较:

     O(n*logn)可以在1s内轻松处理百万数量级的数据,当n=10^5时,其实这个测试数量也不是很大,O(n*logn)比O(n^2)快6000倍。

二、归并排序:

算法与数据结构(3)—— 归并排序


(1)整体思路:

  • 将数组对半划分,分别对左右数组进行排序。
  • 继续划分左边,右边的数组,然后继续划分.....直到划到一个只剩下一个元素,开始对每一个小部分进行排序
  • 小部分排序完,进行向上归并,就是与旁边的小组进行归并(此时每个小组都是有序的,层层往上归并)

(2)算法复杂度

n个元素每次分两组,log以2为底n,就相当于一个树的高度。每次归并处理都可以看做O(n)的时间复杂度,整个过程O(nlogn)

  (3)  代码实现

  • i,j分别指向当前正在考虑的元素,
  • k最终归并,i和j比较后放入的位置,即表示下一个需要放的位置
  • 一个前闭后闭的数组,明确边界的问题
  • 复制数组时始终要记住有一个L的偏移量
private static void merge(Comparable[] arr, int l, int mid, int r) {

        //Comparable[] aux = Arrays.copyOfRange(arr, l, r+1);
        Comparable[] aux = new Comparable[r-l+1];
        for(int i = l; i <= r; i ++){
            aux[i-l] = arr[i];
        }
        //    l...mid区间和mid+1...r区间
        int i = l, j = mid+1;
        for(int k = l; k <= r; k++){
            if(i > mid){        // 如果左半部分元素已经全部处理完毕
                arr[k] = aux[j-l];
                j ++;
            }else if(j > r){       // 如果右半部分元素已经全部处理完毕
                arr[k] = aux[i-l];
                i ++;
            }else if(aux[i-l].compareTo(aux[j-l]) < 0){
                arr[k] = aux[i-l];
                i ++;
            }else {
                arr[k] = aux[j-l];
                j ++;
            }
        }
    }


    //递归使用归并排序,对arr[l..r]的范围进行排序
    private static void sort(Comparable[] arr, int l, int r){

        if(l >= r)  return;

        int mid = (r-l)/2 + l;
        sort(arr, l, mid);
        sort(arr, mid+1, r);
        merge(arr, l, mid, r);
    }

    public static void sort(Comparable[] arr){

        int n = arr.length;
        sort(arr, 0, n-1);
    }

(4)归并与插入比较

对于无序数组来说,归并肯定好

对于近乎有序的数组,数组越有序,插入排序的时间性能越趋近于O(n),比归并排序高效

三、归并优化

(1)优化一

        所有的排序算法中都存在一种优化,就是递归到底优化。,当递归元素较少时,可以用插入排序来提高性能

  • 当待排序的数组元素较少时,近乎有序的情况概率较大,此时插入排序有优势。
  • 虽然插入排序的时间复杂度是O(n^2)级别,而归并排序是O(n*logn),但是别忽视这两者都依赖于常数系数n,当n较小时,插入排序是稍快于归并排序

所以,在此优化中,在一开始判断递归到底的情况下,设定一定的值(这里设定15),剩下的数组采用插入算法进行排序。

(2)优化二

        在merge中,并没有对左右两个部分进行判断在归并,而是一律归并,当左部分的最后一个值小于右部分第一个值的话,此时压根就不需要归并,真个数组都是有序的,直接跳过即可~

注意:归并必须要对logN层进行递归,只是每次发现不需要递归退出来,无法退化成O(N)的算法~

对于改进,数组中存在有序会有一定的效果,但也会阻碍(if语句本身消耗),但总体不打

四、优化后的代码

总之,就是对sort函数进行优化~

private static void sort(Comparable[] arr, int l, int r){
        // 优化1,小规模用插入
        if( r - l <= 15){
            InsertionSortoptimize.sort(arr, l, r);
            return;
        }

        int mid = (r-l)/2 + l;
        sort(arr, l, mid);
        sort(arr, mid+1, r);

        // 优化2,对于已经有序不进行merger
        if(arr[mid].compareTo(arr[mid+1]) > 0){
            merge(arr, l, mid, r);
        }

    }
实验证明,确实是比较好,这种优化更加实用与几乎有序的数组排序~


相关标签: 排序 归并排序