Python 排序方法：选择排序

zltzlt

Python 选择排序

原理

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

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

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

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

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

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

代码

1. from random import randint
   
2. 
   
3. 
   
4. def sel_sort(nums):
   
5.     for i in range(0, len(nums)):
   
6.         min_ = nums[i]
   
7.         min_idx = i
   
8.         for j in range(i, len(nums)):
   
9.             if (new_min := nums[j]) < min_:
   
10.                 min_ = new_min
    
11.                 min_idx = j
    
12.         nums[i], nums[min_idx] = nums[min_idx], nums[i]
    
13. 
    
14. 
    
15. arr = [randint(0, 50) for _ in range(10)]
    
16. print(f"原数组：{arr}")
    
17. sel_sort(arr)
    
18. print(f"排序后数组：{arr}")

复制代码

qiuyouzhi

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

1. >>> def mysort(a):
   
2.         for i in range(len(a)):
   
3.                 for j in range(len(a)):
   
4.                         if a[i] > a[j]:
   
5.                                 a[i], a[j] = a[j], a[i]
   
6. 
   
7.                                
   
8. >>> a = [5, 7, 1, 3, 2]
   
9. >>> mysort(a)
   
10. >>> a
    
11. [7, 5, 3, 2, 1]

复制代码

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