今天早上我在上类的火车上试图凭内存编写一个冒泡排序，但想到了这个。
这种类型有名称吗？
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
最佳答案
这只是冒泡排序，但提前退出。
在“真正的”冒泡排序中，无论数据是什么样子，您都会遍历数组 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符号，但它证明了这一点
关于python - 这种排序有名称吗？它对哪种数据排序有效？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55179592/