归并排序

用户8224910

发布于 2022-05-10 01:40:58

23900

代码可运行

文章被收录于专栏：个人学习总结个人学习总结

运行总次数：0

代码可运行

归并排序

归并排序是排序算法中的一种，采用了分治的思想，将一组数先划分为n组，每组至少有一个数，再将这n组两组两组进行归并排序（有递归的成分），最终即可得到排好序的一组数。

问题 : 实现链表(线性表)

题目描述（线性表）顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序，线性表空间足够大。试用给出一种高效算法，将LB中元素合到LA中，使新的LA的元素仍保持非递减有序。高效指最大限度的避免移动元素。输入输入LA长度m：7 输入数据：3 7 11 15 57 68 99 输入LB长度n：7 输入数据：6 7 8 9 10 23 67 输出 3 6 7 8 9 10 11 15 23 57 67 68 99

样例输入

7 4 6 7 9 10 16 23 8 1 2 4 7 8 13 15 44

样例输出

1 2 4 6 7 8 9 10 13 15 16 23 44

这是一个不太恰当的例子，虽然是链表的题目，但与链表的操作没有直接关系，反而是用到了归并排序的思想。

#include<iostream>
using namespace std;
int main()
{
    int m,n,i,j=0;
    int a[300],b[300],c[600];
    cin>>m;
    for(i=0;i<m;i++)
    {
        cin>>a[i];
    }
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>b[i];
    }
    int k=0,count=0;
    i=0;
    while(i<m && j<n)  //两组数归并排序
    {
        if(a[i]<b[j])     
        {
            c[k++]=a[i++];
        }
        else if(b[j]<a[i])
        {
            c[k++]=b[j++];
        }
        else
        {
            c[k++]=a[i++];  //根据题目要求，注意相等的情况，只将一个数写入新数组即可
            j++;
        }
        count++;
    }
    while(i<m)
    {
        c[k++]=a[i++];
        count++;
    }
    while(j<n)
    {
        c[k++]=b[j++];
        count++;
    }
    for(i=0;i<count;i++)
    {
        cout<<c[i]<<" ";
    }
    cout<<endl;
    return 0;
}