美文网首页
[算法导论]归并排序

[算法导论]归并排序

作者: wenfh2020 | 来源:发表于2019-11-29 11:56 被阅读0次

时间复杂度

《算法导论》2.3.1 分治法。

归并排序采用了分治法的递归排序。分治法:分解子问题,解决子问题,合并子结果。

分解:分解待排序的 n 个元素的序列各成 \frac{n}{2} 个元素的子列。

解决:使用归并排序递å归地排序两个子序列。

合并:合并两个已排序的子序列以产生已排序的答案。

因为排序数组会被 \frac{n}{2} 拆开,归并排序时间复杂度稳定的 nlgn

算法深度

相对于其它的 nlgn 排序,它需要额外的临时空间辅助,有一定的资源损耗。小数量级(百万级别)的排序,要比快速排序慢。但是大数量级数据(千万级别),因为归并排序树深最小,排序比快速排序快。

快速排序,最优算法复杂度,数组会被 \frac{n}{2} 拆开。实际操作中数据很难达到最优。而归并一直都是通过 \frac{n}{2} 进行拆分。


算法

算法导论实现思想

  1. 拆分左右两个临时数组,临时数组最后是一个∞无穷大的数字。
  2. 两个子数组进行比较,小的数值会拷贝到原数组。
算法
归并

实现

实际实现,通过一个辅助数组进行实现(源码)。

void merge_sort(int array[], int start, int mid, int end) {
    int k = 0;
    int low = start;
    int high = mid + 1;
    int* temp = (int*)malloc(sizeof(int) * (end - start + 1));
    
    while (low <= mid && high <= end) {
        (array[low] < array[high]) ? temp[k++] = array[low++]
                                   : temp[k++] = array[high++];
    }

    while (high <= end) temp[k++] = array[high++];
    while (low <= mid) temp[k++] = array[low++];
    for (int i = 0; i < k; i++) array[start + i] = temp[i];

    free(temp);
}

void merge(int array[], int start, int end) {
    if (start >= end) {
        return;
    }

    int mid = (start + end) / 2;
    merge(array, start, mid);
    merge(array, mid + 1, end);
    merge_sort(array, start, mid, end);
}

实现流程

数组 A = {5, 2,4,7, 1, 3, 2, 6} 子数组最后一次合并排序流程。


实现流程

参考

快速排序、归并排序、堆排序三种算法性能比较
《算法导论》(第三版)


更精彩内容,请关注我的博客:https://wenfh2020.com

相关文章

  • 计数排序、基数排序和桶排序

    阅读经典——《算法导论》07 到目前为止,我们已经介绍了插入排序、归并排序、堆排序、快速排序这四种排序算法,他们的...

  • 堆排序

    阅读经典——《算法导论》05 本文介绍一种神奇的排序方法:堆排序。 堆排序不像插入排序和归并排序那样直观,它利用了...

  • 2018-06-30

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

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

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

  • 排序算法之归并排序

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

  • 算法导论-归并排序

    1.伪代码 MERGE算法图示 2.Python代码 result: 循环不变性对于归并算法 初始化: 在循环之前...

  • [算法导论]归并排序

    时间复杂度 《算法导论》2.3.1 分治法。 归并排序采用了分治法的递归排序。分治法:分解子问题,解决子问题,合并...

  • 归并排序【算法导论】

    注:学习算法导论,按照标准伪代码理解翻译为java实现,如有兴趣理解整个过程的细节,建议阅读《算法导论》第二章:2...

  • 归并排序

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

  • 归并排序

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

网友评论

      本文标题:[算法导论]归并排序

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