这种排序有名称吗?它对排序的效率是什么类型的数据？

Question

今天早上在去上班的火车上，我试着根据记忆写一个Bubble排序，但却出现了这个。

这种类型的排序有名称吗？

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  |

Geek for Geek示例气泡排序：

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次，但在这里，如果在前面的某个步骤中数据已经排序，你就会执行break。

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

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