二路归并算法

布满荆棘的人生 2022-06-03 02:48 143阅读 0赞

归并算法到底是什么意思 呢？听到归并就知道其实是把数组进行合并，那么我们合并的时候肯定有什么特征。  
首先我们归并的目标是数组，由于是二路归并，那么我们是有2个数组需要合并，并且这2个数组是有序的。如果说我们是从小到大进行排序。那么这2个数组都是从小到大有序的。

现在的问题是如果我们拿到一个无序数组是怎么样得到我们的有序数组在开始第一轮合并操作的呢。  
我们是用递归把原数组进行拆分成2部分，一直拆分 最后2个数的数组被拆分成1个数的 这个时候递归就结束了，就开始把这2个数拆分后的数组进行合并，合并完毕后就回退到 4个数的数组，进行数组合并，然后是8个数，最后整体数据都有序。

// 二部分归并排序算法.cpp: 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<iostream>
    
    #define MAXSIZE 5
    
    void merging(int*iArray1, int iArrayIndexSize1, int*iArray2, int iArrayIndexSize2);
    
    void Merging(int *list1, int list1Size, int *list2, int list2Size)
    {
        int i, j, k;
        int temp[MAXSIZE];
    
        i = j = k = 0;
    
        while (i < list1Size && j < list2Size)
        {
            if (list1[i] < list2[j])
            {
                temp[k++] = list1[i++];
            }
            else
            {
                temp[k++] = list2[j++];
            }
        }
    
        while (i < list1Size)
        {
            temp[k++] = list1[i++];
        }
    
        while (j < list2Size)
        {
            temp[k++] = list2[j++];
        }
    
        for (int m = 0; m < list1Size + list2Size; m++)
        {
            list1[m] = temp[m];
        }
    }
    
    //二路归并排序算法
    void MergeSort(int iArray[], int n)
    {
        if (n > 1)
        {
            //数组指针1
            int *tempArray1 = iArray;
    
            //数组的元素索引范围
            int arraySize1 = n / 2;
    
            //数组指针2
            int *tempArray2 = iArray + arraySize1;
    
            //数组的元素索引范围
            int arraySize2 = n - arraySize1;
    
            //递归
            MergeSort(tempArray1, arraySize1);
            MergeSort(tempArray2, arraySize2);
    
            //开始合并2个数组
            Merging(tempArray1, arraySize1, tempArray2, arraySize2);
        }
    
    }
    
    int main()
    {
        int iArray[] = {
       5,4,3,2,1};
    
        MergeSort(iArray, 5);
    
        for (int i = 0; i < 5; i++)
        {
            printf("%d\n", iArray[i]);
        }
    
        return 0;
    }