介绍

煎饼排序（英语：Pancake sorting）指的是将大小不同的一摞煎饼按大小排序的数学问题，其中煎饼铲子每次只能从任意位置铲起上方全部煎饼并翻面。“煎饼数”（英语：pancake number）是指给定煎饼的张数时，最坏情况下需要的最少翻面次数。

实现

JavaScript

/*
 * Unlike a traditional sorting algorithm, which attempts to sort with the fewest
 * comparisons possible, the goal of pancake sort is to sort the sequence in as few reversals as
 * possible. The idea is to do something similar to Selection Sort. We one by one place
 * maximum element at the end and reduce the size of current array by one.
 *
 * Source: https://www.geeksforgeeks.org/pancake-sorting/
 *
 * This sorting algorithm is inspired by the pancake problem (hence the name),
 * where a spatula can be placed anywhere between two pancakes and flip all pancakes
 * above.
 *
 * The interesting about this algorithm (besides its name) is that instead of comparisons,
 * the algorithm relies on flipping an array.
 *
 * Source: https://en.wikipedia.org/wiki/Pancake_sorting#The_original_pancake_problem
 *
 */

/**
 * Unlike Array.prototype.reverse, flipArray reverses only a subarray of the given
 * array, determined by the parameters startIndex and endIndex
 *
 * @param {number[]} array The array to flip
 * @param {number} startIndex The start of the subarray
 * @param {number} endIndex The end of the subarray
 * @returns The flipped array
 */
function flipArray (array, startIndex, endIndex) {
  while (startIndex < endIndex) {
    // swap front and back of the subarray
    const temp = array[startIndex]
    array[startIndex] = array[endIndex]
    array[endIndex] = temp

    // essentially reducing the problem to a smaller subarray
    startIndex++
    endIndex--
  }

  return array
}

/**
 * Returns the index of the maximum number of a subarray in a given array
 *
 * @param {number[]} array The array to found the maximum number's index
 * @param {*} startIndex The start of the subarray
 * @param {*} endIndex The end of the subarray
 * @returns The index of the maximum number
 */
function findMax (array, startIndex, endIndex) {
  let maxIndex = 0
  for (let i = startIndex; i <= endIndex; i++) {
    if (array[i] > array[maxIndex]) maxIndex = i
  }

  return maxIndex
}

/**
 * The Pancake Sort algorithm.
 *
 * Note that even though it's a completely different concept of sorting an
 * array, it's rather simple!
 *
 * @param {number[]} array The array to sort
 * @returns The sorted array
 */
function pancakeSort (array) {
  for (let subarraySize = array.length; subarraySize > 1; subarraySize--) {
    const maximumIndex = findMax(array, 0, subarraySize - 1)

    if (maximumIndex !== subarraySize - 1) {
      flipArray(array, 0, maximumIndex)
      flipArray(array, 0, subarraySize - 1)
    }
  }

  return array
}

参考

• 煎饼排序 - 维基百科，自由的百科全书 (opens new window)