#2 归并排序算法的简单分析

作者: 遇事不决_可问春风 | 来源:发表于2018-06-23 19:49 被阅读5次

简介

归并排序是一种使用分治策略的排序算法,相比于之前介绍的插入排序算法,分治算法在数据量较大的场景中速度要快很多(在本文最后会比价两个算法的优劣)

算法原理简述

合并两个已经排好序的数组

首先想象一下你的面前摆放着两堆自上而下已经从大倒小排好序的扑克牌, 你现在要把这两堆扑克牌按照从大到小的顺序合并成一堆, 你需要先拿起牌堆一和牌堆二顶上的一张牌, 然后对比大小, 把小的哪一张放到手中, 大的哪一张放回到原来的牌堆, 重复上面的步骤, 直到其中一堆牌全部被放到手上后, 把另一堆牌堆的所有牌依次追加到手中(说的有点繁琐, 最好能自己按照上面的步骤试一下, 能够更快的理解).

图解

归并排序合并步骤.png

C++ 代码

// 合并两个排好序的子数组
// A: 处理的数组
// p: 子数组的起始
// q: 子数组的中点
// r: 子数组的结尾
void merge(int * A,int p, int q, int r){
    
    // 获取左边子数组的长度
    int n1 = q - p + 1;

    // 获取右边子数组的长度
    int n2 = r - q;
    
    // 创建一个新的数组保存左边的子数组
    int * L = new int[n1];
    
    // 创建一个新的数组保存右边的子数组
    int * R = new int[n2];
    
    // 保存左边的子数组到数组 L
    for(int i = 0; i<n1; i++){
        L[i] = A[p+i];
    }
    
    // 保存右边的子数组到数组 R
    for(int j =0; j<n2; j++){
        R[j] = A[q+j+1];
    }

    // 记录数组 L 和 R 被取出元素的数量
    // 防止数组越界
    int L_sum = 0;
    int R_sum = 0;

    // 将 L 和 R 排序保存到主数组中
    for(int k=p; k<=r; k++){

        // 如果左边数组 (L) 的当前元素 < 右边数组 (R) 的当前元素
        // 并且左边的数组还没有越过边界
        // 则将 (L) 的当前元素追加到子数组中
        if(L[L_sum] < R[R_sum] && L_sum < n1){
            A[k] = L[L_sum];
            L_sum++;
        }
        // 如果右边数组 (R) 还没有越界
        // 则将 (R) 的当前元素追加到子数组中
        else if(R_sum < n2){
            A[k] = R[R_sum];
            R_sum++;
        }
        // 否则将数组 (L) 追加到子数组中
        else{
            A[k] = L[L_sum];
            L_sum++;
        }
    }
}

伪码

MERGE(A, p, q, r)
    n1 = q - p + 1
    n2 = r - q
    let L[1..n1 + 1] and R[1..n2 + 1] be new arrays
    for i = 1 to n1
        L[i] = A[p + i - 1]
    for j = 1 to n2
        L[j] = A[q + j]

    // 添加哨兵, 防止数组越界
    L[n1 + 1] = MAX
    L[n2 + 1] = MAX

    i = 1
    j = 1
    
    for k = p to r
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else A[k] = R[j]
            j = j + 1

分解大数组为小数组并递归的求解他们

一般环境下除了合并两个排好序的数组之外更多的是排序一个无序的数组,这里聊一下怎么利用上面的那个算法来处理排序一个无序数组(语言表达能力不好,直接看图吧, 方便起见, 这里使用 23 个数据为例)

图解

归并排序递归求解子问题合并步骤.png

C++ 代码

// 分解一个大的数组
// A: 数组
// p: 子数组的起始
// r: 子数组的结尾
void merge_sort(int * A,int p, int r){
   
    // 当子数组为 1 的时候停止递归
    if(p < r){
        // 得到当前子数组的中点
        int q = floor((p+r)/2);

        // 递归的去分解前半段子数组
        merge_sort(A, p, q);

        // 递归的去分解后半段子数组
        merge_sort(A, q+1, r);
        
        // 将子数组合并
        merge(A, p, q, r);
    }
}

伪码

MERGE-SORT(A, p, q)
    if p < r
        q = ⌊(p + r) / 2⌋
        MERGE-SORT(A, p, q)
        MERGE-SORT(A, q + 1, r)
        MERGE(A, p, q, r)

完整归并排序 C++ 代码

/*************************************************************************
> File Name: sf2.cpp
> Author: 
> Mail: 
> Created Time: 2018年06月05日 星期二 00时01分49秒
************************************************************************/
#include<iostream>
#include<math.h>
using namespace std;


// 合并两个排好序的数组
void merge(int * A,int p, int q, int r);

// 分解一个大的数组
void merge_sort(int * A,int p, int r);

int main(){

    // 测试数据
    int A[9] = {10,9,8,6,5,3,1,2,4};
    
    // 数组的起始 
    int p = 0;
    // 数组的结尾
    int r = 8;

    // 打印测试数据
    cout << "测试数据: ";
    for(int i = 0; i<=r; i++){
        cout << A[i] << " ";
    }
    cout << endl;

    // 排序入口
    merge_sort(A, p, r);

    // 打印运行结果
    cout << "运行结果: ";
    for(int i = 0; i<=r; i++){
        cout << A[i] << " ";
    }
    return 0;
}

// 合并两个排好序的子数组
// A: 处理的数组
// p: 子数组的起始
// q: 子数组的中点
// r: 子数组的结尾
void merge(int * A,int p, int q, int r){
    
    // 获取左边子数组的长度
    int n1 = q - p + 1;

    // 获取右边子数组的长度
    int n2 = r - q;
    
    // 创建一个新的数组保存左边的子数组
    int * L = new int[n1];
    
    // 创建一个新的数组保存右边的子数组
    int * R = new int[n2];
    
    // 保存左边的子数组到数组 L
    for(int i = 0; i<n1; i++){
        L[i] = A[p+i];
    }
    
    // 保存右边的子数组到数组 R
    for(int j =0; j<n2; j++){
        R[j] = A[q+j+1];
    }

    // 记录数组 L 和 R 被取出元素的数量
    // 防止数组越界
    int L_sum = 0;
    int R_sum = 0;

    // 将 L 和 R 排序保存到主数组中
    for(int k=p; k<=r; k++){

        // 如果左边数组 (L) 的当前元素 < 右边数组 (R) 的当前元素
        // 并且左边的数组还没有越过边界
        // 则将 (L) 的当前元素追加到子数组中
        if(L[L_sum] < R[R_sum] && L_sum < n1){
            A[k] = L[L_sum];
            L_sum++;
        }
        // 如果右边数组 (R) 还没有越界
        // 则将 (R) 的当前元素追加到子数组中
        else if(R_sum < n2){
            A[k] = R[R_sum];
            R_sum++;
        }
        // 否则将数组 (L) 追加到子数组中
        else{
            A[k] = L[L_sum];
            L_sum++;
        }
    }
}

// 分解一个大的数组
// A: 数组
// p: 子数组的起始
// r: 子数组的结尾
void merge_sort(int * A,int p, int r){
   
    // 当子数组为 1 的时候停止递归
    if(p < r){
        // 得到当前子数组的中点
        int q = floor((p+r)/2);

        // 递归的去分解前半段子数组
        merge_sort(A, p, q);

        // 递归的去分解后半段子数组
        merge_sort(A, q+1, r);
        
        // 将子数组合并
        merge(A, p, q, r);
    }
}

简单分析一下归并排序的时间复杂度

方便起见, 这里使用 2N 个数据为例, 首先我们定义一个变量 N 代表 常量 C 代表分解步骤与处理每个数组元素需要的时间的和(这里可能不是非常准确,但是不妨碍我们求解归并排序算法的最差运行时间, 只是多算了一些分解数组的时间)

下图图示了归并排序的归并树, 每一层的代价为 CN 一共有 log2N + 1, 所有的代价和为 T(N) = CN * log2N + CN, 使用大 O 记号去掉常量和低阶项得到该算法时间复杂度O(N * log2N)

image.png

相关文章

  • 6-十大排序篇二

    十大排序(2) 今天先学习第二大类排序算法 归并排序 排序排序 希尔排序 堆排序 1.归并排序 分析:利用归并的思...

  • 归并排序

    归并排序 动图演示 思路分析 归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用...

  • 基本排序算法

    冒泡算法 简单选择排序 堆排序 快排 归并排序

  • 2018-06-30

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

  • 数据结构与算法--归并排序

    数据结构与算法--归并排序 归并排序 归并排序基于一种称为“归并”的简单操作。比如考试可能会分年级排名和班级排名,...

  • 排序算法之归并排序

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

  • 看图说话排序算法之归并排序

    归并排序和快速排序类似,都典型以递归方式实现的算法,归并排序的时间复杂度分析也和快速排序的时间复杂度分析类似。本文...

  • #2 归并排序算法的简单分析

    简介 归并排序是一种使用分治策略的排序算法,相比于之前介绍的插入排序算法,分治算法在数据量较大的场景中速度要快很多...

  • 常见排序算法

    1 前言 2 排序基础2.1 选择排序2.2 插入排序 3 高级排序算法3.1 归并排序3.1.1 插入排序与归并...

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

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

网友评论

    本文标题:#2 归并排序算法的简单分析

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