归并排序【模板】

简介:

模板直接见代码:

#include <iostream>
using namespace std;

const long M=999999999;

void Merge(int A[],long Left,long Middle,long Right)
{
    long n1=Middle-Left+1;
    long n2=Right-Middle;

    int *L = new int[n1+2]; //预留空间
    int *R = new int[n2+2];

    long i,k;
    //分成左右数组
    for(i=1;i<=n1;i++)
        L[i]=A[Left+i-1];
    for(i=1;i<=n2;i++)
        R[i]=A[Middle+i];

    L[n1+1]=M; //哨兵
    R[n2+1]=M;

    i=1;
    long j=1;
    for(k=Left;k<=Right;k++)
    {
        //如果某一边先抵达哨兵,另一边一定是小于的
        if(L[i]<=R[j])
            A[k]=L[i++];

        else
            A[k]=R[j++];
    }

    delete L,R;
}

void Merge_sort(int A[],long Left,long Right)
{
    long Middle;
    if(Left<Right)
    {
        Middle=(Left+Right)/2; 
        Merge_sort(A,Left,Middle);  // 二分分解左部分
        Merge_sort(A,Middle+1,Right); // 二分分解有部分
        Merge(A,Left,Middle,Right); //合并两部分
    }
}

int main() 
{
    int array[10] = {4,5,7,1,22,33,8,10,23,199};

    Merge_sort(array,0,9);

    for(int i=0;i<10;++i) {
        cout<<array[i]<<" ";
    }

    return 0; 
}

运行结果:

1 4 5 7 8 10 22 23 33 199

相关文章
|
4月前
|
算法
二分 模板
二分的另一个板子
35 1
|
5月前
|
Java Python
二分查找模板
二分查找模板
|
6月前
|
Python
{二分模板}
{二分模板}
24 0
|
6月前
线段树模板
线段树模板
45 0
|
机器学习/深度学习
P1873 砍树(二分查找模板)
P1873 砍树(二分查找模板)
123 0
|
机器学习/深度学习 人工智能 搜索推荐
P1177 【模板】快速排序(二分排序)
P1177 【模板】快速排序(二分排序)
80 0
|
编译器 C语言 C++
C++ 冒泡排序,模板
C++ 冒泡排序,模板
二分搜索的三种模板
二分搜索的三种模板
67 0
|
存储 算法
线段树模板与练习
线段树模板与练习
101 0