为何我偶然实现的Python weirdsort排序算法可行？

你写的weirdsort确实能正确完成升序排序，它的核心逻辑可以拆解如下：

def weirdsort(x):
    for i in range(len(x)):
        for j in range(len(x)):
            if (x[i] < x[j]):
                x[i], x[j] = x[j], x[i]

核心逻辑分析 #

• 外层循环i从0遍历到数组末尾，每一轮i的迭代，都会把当前数组中的最大值逐步“移动”到索引i的位置。
• 内层循环j遍历整个数组，只要发现x[i]小于x[j]就交换两者。这意味着在j的遍历过程中，x[i]会不断被替换成更大的元素，直到遍历结束时，x[i]成为整个数组的最大值。
• 随着i从0到n-1递增，最大值会被一步步从数组前端“推”到后端：
  • i=0时，最大值被放到索引0；
  • i=1时，最大值会从索引0交换到索引1；
  • 以此类推，直到i=n-1时，最大值最终被放到数组最后一位。
• 与此同时，较小的元素会被逐步往前置换，最终整个数组呈现升序排列。

和冒泡、选择排序的对比 #

• 冒泡排序：通过相邻元素比较交换，每一轮把当前未排序部分的最大值“冒”到末尾，外层循环控制已排序的末尾位置，内层循环范围逐步缩小。
• 选择排序：每一轮找到未排序部分的最小值，放到已排序部分的末尾，仅在找到最小值后进行一次交换。
• weirdsort：每一轮把全局最大值“挪”到当前i的位置，内层循环始终遍历整个数组，交换次数远多于前两者，但时间复杂度同样为O(n²)。

内容的提问来源于stack exchange，提问作者newatcodn