本文目录导读：
我来详细介绍Python选择排序的实操编写方法。
基础选择排序算法
def selection_sort(arr):
"""
基础选择排序实现
时间复杂度：O(n²)
空间复杂度：O(1)
"""
n = len(arr)
# 遍历所有元素
for i in range(n):
# 假设当前位置i的元素是最小值
min_idx = i
# 在剩余元素中找到最小值
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# 将找到的最小值与当前位置交换
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# 测试
test_arr = [64, 34, 25, 12, 22, 11, 90]
print("排序前:", test_arr)
sorted_arr = selection_sort(test_arr)
print("排序后:", sorted_arr)
带详细注释的版本
def selection_sort_detailed(arr):
"""
详细注释版的选择排序
"""
n = len(arr)
print(f"初始数组: {arr}")
print("-" * 40)
for i in range(n):
min_idx = i
print(f"第{i+1}轮: 当前位置i={i}, 值={arr[i]}")
# 在未排序部分查找最小值
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# 如果找到了更小的值，进行交换
if min_idx != i:
print(f" 找到最小值 arr[{min_idx}] = {arr[min_idx]}, 与 arr[{i}] = {arr[i]} 交换")
arr[i], arr[min_idx] = arr[min_idx], arr[i]
print(f" 交换后数组: {arr}")
else:
print(f" arr[{i}] 已是最小值，无需交换")
print(f"第{i+1}轮结束: {arr}")
print("-" * 40)
return arr
# 测试详细版本
test_arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort_detailed(test_arr.copy())
降序选择排序
def selection_sort_descending(arr):
"""
降序选择排序
"""
n = len(arr)
for i in range(n):
# 找最大值，而不是最小值
max_idx = i
for j in range(i + 1, n):
if arr[j] > arr[max_idx]: # 改为大于号
max_idx = j
arr[i], arr[max_idx] = arr[max_idx], arr[i]
return arr
# 测试降序
test_arr = [64, 34, 25, 12, 22, 11, 90]
print("升序:", selection_sort(test_arr.copy()))
print("降序:", selection_sort_descending(test_arr.copy()))
选择排序的变体 - 同时选择最大最小值
def selection_sort_bidirectional(arr):
"""
双向选择排序：同时找到最大和最小值
"""
n = len(arr)
left = 0
right = n - 1
while left < right:
min_idx = left
max_idx = right
# 在范围内同时查找最大和最小值
for i in range(left, right + 1):
if arr[i] < arr[min_idx]:
min_idx = i
if arr[i] > arr[max_idx]:
max_idx = i
# 将最小值放到左边
if min_idx != left:
arr[left], arr[min_idx] = arr[min_idx], arr[left]
# 如果最大值被移动到最小值位置了，更新最大值索引
if max_idx == left:
max_idx = min_idx
# 将最大值放到右边
if max_idx != right:
arr[right], arr[max_idx] = arr[max_idx], arr[right]
left += 1
right -= 1
return arr
# 测试双向选择排序
test_arr = [64, 34, 25, 12, 22, 11, 90]
print("双向选择排序:", selection_sort_bidirectional(test_arr.copy()))
选择排序性能测试
import time
import random
def test_performance():
"""测试不同规模数据的性能"""
sizes = [100, 1000, 5000]
for size in sizes:
# 生成随机数组
arr = [random.randint(1, 10000) for _ in range(size)]
# 计时
start_time = time.time()
selection_sort(arr.copy())
end_time = time.time()
print(f"数据规模 {size}: {end_time - start_time:.4f} 秒")
# 运行性能测试
test_performance()
选择排序的实际应用示例
def sort_students_by_grade(students):
"""
使用选择排序对学生成绩进行排序
"""
n = len(students)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if students[j]['grade'] < students[min_idx]['grade']:
min_idx = j
students[i], students[min_idx] = students[min_idx], students[i]
return students
# 测试学生成绩排序
students = [
{'name': '张三', 'grade': 85},
{'name': '李四', 'grade': 92},
{'name': '王五', 'grade': 78},
{'name': '赵六', 'grade': 95},
{'name': '刘七', 'grade': 88}
]
sorted_students = sort_students_by_grade(students.copy())
print("按成绩排序:")
for student in sorted_students:
print(f"{student['name']}: {student['grade']}分")
选择排序的优缺点
def selection_sort_analysis():
"""
选择排序分析
"""
analysis = {
"时间复杂度": {
"最好情况": "O(n²) - 即使已经排好序，也需要比较所有元素",
"最坏情况": "O(n²) - 逆序排列时",
"平均情况": "O(n²)"
},
"空间复杂度": "O(1) - 原地排序",
"稳定性": "不稳定 - 相同元素可能会交换位置",
"比较次数": "n(n-1)/2 次比较",
"交换次数": "n-1 次交换（最好情况也是n-1次）"
}
print("选择排序分析:")
for key, value in analysis.items():
print(f"{key}: {value}")
selection_sort_analysis()
实操建议：
- 代码调试：使用print语句查看每一轮的变化
- 边界测试：测试空数组、单元素数组、已排序数组
- 性能优化：对于小规模数据（<1000）选择排序性能尚可
- 实际应用：适合数据量小或对内存要求严格的场景
选择排序虽然效率不高，但实现简单、逻辑清晰,是理解排序算法的重要基础。
