美文网首页
归并排序算法

归并排序算法

作者: StormZhu | 来源:发表于2018-08-07 22:26 被阅读0次

基本思想

归并排序采用的是分治算法的思想,其中最重要的操作就是归并操作。

主要思想是,将数组平分为A,B两部分,分别将A,B两部分排好序,然后再合并,对A排序的时候,也是同样的思路,将A分为两份,同样先分别排序,再合并。一直递归下去,直到不能再分解为止。

网上看到一张图很好的解释了这个过程:

归并算法过程.png

再用动画展示一下这个过程:


归并过程动画.gif

归并过程

假设数组已经被分解成了两个有序的数组,这个时候就应该将这两个有序数组合并成一个新的有序数组。这个时候需要额外的存储空间来辅助这个归并过程(所以归并排序不是原地排序)。

下面来张图展示这个过程:

归并过程.png

代码实现--递归版

#include <iostream>
using namespace std;

template<typename T>
void mergeSort(T arr[], int n){
    // 一次性申请aux空间,
    // 并将这个辅助空间以参数形式传递给完成归并排序的各个子函数
    T *aux = new T[n];

    __mergeSort( arr , aux, 0 , n-1 );

    delete[] aux;   // 使用C++, new出来的空间不要忘记释放掉:)
}

// 使用优化的归并排序算法, 对arr[l...r]的范围进行排序
// 其中aux为完成merge过程所需要的辅助空间
template<typename T>
void __mergeSort(T arr[], T aux[], int l, int r){
    // 递归的终点 数组只剩一个元素的时候就可以停止了
    if( l >= r ){
        return;
    }

    int mid = l + (r-l)/2;
    __mergeSort(arr, aux, l, mid);
    __mergeSort(arr, aux, mid+1, r);
    __merge(arr, aux, l, mid, r);
}

// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
// 其中aux为完成merge过程所需要的辅助空间
template<typename  T>
void __merge(T arr[], T aux[], int l, int mid, int r){
    // 将原数组的数据复制给aux
    for( int i = l ; i <= r; i ++ )
        aux[i] = arr[i];

    // 初始化,i指向左半部分的起始索引位置l;j指向右半部分起始索引位置mid+1
    int i = l, j = mid+1;
    for( int k = l ; k <= r; k ++ ){
        if( i > mid ){  // 如果左半部分元素已经全部处理完毕
            arr[k] = aux[j]; j ++;
        }
        else if( j > r ){  // 如果右半部分元素已经全部处理完毕
            arr[k] = aux[i]; i ++;
        }
        else if( aux[i] < aux[j] ) {  // 左半部分所指元素 < 右半部分所指元素
            arr[k] = aux[i]; i ++;
        }
        else{  // 左半部分所指元素 >= 右半部分所指元素
            arr[k] = aux[j]; j ++;
        }
    }
}

结论

归并排序总的平均时间复杂度为O(nlogn),最好,最坏,平均时间复杂度均为O(nlogn)。所以归并排序是稳定的排序算法,缺点是需要额外的存储空间(貌似也有原地归并排序,无需额外存储空间,待研究)。

我的segmentfault链接

参考

  1. 图解排序算法(四)之归并排序
  2. 慕课网算法与数据结构课程

相关文章

  • 2018-06-30

    排序算法之归并排序 归并排序算法是排序算法中的经典算法之一,其核心思想是利用归并的思想实现的排序方法,该算法采用经...

  • java实现快速排序、归并排序、希尔排序、基数排序算法...

    快速排序算法 归并排序算法 希尔排序算法 基数排序算法

  • 排序算法之归并排序

    归并排序(Merge Sort) 归并排序是利用归并的思想实现排序的方式,该算法采用的是经典的分治算法 归并排序过...

  • 归并排序

    图解排序算法(四)之归并排序 基本思想 归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用...

  • 归并排序

    归并排序 这个排序算法是建立在归并操作上的一种有效的排序算法,算法主要采用分治法,归并排序的算法复杂度为O(n*l...

  • 第三章:高级排序算法

    归并排序算法(mergeSort) 算法思想:Python使用函数实现: 自底向上的归并排序算法 算法思想:Pyt...

  • 算法入门——归并排序、希尔排序

    上篇文章我们学习了算法入门——堆排序,这篇文章我们学习算法入门——归并排序、希尔排序。 归并排序 归并排序是将一个...

  • 归并算法

    归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。归并算法的中心是归并两...

  • web开发需要知道的几个算法

    算法分类 快速排序算法 深度优先算法 广度优先算法 堆排序算法 归并排序算法

  • iOS - 归并排序

    Demo_github 归并排序: 归并排序(Merge Sort)是建立在归并操作上的一种有效的排序算法,算法主...

网友评论

      本文标题:归并排序算法

      本文链接:https://www.haomeiwen.com/subject/qsezvftx.html