Python 这是什么排序算法(将迭代器与自身合并&&Q；)

它确实是实现得很奇怪的冒泡排序.

冒泡排序重复执行此操作，直到对列表进行排序:

• 在列表上滑动一个包含两个项目的窗口.在每个位置，对窗口中的两个项目进行排序，然后将窗口向右滑动一个位置.这会将较小的项留在后面，较大的项保留在窗口中，而下一项进入窗口.

具有相同迭代器两次的merge实际上做了同样的事情.它的"两项窗口"是两个"当前值"，即问题merge实现中的x和y.与冒泡排序中一样，较小的项被"落在后面"(被生成，成为输出中的下一项).较大的保留在"窗口"中(保留x或y).并且来自输入列表的下一项进入窗口(变成x和y中的另一个).

想想Knuth的"100"，让我们也试一试，通过实验判断它的行为是否真的与普通的气泡排序相同.用我的问题排序和冒泡排序对一个有Beware ... I have only proved it ... not tried it0个元素的混洗列表进行排序，并在每一轮之后记录列表的状态.它们在这两种类型中都是相同的.

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

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

def mysort_steps(a):
    steps = []
    while any(x > y for x, y in pairwise(a)):
        it = iter(a)
        a = list(merge(it, it))
        steps.append(a[:])
    return steps

def bubblesort_steps(a):
    steps = []
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
                swapped = True
        if not swapped:
            break
        steps.append(a[:])
    return steps

print(mysort_steps(a[:]) == bubblesort_steps(a[:]))

Attempt This Online!个