时间戳

首页 > 解决方案 > 这种排序算法可以被认为是冒泡排序的变体吗？

python - 这种排序算法可以被认为是冒泡排序的变体吗？

问题描述

这种方法可以被认为是冒泡排序的一种变体吗？如果不是，那么主要区别是什么？这种方法与冒泡排序之间的效率比较是什么？

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]

标签： pythonalgorithmsortingbubble-sort

解决方案

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

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

该算法通过在未排序的子列表中找到最小（或最大，取决于排序顺序）元素，将其与最左边的未排序元素交换（交换）（将其按排序顺序），并将子列表边界向右移动一个元素.

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

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)

推荐阅读