C++如何实现二路归并排序

C++如何实现二路归并排序

二路归并排序是一种常用的排序算法，其基本思想是将两个有序子表归并成一个有序表。本文将详细介绍如何使用C++实现二路归并排序，包括算法的基本思想、时间复杂度分析以及具体的代码实现。

二路归并排序

基本思想

二路归并排序就是将两个有序子表归并成一个有序表。首先我们得有一个算法用于归并：两个有序表放在同一数组的相邻位置上，arr[left]到arr[center-1]为第一个有序表，arr[center]到arr[right]是第二个有序表。每次从两端中取出一个进行比较，小的先放在一个temp数组，最后将比较剩下的直接放到temp中去，最后将temp又复制回arr。这是“治”。

所谓“分”，就是递归地将前半部分和后半部分的数据各自归并排序即可。

算法分析

每一趟归并的时间复杂度为O(n)，共需要进行⌈log2n⌉趟。对应的算法的时间复杂度为O(nlog2n)。归并排序的空间复杂度O(n)。另外，归并排序中归并的算法并不会将相同关键字的元素改变相对次序，所以归并排序是稳定的。

二路归并排序的前提是两个序列本身有序。

void Merger(int *arr, int len, int width)
{
    int *temp = (int *)malloc(sizeof(int) * (len));
    // 首先对两路下标分别进行初始化
    int l1 = 0;
    int h2 = l1 + width - 1;
    int l2 = h2 + 1;
    int h3 = l2 + width - 1 < len - 1 ? l2 + width - 1 : len - 1;
    int temppos = 0;
    // 判断所在下标位置的值
    while (l1 < len && l2 < len)
    {
        while (l1 <= h2 && l2 <= h3)
        {
            if (arr[l1] < arr[l2])
            {
                temp[temppos++] = arr[l1++];
            }
            else
            {
                temp[temppos++] = arr[l2++];
            }
        }
        // l1有剩余
        while (l1 <= h2)
        {
            temp[temppos++] = arr[l1++];
        }
        // l2有剩余
        while (l2 <= h3)
        {
            temp[temppos++] = arr[l2++];
        }
        // l1 l2向后移动
        l1 = h3 + 1;
        h2 = (l1 + width - 1) < (len - 1) ? (l1 + width - 1) : (len - 1);
        l2 = h2 + 1;
        h3 = (l2 + width - 1) < (len - 1) ? (l2 + width - 1) : (len - 1);
    }
    // 奇数归并块 剩下的一个单都块操作
    while (l1 < len)
    {
        temp[temppos++] = arr[l1++];
    }
    // 将临时数组中的数据复制回原数组
    for (int i = 0; i < len; i++)
    {
        arr[i] = temp[i];
    }
    free(temp);
}

二路合并排序算法

#include <iostream>
using namespace std;

class SortableList
{
public:
    SortableList(int mSize)
    {
        maxSize = mSize;
        l = new int[maxSize];
        n = 0;
    }
    ~SortableList()
    {
        delete[] l;
    }
    void Merge(int, int, int);
    void MergeSort(int, int);
    void Input();
    void Output();

private:
    int *l;
    int maxSize;
    int n;
};

void SortableList::Input()
{
    cout << "请输入要排序的数：";
    for (int i = 0; i <= maxSize - 1; i++)
        cin >> l[i];
}

void SortableList::Output()
{
    cout << "排序后的数是：";
    for (int i = 0; i <= maxSize - 1; i++)
        cout << l[i] << ' ';
}

void SortableList::MergeSort(int left, int right)
{
    if (left < right) // 如果序列长度大于1则划分
    {
        int mid = (left + right) / 2;
        MergeSort(left, mid); // 对左序列进行排序
        MergeSort(mid + 1, right); // 对右序列进行排序
        Merge(left, mid, right); // 合并
    }
}

void SortableList::Merge(int left, int mid, int right)
{
    int *temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while ((i <= mid) && (j <= right)) // 判断序列是否为空
        if (l[i] <= l[j])
            temp[k++] = l[i++];
        else
            temp[k++] = l[j++];
    while (i <= mid)
        temp[k++] = l[i++]; // 右序列空了左序列依次写入
    while (j <= right)
        temp[k++] = l[j++]; // 左序列空了右序列依次写入
    for (i = 0, k = left; k <= right;)
        l[k++] = temp[i++]; // 临时在数组temp中的排列好的数据放入数组l
}

int main()
{
    int m;
    cout << "请输入要排序的数的数目：";
    cin >> m;
    SortableList a1(m);
    a1.Input();
    a1.MergeSort(0, m - 1);
    a1.Output();
}

感谢各位的阅读，以上就是“C++如何实现二路归并排序”的内容了，经过本文的学习后，相信大家对C++如何实现二路归并排序这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。

本文原文来自创新互联建站