归并排序详解 和逆序数计算

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。(摘自baidu)

归并排序的核心思想是将两个已经排序的序列合并成一个序列,那如何得到两个已经排序的序列呢?我们知道, 如果一个序列只有一个元素,那该序列是已经排序的,这样我们就可以利用分治的思想,将未排序的序列划分成更小的序列,只到我们可以很方便的对小序列进行排序(比如划分到序列只有一个元素, 或者序列很小可以方便的使用其它排序算法进行排序),然后再将小序列逐次合并,得到最后的排序结果。(csdn

归并排序的效率是比较高的,设数列长为N,将数列分开成小数列一共要logN步,每步都是一个合并有序数列的过程,时间复杂度可以记为O(N),故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作,所以归并排序在O(N*logN)的几种排序方法(快速排序,归并排序,希尔排序,堆排序)也是效率比较高的。(白话经典算法

第一步是递归实现数组的不断分割知道只有一个元素;

void mergesort(int a[], int first, int last)
{
    if (first < last)
    {
        int mid = (first + last) / 2;
        mergesort(a, first, mid);    //左边有序
        mergesort(a, mid+1, last); //右边有序
        merge(a, first, mid, last); //再将二个有序数列合并
    }
}

  要注意的是mid+1这个细节

然后对分割后的进行合并,相当于递归过程中值的返回过程

1+1=2

2+2=4;

成对成对的合并

一直到原来的数组大小,长度是非偶数时,假设为3,会被分成一个长度为1的和一个长度为2的数组;

void merge(int a[], int first, int mid, int last)
{
    int i = first, j = mid + 1;
    int m = mid,   n = last;
    int k = 0;
    int temp[maxn];
    while (i <= m && j <= n)
    {
        ope_num++;
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }

    while (i <= m)
        temp[k++] = a[i++];

    while (j <= n)
        temp[k++] = a[j++];

    for (i = 0; i < k; i++)
        a[first + i] = temp[i];
}

  要注意把剩下的的归并进去;

合成代码是:

#include <bits/stdc++.h>
using namespace std;
#define maxn 200000
int n;
int ope_num=0;
int wosort_num=0;
void merge(int a[], int first, int mid, int last)
{
    int i = first, j = mid + 1;
    int m = mid,   n = last;
    int k = 0;
    int l=mid-first;
    int temp[maxn];
    while (i <= m && j <= n)
    {
        ope_num++;
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
        {
            temp[k++] = a[j++];
            wosort_num+=(l-i+first);
        }

    }

    while (i <= m)
        temp[k++] = a[i++];

    while (j <= n)
        temp[k++] = a[j++];

    for (i = 0; i < k; i++)
        a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last)
{
    if (first < last)
    {
        int mid = (first + last) / 2;
        mergesort(a, first, mid);    //左边有序
        mergesort(a, mid+1, last); //右边有序
        merge(a, first, mid, last); //再将二个有序数列合并
    }
}
int main()
{
    int a[maxn];
    memset(a,0,sizeof(a));
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    mergesort(a,0,n);
    for(int i=1;i<=n;i++)
    {
        if(i-1) cout<<" ";
        cout<<a[i];
    }
    cout<<endl;
    cout<<wosort_num<<endl;//这是求逆序数
    cout<<ope_num<<endl;//这是求比较次数
}

  本代码顺便把常见的两种问题,求逆序数和比较次数给带入了,可以看看。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏猿人谷

判断单链表是否存在环

周末参加完美世界校园招聘中就有一道判断单链表是否有环的编程题。 写一个C/C++函数,来判断一个单链表是否具有环,如果存在环,则给出环的入口点。 有一个单链表,...

1819
来自专栏Java帮帮-微信公众号-技术文章全总结

04-02.总结switch,for,while,do。while跳转语句

(4)do...while循环 A:基本格式 do { 循环体语句; }while(判断条件语句); 扩展格式: 初始化语句; do { 循环体语...

3574
来自专栏数据结构与算法

洛谷P1138 第k小整数

题目描述 现有n个正整数,n≤10000,要求出这n个正整数中的第k个最小整数(相同大小的整数只计算一次),k≤1000,正整数均小于30000。 输入输出格式...

3166
来自专栏小小挖掘机

一招解决4道leetcode hard题,动态规划在字符串匹配问题中的应用

在做leetcode的时候,遇到hard题大家往往都觉得头疼,但其实,掌握方法,举一反三,hard题有时候我们也能想到好的思路,顺利攻破,今天我们就介绍一下动态...

1.1K5
来自专栏IMWeb前端团队

JavaScript强化教程——sort() 方法

本文作者:IMWeb 王军 原文出处:IMWeb社区 未经同意,禁止转载 本文为 H5EDU 机构官方 HTML5培训 教程,主要介绍:JavaScr...

1775
来自专栏机器学习算法全栈工程师

归并排序

作者:柳行刚 编辑:徐 松 基本思想 归并排序是建立在二路归并和分治法的基础上的一个高效排序算法,将已有序的子序列合并,得到完全有序的序列;即先使...

35410
来自专栏算法channel

Pandas|排序,分组,组内排序

01 Pandas的基本排序 Pandas的主要数据结构有2个:DataFrame,Series,针对这两个类型的排序Demo如下: #coding=utf-...

6264
来自专栏数据结构与算法

2144 砝码称重 2

 时间限制: 1 s  空间限制: 16000 KB  题目等级 : 钻石 Diamond 题解 题目描述 Description 有n个砝码,现在要称一个质量...

3506
来自专栏Vamei实验室

Python基础09 面向对象的进一步拓展

我们熟悉了对象和类的基本概念。我们将进一步拓展,以便能实际运用对象和类。 调用类的其它信息 上一讲中提到,在定义方法时,必须有self这一参数。这个参数表示某个...

1867
来自专栏撸码那些事

【图解数据结构】 树

983

扫码关注云+社区