2

我正在尝试使用 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)，这是由于在每个合并排序调用中创建了向量（我认为）。我尝试删除向量并仅在合并函数中使用数组，如下所示

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

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

4

1 回答 1

4

正如 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);
    }
}

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

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

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);
于 2012-12-01T18:49:42.537 回答