归并排序【模板】

简介:

模板直接见代码:

#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月前
|
算法
二分 模板
二分的另一个板子
34 1
|
5月前
|
Java Python
二分查找模板
二分查找模板
|
5月前
|
算法 搜索推荐 C++
【洛谷 P1177】【模板】快速排序 题解(快速排序+数组索引)
**快速排序模板题目**,要求使用快排算法对输入的整数序列进行排序。输入包含正整数N和N个整数,输出排序后的序列。20%的数据N≤10^3,所有数据N≤10^5。代码中提供了一种实现,包括读取输入、定义partition函数划分数组、递归调用quickSort及主函数执行排序和输出。注意C++选手避免使用STL的`sort`。
25 0
|
6月前
|
Python
{二分模板}
{二分模板}
23 0
|
机器学习/深度学习
P1873 砍树(二分查找模板)
P1873 砍树(二分查找模板)
109 0
|
机器学习/深度学习 人工智能 搜索推荐
P1177 【模板】快速排序(二分排序)
P1177 【模板】快速排序(二分排序)
77 0
|
编译器 C语言 C++
C++ 冒泡排序,模板
C++ 冒泡排序,模板
二分搜索的三种模板
二分搜索的三种模板
66 0
二分查找(my理解和模板)
之前先学了y总的二分,后来又看了代码随想录的,感觉代码随想录的更好记忆
97 0
ACM模板——排序 - 归并排序
ACM模板——排序 - 归并排序
110 0
ACM模板——排序 - 归并排序