C++ 煎饼排序

本文将讨论 C++ 中的煎饼排序及其示例。

当可以在堆栈的任何位置插入铲子并用于翻转其上方的所有煎饼时，将一堆杂乱的煎饼按大小顺序排序的数学问题称为煎饼排序。使一定数量的煎饼所需的最小翻转次数称为煎饼数。

它的主要目标是类似于选择排序。我们通过在末尾添加最大的元素，逐渐将当前数组的大小减小一。

程序说明

1. 创建一个名为 flip(Arr, i) 的方法，该方法翻转数组 arr 的前 i 个元素的顺序。
2. 创建函数 pancakeSort(Arr)，该函数返回排序后的输入数组。您只能使用 flip 函数来更改数组。

算法

设给定数组为 Arr[]，数组大小为 'n'。

从当前大小 'n' 开始，并在当前大小大于 1 时将其减小一。设当前大小为 c。对每个 'c' 执行以下操作。

1. 在 Arr[0....c-1] 中找到最大元素的索引 'i'。
2. 调用 flip(Arr,i)
3. 调用 flip(Arr,c-1)

程序

让我们举一个例子来演示 C++ 中的煎饼排序

输出

复杂度

时间复杂度

煎饼排序算法的时间复杂度为 O(n2)，其中 'n' 是输入数组中元素的数量。

在最坏的情况下，最大的元素可能需要多达 n 次翻转（反转）才能到达堆栈顶部，然后是 n-1 次翻转才能将第二大的元素移动到第二个位置，依此类推。因此，时间复杂度是二次方。

空间复杂度

煎饼排序算法的空间复杂度为 O(1)，这意味着无论输入大小如何，它始终需要固定量的额外内存。

原地排序算法，煎饼排序，在不使用与输入大小成比例的额外内存的情况下对初始数组中的元素进行排序。