这种排序算法可以被视为冒泡排序的变体吗？

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

您的代码已实现算法 selection sort rather than bubble sort。虽然它们有些相似：它们都是基于元素交换。

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

The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

并且可以改进您的代码以避免不必要的交换：

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)

这种排序算法可以被视为冒泡排序的变体吗？

can this sorting algorithm be considered as a variation of bubble sort?

python

algorithm

sorting

bubble-sort