c++ - 通过分而治之的C ++递归排序和迭代排序

Question

你们能否用外行的话向我解释一下，无论有没有代码示例，使用递归的分而治之数组排序是如何工作的，以及它与迭代数组排序有何不同？我完全迷失在这里。

Answer 1

有几种迭代数组排序算法，所有这些算法都涉及比较元素并根据需要移动它们以使数组排序。

进行递归解决方案的一种方法是有一个基本情况，如果数组非常小，则使用迭代排序，对于较大的数组，它将数组拆分为较小的块并递归。这些块中的每一个都将按排序返回，然后将它们合并（合并排序数组很快）。

所以在伪代码中：

function recursive_sort(array) {
    if (array is small)
        sort array iteratively and return
    else
        // split the array
        let array1 be the first half of array
        let array2 be the second half of array
        // sort the chunks
        recursive_sort(array1)
        recursive_sort(array2)
        // merge() describes the operation of merging two sorted arrays (fast!)
        array = merge(array1, array2)
}

请注意，递归排序的基本情况可能只是array空的或只有 1 个元素。在这种情况下，基本情况不需要做任何事情，因此不依赖于迭代排序方法。

当然还有其他递归算法可以使用，但基本思想是相同的：每次递归调用将使用原始数组的一些较小块，并且这些块在最后组合以给出排序结果。