分治冒泡排序算法

Question

这学期我们学习了分而治之，在分而治之中，问题被分成子问题，然后像合并排序或快速排序一样解决。

虽然我发布这个问题不是为了让你们解决我的作业，我们的教授给了我们一个任务，让我们把冒泡排序作为一种分治算法来实现，现在我坐在笔记本电脑上，几天都在挠头，想知道冒泡排序是如何分治算法的。

如果我试图将冒泡排序实现为分治，数组必须被分割，当我将数组划分为最后一个元素，然后将其合并回已排序的形式时，算法就变成了合并排序。
如果我通过递归调用bubbleSort（数组，size-1)来实现它，算法就变成了Reduce and conquer。

我的问题是“如何将冒泡排序实现为分治算法？”

Answer 1

假设您编写了一个bubblesort函数，该函数允许对数组的一部分进行排序：

bubblesort(arr, start, end)
{
    // sorts the items from arr[start] to arr[end]
}

因此，如果数组[1,7,4,9,6,3,2,5]并称为bubblesort(arr,0,3)，则结果数组将为[1,4,7,9,6,3,2,5]。

现在想象一下，如果你打了这些电话，会发生什么：

bubblesort(arr, 0, 1);
bubblesort(arr, 2, 3);
bubblesort(arr, 4, 5);
bubblesort(arr, 6, 7);

bubblesort(arr, 1, 3);
bubblesort(arr, 4, 7);

bubblesort(arr, 0, 7);

它与合并排序是相同的调用模式，但肯定不是合并排序。