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

归并排序(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 条评论
登录 后参与评论

相关文章

来自专栏恰同学骚年

剑指Offer面试题:31.两个链表的第一个公共节点

  碰到这道题,很多人的第一反应就是蛮力法:在第一链表上顺序遍历每个结点,每遍历到一个结点的时候,在第二个链表上顺序遍历每个结点。如果在第二个链表上有一个结点和...

471
来自专栏desperate633

LintCode 二叉树中的最大路径和题目分析代码

给出一棵二叉树,寻找一条路径使其路径和最大,路径可以在任一节点中开始和结束(路径和为两个节点之间所在路径上的节点权值之和)

592
来自专栏desperate633

LeetCode 25. Reverse Nodes in k-Group分析代码

我们设计一个翻转k的算法 head -> n1 -> n2 ... nk -> nk+1 => head -> nk -> nk-1 .. n1 -> nk...

852
来自专栏小樱的经验随笔

平面上给定n条线段,找出一个点,使这个点到这n条线段的距离和最小。

题目:平面上给定n条线段,找出一个点,使这个点到这n条线段的距离和最小。 源码如下: 1 #include <iostream> 2 #include ...

2434
来自专栏python学习路

数据结构与算法(二)

排序与搜索 排序算法(英语:Sorting algorithm)是一种能将一串数据依照特定顺序进行排列的一种算法。 排序算法的稳定性 稳定性:稳定排序算法会让原...

3078
来自专栏java初学

dfs

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

二叉树性质

•【性质1】在二叉树的第i层上最多有2i-1个结点(i>=1)。 【性质2】深度为k的二叉树至多有2k –1个结点(k>=1)。 •【特别】一棵深度为k且有2k...

2416
来自专栏用户画像

7.7.5 最佳归并树

文件经过置换-选择排序之后,得到的是长度不等的初始归并段。下面讨论如何组织初始归并段的归并顺序,使I/O访问次数最少。

441
来自专栏郭耀华‘s Blog

数据结构二叉树知识点总结

术语  1. 节点的度:一个节点含有的子树的个数称为该节点的度; 2. 叶节点或终端节点:度为零的节点;  3. 非终端节点或分支节点:度不为零的节点;  4....

26513
来自专栏我的博客

选择排序

分类: 选择排序(选择排序,堆排序,平滑排序,笛卡尔树排序,锦标赛排序,圈排序) 思想: 1、从左至右遍历,找到最小(大)的元素,然后与第一个元素交换。 2、从...

3078

扫码关注云+社区