分而治之气泡排序算法

Question

本学期，我们学习了分而治之，其中将问题分为子问题，然后像合并排序或快速排序一样进行了解决。尽管我并没有发布这个问题来让大家解决我的任务，但是我们的教授给了我们一个任务，以将Bubble Sort作为分治算法来实现，现在我坐在笔记本电脑上摸索了几天，以讨论Bubble Sort可分治算法。如果我尝试实现Bubble Sort作为划分并征服数组，则必须将其划分为零，当我将数组划分为最后一个元素，然后将其合并回到其排序形式时，该算法将变为合并排序。如果我通过递归调用bubbleSort（array，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);
与合并排序相同的调用模式，但绝对不是合并排序。

Answer 2

谢谢您的回答，请您说明一下时间复杂度，并简要说明哪种算法更好。分而治之还是迭代的？