Python 排序方法：选择排序

zltzlt

Python 选择排序

原理

选择排序就是重复 “从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换” 这一操作的算法。

选择排序使用了线性查找来寻找最小值，因此在第 1 轮中需要比较 n - 1 个数字，第 2 轮需要比较 n - 2 个数字……到第 n - 1 轮的时候就只需比较 1 个数字了。

因此，总的比较次数与冒泡排序的相同，都是 (n-1)+(n-2)+…+1 ≈ n²/2 次。

每轮中交换数字的次数最多为 1 次。

如果输入数据就是按从小到大的顺序排列的，便不需要进行任何交换。

选择排序的时间复杂度和冒泡排序的一样，都为 O(n²)。

代码

from random import randint


def sel_sort(nums):
    for i in range(0, len(nums)):
        min_ = nums[i]
        min_idx = i
        for j in range(i, len(nums)):
            if (new_min := nums[j]) < min_:
                min_ = new_min
                min_idx = j
        nums[i], nums[min_idx] = nums[min_idx], nums[i]


arr = [randint(0, 50) for _ in range(10)]
print(f"原数组：{arr}")
sel_sort(arr)
print(f"排序后数组：{arr}")

qiuyouzhi

最简单的（我最喜欢用的）：

>>> def mysort(a):
        for i in range(len(a)):
                for j in range(len(a)):
                        if a[i] > a[j]:
                                a[i], a[j] = a[j], a[i]

                                
>>> a = [5, 7, 1, 3, 2]
>>> mysort(a)
>>> a
[7, 5, 3, 2, 1]

虽然数一多就GG,但是它简单啊！
（能用sort尽量用sort ）