这种排序算法可以被认为是冒泡排序的一种变体吗?

Question

这种方法可以被视为冒泡排序的一种变体吗?如果不是，那么关键的区别是什么?这种方法和冒泡排序之间的效率比较是什么?

def bubble_sort(arr):
for i in range(len(arr)):
for j in range(len(arr)-i):
if arr[i] > arr[j+i]:
arr[i], arr[j+i] = arr[j+i], arr[i]
return arr

if __name__ == '__main__':
arr = [21,4,1,3,9,20,25,6,21,14]
print(bubble_sort(arr))

: [1,3,4,6,9,14,20,21,21,25]

Answer 1

您的代码实现了算法选择排序而不是冒泡排序。虽然它们有些相似:它们都基于元素交换。

对于选择排序，算法的关键是找到最小或最大元素并最终交换:

算法通过查找最小(或最大，取决于在未排序的子列表中按排序顺序)元素，交换(交换)它与最左边未排序的元素(把它排序)顺序)，并将子列表边界向右移动一个元素。

你的代码可以改进以避免不必要的交换:

import random
def my_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(len(arr)-i):
if arr[min_idx] > arr[j+i]:
min_idx = j + i
arr[i],arr[min_idx] = arr[min_idx], arr[i]
return arr

if __name__ == '__main__':
for i in range(360):
i = i + 1
r = random.choices(range(i * 10), k=i)   # Get list of numbers
r1 = r.copy()
assert my_sort(r) == sorted(r1)