数据结构及算法——归并排序

本文主要是介绍数据结构及算法——归并排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、归并排序的思想
其原理是假设初始序列含有n个记录，则可以将n个记录看成是n个有序的子序列，每个子序列长度为1，然后两两进行归并，得到[n/2]（即不小于n/2的最小整数）个长度为2或者1（当序列的元素为奇数个时最后可能存在一个单独的子序列）的有序子序列；再进行两两归并，如此重复，直到得到一个长度为n的有序序列为止，此排序方法称作为2路归并排序。

二、归并排序代码（来源于大话数据结构）

#include <iostream>
#include <initializer_list>
#define MAXSIZE 10
typedef int Status;

struct SqList
{
    int r[MAXSIZE+1]= {0, 1, 5, 8, 3, 10, 9};
    int length = 6;
};

void Merge(int *SR, int *TR, int i, int m, int n); //将数组SR归并为TR
void MSort(int *SR, int *TR1, int s, int t); //将数组SR中的关键字归并到TR1中
void MergeSort(SqList &L)
{
    MSort(L, L, 1, L.length);
}
void MSort(int *SR, int *TR1, int s, int t) 
{
    int m;
    int TR2[MAXSIZE+1]; //中间辅助数组，此处每次递归都会创建数组，造成空间浪费，更好的实现方法参见b站浙大数据结构视频中的讲解
    if(s==t)
        TR[s] = SR[s];
    else
    {
        m = (s+t)/2;
        MSort(SR, TR2, s, m); 
        MSort(SR, TR2, m+1, t);
        Merge(TR2, TR1, s, m, t);
    }
}
void Merge(int *SR, int *TR, int i, int m, int n)
{
    int j, k, l; //三个指针，分别指向两个子序列中待比较关键字的位置以及目标数组中待放入关键字的位置
    for(k=i, j=m+1; i<=m && j<=n; ++k)
    {
        if(SR[i]<SR[j])
            TR[k] = SR[i++];
        else
            TR[k] = SR[j++];
    }
    if(i<=m)
        for(l=0; l<=m-i; ++l)
            TR[k+l] = SR[i+l];
    if(j<=n)
        for(l=0; l<=n-j; ++l)
            TR[k+l] = SR[j+l];
}
int main()
{
    SqList L;
    MergeSort(L);
    for(int i=1; i<=L.length; ++i)
        std::cout << L.r[i] << " ";
}
        

这篇关于数据结构及算法——归并排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！