这是什么排序算法？ (“将迭代器与其自身合并”)

Question

只要列表未排序，就继续用迭代器与其自身的合并来替换它。这是（相当于）一种众所周知的排序算法，只是实现得很奇怪，还是新的东西？

from random import shuffle
from heapq import merge
from itertools import pairwise

# Create test data
a = list(range(100))
shuffle(a)

# Sort
while any(x > y for x, y in pairwise(a)):
    it = iter(a)
    a = list(merge(it, it))

print(a)

在线尝试！

Answer 1

这是一种复杂的冒泡排序编写方式。

merge(it, it)

是一种复杂的方法，将所有对排序为

it[0]

与

it[1]

，然后将较大的对与

it[2]

排序，依此类推。 “

it[0]

against

it[1]

”部分来自于对同一迭代器的双重迭代以及来自

merge

的成对排序。

any(x > y for x, y in pairwise(a))

测试排序的程度，即下一次迭代是否会执行任何交换以确保成对排序。

这实际上是冒泡排序的教科书定义：

冒泡排序，有时称为下沉排序，是一种简单的排序算法，它逐个元素地重复遍历输入列表，将当前元素与其后面的元素进行比较，并在需要时交换它们的值。重复对列表的这些遍历，直到在遍历期间无需执行交换

，这意味着列表已完全排序。