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

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

相关文章

来自专栏机器学习入门

挑战程序竞赛系列(90):3.6凸包(1)

挑战程序竞赛系列(90):3.6凸包(1) 传送门:POJ 2187: Beauty Contest 题意: 平面上有N个牧场。i号牧场的位置在格点(xi,y...

2187
来自专栏无题

链式存储线性表(LinkedList)数据结构解析

LinkedList内部是通过链表来实现的 一、节点分析 LinkedList内部是通过链表来实现的,那么就少不了节点,所以在源码中必然能找到这样一个节点。 ...

3266
来自专栏学海无涯

16.Swift学习之结构体

692
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题22栈的压入、弹出序列

本题的详细分析过程均在代码的注释中: import java.util.Stack; /** * 题目:输入两个整数序列,第一个序列表示栈的压入顺序,请判断...

2917
来自专栏武培轩的专栏

剑指Offer-栈的压入、弹出序列

题目描述 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压...

3327
来自专栏个人随笔

房上的猫:StringBuffer类

一.使用StringBuffer类  StringBuffer类位于java.lang包中,是String类的增强类  步骤:   1.声明StringBuff...

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

13(01)总结StringBuffer,StringBuilder,数组高级,Arrays,Integer,Character

1:StringBuffer(掌握) (1)用字符串做拼接,比较耗时并且也耗内存,而这种拼接操作又是比较常见的,为了解决这个问题,Java就提供了 一...

3935
来自专栏禁心尽力

Java Collection开发技巧

Java Collection(集合) ? 集合中的一些技巧: 通过Collections类的静态方法,可以对集合进行一些操作 1 java....

21510
来自专栏noteless

[五]基础数据类型之Short详解

3473
来自专栏郭耀华‘s Blog

Java集合框架(四)—— Queue、LinkedList、PriorityQueue

Queue接口   Queue用于模拟了队列这种数据结构,队列通常是指“先进先出”(FIFO)的容器。队列的头部保存在队列中时间最长的元素,队列的尾部保存...

3456

扫码关注云+社区