python - 是否有这种类型的名称？它对什么样的数据进行排序是有效的？

Question

今天早上在上类的火车上，我试图凭内存写一个冒泡排序，但我却想出了这个。

这种类型有名称吗？

def not_bubble_sort(arr):
    length = len(arr)
    while True:
        is_sorted = True
        for i in range(length - 1):
            if arr[i] > arr[i + 1]:
                is_sorted = False
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
        if is_sorted:
            break

    return arr

我预计这会非常低效，对于某些数据来说确实如此。但是对于其他随机生成的列表，它非常快，有人可以解释为什么会这样。有没有办法利用它？或者我在某处犯了错误。

我针对实际的冒泡排序运行了一些基准测试，发现对于某些类型的随机生成的列表，这要快得多。

基准测试对生成的 n 个 randint 整数列表进行排序。

N = 5000
------
|  min          |  avg          |  max          |  func             |  name             |
|---------------|---------------|---------------|-------------------|-------------------|
|  0.000463724  |  0.034745610  |  3.425408840  |  not_bubble_sort  |  sarcoma          |
|  1.159517288  |  1.212791989  |  1.768434763  |  bubble_sort      |  geeks_for_geeks  |

极客对极客冒泡排序示例:

def bubble_sort(arr):
    n = len(arr)

    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

    return arr

https://github.com/sarcoma/algorithms-python/blob/master/algorithms/sort/bubble_sort.py

Answer 1

这只是冒泡排序，但会提前退出。

在“真正的”冒泡排序中，无论数据是什么样子，你都会遍历数组 length-1 次，但在这里，如果在前面的某个步骤中数据已排序，你将中断。

效率低下是因为你的算法复杂度为“O(n^2)”而不是“O(1/2*n^2)”*(因为这个 for i in range(length - 1): 而不是这个 for j in range(0, n - i - 1):)

*不是真正的大O符号，但它证明了这一点