Python选择排序案例如何实操编写

本文目录导读：

1. 基础选择排序算法
2. 带详细注释的版本
3. 降序选择排序
4. 选择排序的变体 - 同时选择最大最小值
5. 选择排序性能测试
6. 选择排序的实际应用示例
7. 选择排序的优缺点
8. 实操建议：

我来详细介绍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()

实操建议：

1. 代码调试：使用print语句查看每一轮的变化
2. 边界测试：测试空数组、单元素数组、已排序数组
3. 性能优化：对于小规模数据（<1000）选择排序性能尚可
4. 实际应用：适合数据量小或对内存要求严格的场景

选择排序虽然效率不高，但实现简单、逻辑清晰,是理解排序算法的重要基础。