分而治之冒泡排序算法

Question

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

虽然我发布这个问题不是为了让你们解决我的作业，但我们的教授给了我们一个作业，将冒泡排序作为一种分而治之的算法来实现，现在我坐在笔记本电脑上绞尽脑汁想了好几天冒泡排序可以分治算法。

如果我尝试将 冒泡排序 实现为分而治之，则必须对数组进行划分，当我将数组划分为其最后一个元素然后将其合并回其排序形式时，算法就变成了合并排序。
如果我通过递归调用 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);

它与归并排序的调用模式相同，但绝对不是归并排序。

分而治之冒泡排序算法

Divide And Conquer Bubble Sort Algorithm

c++

sorting

algorithm

bubble-sort

divide-and-conquer