归并排序
麦兜 / 2019-07-28 / 算法 / 阅读量 399

归并排序核心:分解 合并

首先了解它是如何合并元素就很容易去了解这个算法
分解步骤:
1.png
数组两边都是有序的子数组,然后需要把他们拆分开
2.png


合并的步骤:
1、定义三个变量 i、j、k i指向Arr1的第一个元素 j指向Arr2的第一个元素 K指向 数组第一个元素
2、让arr1[i]和arr2[j]比较大小 顺序取小 逆序取大
3、如果arr1[i]<arr2[j] 就把arr1[i]这个元素放在arr3[3]里面
4、然后维护一下下标 如果取arr1[i]元素 i++ 如果取arr2[j]元素 j++ 然后k因为也添加元素了维护一下 k++往后移
3.png
4.png
5.png
6.png
7.png
完事!!!!


但是 别忘了 这是两边排序好的。 如果是顺序乱的呢(当然是排序啦

1、首先分解 把他分解成还剩一个元素 再合并。(只有一个元素 当然是排序好的了)
8.png

代码示例:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
/*合并*/
void merger(int arr[],int L,int M,int R)
{
    int leftsize = M - L;
    int rightsize = R - M + 1;
    int *left = new int[leftsize];
    int *right = new int[rightsize];
    for (int i = L; i < M; i++)
    {
        left[i - L] = arr[i];
    }
    for (int j = M; j <=R; j++)
    {
        right[j - M] = arr[j];
    }

    /*大小比较合并*/
    int i = 0; int j = 0; int k = L;
    while (i < leftsize&&j < rightsize)
    {
        if (left[i] <right[j])
        {
            arr[k] = left[i];
            i++;
            k++;
        }
        else {
            arr[k] = right[j];
            j++;
            k++;
        }
    }
    /*剩余的合并*/
    while (i < leftsize)
    {
        arr[k] = left[i];
        i++;
        k++;
    }
    while (j < rightsize)
    {
        arr[k] = right[j];
        j++;
        k++;
    }
}
/*分解合并*/
void mergersort(int arr[], int L, int R)
{
    if (L == R) 
        return;
    /*砍一半*/
    int M = (L + R) / 2; 
    mergersort(arr, L, M);
    mergersort(arr, M+1,R);
    merger(arr, L, M+1, R);
}
int main()
{
    int arr[] = { 2,5,1,3,4};
    mergersort(arr,0, 4);
    for (int i = 0; i <=4; i++)
    {
        cout << arr[i];
    }

    return 0;
}
1 + 8 =
快来做第一个评论的人吧~