时间戳

首页 > 解决方案 > 自底向上归并排序的实现

c++ - 自底向上归并排序的实现

问题描述

我了解到合并排序是一种遵循分治原则的排序算法，它的平均时间复杂度为 n(log n)。

在这里，我将大小为 n 的数组划分为子数组（以长度 2 初始化），并通过对子数组进行排序来征服它。然后我们继续以 2 的倍数计算范围，直到它小于数组的长度（即 2,4,8,....i，其中 i< 数组长度）。

当它超过数组的长度时，函数返回排序后的数组。

我使用了两个函数来实现合并排序：

  1. 合并排序（产生子数组）
  1. 插入排序（对子数组进行排序）

该程序运行良好，我想知道我是否理解合并排序的概念并正确实施它？

//C++ Code
#include<iostream>

// Print
void print(int *arr, int length);

// To Sort the sub array
void insertion_sort(int *arr, int low, int high)
{
    for(int i = high; (i-1)>=low; i--)
    {
        if (arr[i] < arr [i-1])
        {
            int temp = arr[i];
            arr[i] = arr[i-1];
            arr[i-1] = temp;
        }
    }
}

int *merge_sort(int* arr, int length, int index = 2)
{
    if (length <= index) // Terminating Condition
    {
        return arr;
    }

    // The range is defined by index.

        /*
            If array has 8 elements:  ********
            It will sort array until it's range within the length of array.
            1st call  2*1 elements max: ** ** ** ** // 2 set as default argument
            2nd call  2*2 elements max: **** ****
            3rd call  2*3 elements max: ********
            Returns Array
        */

    // The range is defined by index.

    for(int i=0; (i+index)<length; i+=index)
    {
        // Divide and Sort
        insertion_sort(arr, i, i+index);
    }

    // The range will increase in multiple of 2 (i.e. 2,4,8,....i where i<length of array)
    return merge_sort(arr, length, index*2);
}

int main()
{
    int length;    
    std::cout<<"Length of Array: ";
    std::cin>>length;

    int arr[length];

    for(int i=0; i<length; i++)
    {
        std::cout<<"Enter element "<<i+1<<" : ";
        std::cin>>arr[i];
    }

    int *result = merge_sort(arr, length);
    
    print(result, length);
    
    return 0;
}

void print(int *arr, int length)
{
    std::cout<<"Sorted Array: ";

    for(int i=0; i<length; i++)
    {
        std::cout<<arr[i]<<" ";
    }

    std::cout<<"\n";
}

标签： c++arraysalgorithmmergesort

解决方案

纯自下而上的归并排序将包含 n 个元素的数组划分为大小为 1 的 n 次运行，然后每次遍历合并偶数和奇数运行。链接到 wiki 示例：

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation

正如 Wiki 示例评论中所建议的，每次通过都可以更改合并的方向。以原始数组中的排序数据结束，计算所需的通过次数，如果通过次数为奇数，则比较并交换（如果需要）元素对以创建大小为 2 的运行，然后进行合并排序通过。

对于混合插入+归并排序，对遍历次数进行相同的计算，如果遍历次数为奇数，则将初始运行大小设置为 32 个元素，否则将初始运行大小设置为 64 个元素。使用插入排序对初始运行进行一次排序，然后切换到合并排序。

获取通过计数的简单示例代码（对于 32 位构建，假设 n <= 2^31）：

size_t GetPassCount(size_t n)               // return # passes
{
    size_t i = 0;
    for(size_t s = 1; s < n; s <<= 1)
        i += 1;
    return(i);
}

推荐阅读