归并排序

简介:

归并:将两个或两个以上的有序表组合成一个新的有序表

2-路 归并排序

排序过程

  1. 初始序列看成n个有序子序列,每个子序列长度为1

  2. 两两合并,得到n/2个长度为2或1的有序子序列

  3. 再两两合并,重复直至得到一个长度为n的有序序列为止

这里写图片描述

  void Merge(RedType R[],RedType &T[],int low,int mid,int high)
  {
          i=low;j=mid+1;k=low;

          while(i<=mid&&j<=high)
{
      if(R[i].key<=R[j].key) T[k]=R[i++];

     else T[k]=R[j++];
}
        while(i<=mid)

        T[k++]=R[i++];

         while(j<=high)

         T[k++]=R[j++];
}

算法分析时间效率:O(nlog2n)

空间效率:O(n)

稳定性:稳定

排序算法比较

1.为避免顺序存储时大量移动记录的开销,可以考虑用链式作为存储结构
直接插入排序、归并排序

2.不宜采用链式作为存储结构的
折半插入排序、希尔排序、快速排序、堆排序

排序算法选择规则

n较大时

(1)分布随机,稳定性不做要求,则采用快速排序

(2)内存允许,要求排序稳定时,则采用归并排序

(3)可能会出现正序或逆序,稳定性不做要求,则采用堆排序或归并排序

n较小时

(1)基本有序,要求稳定,则采用直接插入排序

(2)分布随机,稳定性不做要求,则采用直接选择排序,若排序码不接近逆序,也可以采用直接插入排序。

目录
相关文章
|
6月前
归并排序详解
归并排序详解
56 1
|
人工智能 BI
归并排序
归并排序。
44 0
|
5月前
|
算法 搜索推荐 Java
归并排序就是这么容易
归并排序就是这么容易
40 2
|
6月前
|
搜索推荐
归并排序是什么
归并排序是什么
20 归并排序
20 归并排序
42 0
|
存储 算法 搜索推荐
归并排序(看了就会)
归并排序(看了就会)
|
搜索推荐 算法 C#
C#——归并排序
C#——归并排序
152 0
|
算法
归并排序及小和问题(中)
归并排序及小和问题(中)
158 1
归并排序及小和问题(中)
|
算法
【2. 归并排序】
归并与快排不同: >快速排序: >- 分界点是随机数组里面的一个`数`来分,使得左边都是<= 这个数,右边 >= 这个数 (`数值`) >- 先分完,在分别递归俩边 > >归并排序: >- 先递归俩边,在进行合并操作 >- 分界点是`整个数组中间的位置`(`下标值`)
95 0
【2. 归并排序】