Java 中的煎饼排序

在本节中，我们将学习Java 中的煎饼排序。在煎饼排序中，需要通过执行一个操作来对数组进行排序，该操作是

flipArr(arr, j): 反转数组 arr 从索引 0 到 j。

通常，在其他排序算法中，会尝试以最少的元素比较次数来排序数组中的元素。然而，在煎饼排序中，我们专注于以最少的反转次数来排序数组中的元素。

煎饼排序涉及的步骤

煎饼排序涉及以下步骤。

• 从当前大小 s 开始，然后每次将当前大小减 1，直到它小于或等于 1。假设当前大小由 currSize 表示。现在，对于每个 currSize，执行以下操作。
  • 搜索 arr[0… currSize - 1] 中最大元素的索引。假设该索引为 'idx'
  • 调用 flipArr(arr, idx)
  • 调用 flipArr(arr, currSize - 1)

实施

以下代码显示了使用上述步骤实现的煎饼排序。

文件名： PancakeSortingExample.java

输出

Input Array is: 
23 100 210 101 112 66 27 67 809 

After sorting the array is: 
23 27 66 67 100 101 112 210 809

解释

我们做了类似于选择排序的操作。我们将最大元素放在数组的末尾，然后将数组的当前大小减 1。当前大小的减小会一直持续，直到整个数组排序完成。