c++ - 使用指向数组的指针进行合并排序

Question

我正在尝试使用 STL 库制作合并排序算法，但遇到一些问题。下面是我正在使用的代码

template <typename Item, typename SizeType>
void merge_sort(Item array[], SizeType size){
    size_t n1; //Size of the first subarray
    size_t n2; //Size of the second subarray

    if(size > 1){
        //Compute the size of the subarrays
        n1 = size/2;
        n2 = size - n1;

        //create the temp array.
        int* n1Temp = new int[n1];
        int* n2Temp = new int[n2];
        int i;
        for(i = 0; i < n1; i++)
            n1Temp[i] = array[i];
        for(i = 0; i < n2; i++)
            n2Temp[i] = array[i + n1];

        //recursive calls
        merge_sort(n1Temp, n1);//sort from array[0] through array[n1 - 1] 
        merge_sort(n2Temp, n2);//sort from array[n1] to the end

        //Merge the two sorted halves.
        vector<int> v(array, array + size);
        merge(n1Temp, n1Temp + n1, n2Temp, n2Temp + n2, v.begin());     
        copy(v.begin(), v.end(), array);//copy the vector back to the array

        delete[] n1Temp;
        delete[] n2Temp;
    }
}

代码排序很好，但问题是它的行为类似于 O(n^2) 算法，而不是 O(n\log n)，这是由于在每个合并排序调用中创建了 vector (我认为)。我尝试删除 vector 并仅在合并函数中使用数组，如下所示

    //Merge the two sorted halves.
    int* finalArray = new int[n1 + n2];
    merge(n1Temp, n1Temp + n1, n2Temp, n2Temp + n2, begin(finalArray)); 
    array = finalArray;

但这只会给我带来错误。我可以做些什么来挽救我的合并排序算法吗？

Answer 1

正如 Vaughn 和 user93353 所指出的，您应该能够在每个合并点直接合并到目标数组中。但您仍然可以使用 std::vector<> 来使这对您自己来说变得更加容易。

此外，您的临时数组是直接类型“int”，我相当确定它是模板参数 Item 的类型。我不确定 SizeType 参数的用途，但我保留了它，以防您有特殊的想法。不管它是什么，它最好与 size_t 兼容:

template <typename Item, typename SizeType>
void merge_sort(Item array[], SizeType size)
{
    if(size > 1)
    {
        //Compute the size of the subarrays
        size_t n1 = size/2;

        //create the temp array
        std::vector<Item> n1Temp(array, array+n1);
        std::vector<Item> n2Temp(array+n1, array+size);

        //recursive calls
        merge_sort(&n1Temp[0], n1);       //sort array[0] through array[n1-1]
        merge_sort(&n2Temp[0], size-n1);  //sort array[n1] through array[size-1]

        // merge the sorted halves
        std::merge(n1Temp.begin(), n1Temp.end(),
                   n2Temp.begin(), n2Temp.end(), array);
    }
}

上述技术通过拷贝自上而下分割子序列，然后将分割拷贝就地合并到原始数组中。您可以通过对原始数组进行拆分，然后合并到临时空间并在之后进行复制，从而减少该算法的一个子列表分配时间(但空间不少于)，我认为 你首先想要做的是:

template <typename Item>
void merge_sort(Item ar[], size_t n)
{
    if (n > 1)
    {
        // Compute the size of the subarrays
        size_t n1 = n/2;

        // invoke recursion on the submerges
        merge_sort(ar, n1);      //sort array[0] through array[n1-1]
        merge_sort(ar+n1, n-n1); //sort array[n1] through array[size-1]

        // create merge-buffer
        std::vector<Item> mrg;
        std::merge(ar, ar+n1, ar+n1, ar+n, back_inserter(mrg));
        std::copy(mrg.begin(), mrg.end(), ar);
    }
}

---

基于迭代器的通用解决方案

对于允许更大灵活性的通用解决方案，您可以基于迭代器而不是项目指针来定义合并排序。它变得更加毛茸茸的，但好处是非常标准库式的。

template <typename Iterator>
void merge_sort(Iterator first, Iterator last)
{
    typedef typename std::iterator_traits<Iterator>::value_type value_type;
    typedef typename std::iterator_traits<Iterator>::difference_type difference_type;

    difference_type n = std::distance(first, last)/2;
    if (n == 0)
        return;

    // invoke recursion on the submerges
    merge_sort(first, first + n);
    merge_sort(first + n, last);

    // create merge-buffer
    std::vector<value_type> mrg(std::distance(first, last));
    std::merge(first, first+n, first+n, last, mrg.begin());
    std::copy(mrg.begin(), mrg.end(), first);
}

---

最后，如果您发现自己对大量固定长度的 C 数组进行排序，您可能会发现以下内容很有帮助(它使用上面的通用迭代器解决方案):

// front-loader for C arrays
template<typename Item, size_t N>
void merge_sort(Item (&ar)[N])
{
    merge_sort(std::begin(ar), std::end(ar));
}

它使下面的代码变得相当方便:

int arr[1024];
... fill arr ...
merge_sort(arr);