一道「空间」很贵的排序算法

[Jocs]

又是十点钟才离开公司，拖着疲惫的驱壳，挪着步子，走进地铁站，上海真的很多人，晚上十点多了，地铁上还是很挤，我习惯的拿出了手机，看一下微信群，放松下加班后劳累的身体。

打开了小区业主群，一个叫做「九哥哥」的邻居在小区群里竟然提了一个问题，准确的说是一道算法题：

借此地问个问题，各位ITer看此题是否有解，有一个队列结构(FIFO)，如何对里面的元素进行从小到大排序，元素可以多次进出，而且允许有一个额外空间能暂存一个元素。

哎，本来想放松下心情的，结果又被这道算法题勾起了兴趣。。。脑子里迅速浮现了常见的排序算法：冒泡排序、快速排序、插入排序、归并排序。。。

果然，群里马上就炸开锅了（感觉我们业主群整个就是一个 IT 交流互助群了），迅速有一位「小毛」的业主回复了。

小毛：看上去是面试题呀，不考虑并发，不考虑性能， 用冒泡排序嘛

「unix」的业主跟着回复道：

Unix：[奸笑]冒泡啊。。不是有个空间能暂存一个元素的么。。

想想也就知道了，队列（FIFO）只提供了 pop(从队列末端推出元素)和 unshift(从队列入口推入元素)，而且只有一个额外的空间用于暂存元素，因此根本就没法交换两个来冒泡排序。

后面果然有人反驳道了。

秋风哥哥：@ unix 冒泡搞不了啊

九哥哥（提问者）：肯定不是冒泡撒[捂脸]

Unix：[捂脸]搞不了。。刚看到是队列。。

这时候，作为群主的「小毛」不服气了。怒怼众人。

小毛：冒泡咋就搞不定捏，我就问一个问题， 用冒泡写出来了， 有人吃屎不？

九哥哥（提问者）：没法交换相邻的元素@小毛

终于来了一个反对冒泡排序，有理有据的回答了。

很着调：jj， 冒泡交换数据那个动作 比较+暂存需要三个存储空间了 除去出的那个算一个，还需要额外的两个存储空间，他们只有一个

看来，冒泡排序已经被大家否决了，但是群里又抛出了另外一个疑问？

秋风哥哥：@小毛 冒泡排序，也要知道总长度，不然你冒泡啥时候停止

九哥哥（提问者）：总长度知道的

小毛：就是嘛，我就没见过类似集合类的数据结构本身无法描述长度的

讨论到这里，感觉，终于有人给出了文字描述的算法。

秋风哥哥：第一次队列全出进，可以确定一个最大值
秋风哥哥：然后插入队列尾部
秋风哥哥：然后第二次出队，出队个数为 总个数-1，求出第二大，这个要自己推演一下

感觉算法已经基本有了，群里疑问又一次升级。。。讨论到了算法复杂度的层面了。。。

肖立涛：你这样的时间复杂度基本是在O(n2)，为什么空间控制这么严格呢？

九哥哥（提问者）：因为这不是内存，而是个实际的柜子，只有这么大空间[捂脸]，完全不考虑时间复杂度

很着调：柜子高兴开哪个就开哪个，它的数据结构不是可以是数组了，为什么还限制死是pipe的

九哥哥（提问者）：OK，不是我们想的这种柜子，反正就是这么个结构，只能从上面放，从下面取，中间没有门@很着调

很着调：好吧

九哥哥（提问者）：设计给机械操作的，做不到灵活的存取，只能固定两个位置

聊天看到这儿才发现，这原来不是面试题。。。是用算法解决实际问题啦。

👌，感觉聊天到这儿已经接近尾声，在地铁上无聊，也没心思去想它，开始打游戏了。回到家，蹭着脑袋清醒多了，打开电脑，写下了如下实现算法：

/**
 * 只能使用 unshift\pop
 * 只有 x 用于暂存元素。
 */
// 去队列顶部元素
function peak(list) {
	return list[list.length - 1]
}
function sort(list) {
	const len = list.length
	let x = list.pop()

	for(let i = 0; i < len - 1; i++) {
		for (let j = 0; j < len - i - 1; j++) {
			if (x > peak(list)) {
				list.unshift(x)
				x = list.pop()
			} else {
				list.unshift(list.pop())
			}
		}
		list.unshift(x)
		for (let k = 0; k < i; k++) {
			list.unshift(list.pop())
		}
		if(i !== len - 2) x = list.pop()
	}
	return list
}
const input = [1, 12, 45, 4, 5, 7, 1, 2, 9, 6]
sort(input) // [ 1, 1, 2, 4, 5, 6, 7, 9, 12, 45 ]

算法不复杂，嵌套两个循环，如果以代码中 x > peak(list) 比较作为最耗时的步骤，假设队列长度为 n，那么总共需要做 （n - 1) * n / 2 次比较。可见其时间复杂度为 O(n2)。

😝，感觉小群业主群已然变味了，不再讨论菜米油盐，也不再抱怨小区物业无作为。感觉聊天内容到了一个新的高度。竟然聊计算机算法了，这么稀奇的事情，我决定把它记下来。

写在最后，也没见「小毛」用冒泡排序写出实现代码来，当然也就没人吃屎了。

[strongcode9527]

标题修改记录显示了作者挣扎的内心

[Jocs]

@strongcode9527 😆，读得太仔细了哈，关注重点。

[myst729]

跳过你的代码部分，快糙猛地实现了一个，直接n * (n - 1)次比较 🤣

function sort (queue) {
  let swap
  for (let i = 0; i < queue.length; i++) {
    swap = queue.shift()
    for (let j = 0; j < queue.length; j++) {
      if (swap > queue[0]) {
        queue.push(queue.shift())
      } else {
        queue.push(swap)
        swap = queue.shift()
      }
    }
    queue.push(swap)
  }
  return queue
}

跟你的实现差不多，没优化

[myst729]

有趣的题目也可以分享到 https://github.com/eleme/rice/issues 大家一起玩

[Jocs]

@myst729 👌，我把题目整理下，再发上去。