选择排序的 Python 算法实现和一些测试代码。

select_sort.py

# 选择排序：每一轮选择最小的元素排在前面
from sort.sort_helper import generate_random_nums, check_sorted


def swap(nums, idx1, idx2):
    if idx1 == idx2:
        return
    temp = nums[idx1]
    nums[idx1] = nums[idx2]
    nums[idx2] = temp


def select_sort_1(nums):
    '''
    选择排序第 1 版，遇到比开始的元素小的元素，就交换位置
    :param nums:
    :return:
    '''
    n = len(nums)

    for i in range(n):
        for j in range(i + 1, n):
            if nums[j] < nums[i]:
                swap(nums, i, j)
    return nums


def select_sort_2(nums):
    '''
    选择排序第 2 版，记录最小元素的索引，最后才交换位置
    :param nums:
    :return:
    '''
    n = len(nums)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if nums[j] < nums[min_index]:
                min_index = j
        swap(nums, i, min_index)


if __name__ == '__main__':
    nums1 = generate_random_nums(1000, 1, 10)
    origin_nums = nums1.copy()
    select_sort_1(nums1)
    check_sorted(origin_nums, nums1)

    nums2 = generate_random_nums(1000, 1, 10)
    origin_nums = nums2.copy()
    select_sort_2(nums2)
    check_sorted(origin_nums, nums2)

sort_helper.py

import random
import time


def swap(nums, index1, index2):
    if index1 == index2:
        return
    temp = nums[index1]
    nums[index1] = nums[index2]
    nums[index2] = temp


def generate_asc_nums(minimum, maximum):
    return [_ for _ in range(minimum, maximum)]


def generate_desc_nums(minimum, maximum):
    '''
    生成的倒序数组包含最大值和最小值
    :param minimum:
    :param maximum:
    :return:
    '''
    return [_ for _ in range(maximum, minimum - 1, -1)]


def generate_random_nums(nums_count, minimum, maximum):
    nums = []
    for i in range(nums_count):
        # 生成的随机整数包括 minimum 和 maximum
        nums.append(random.randint(minimum, maximum))
    return nums


def check_sorted(origin_nums, your_sort_nums):
    if len(origin_nums) != len(your_sort_nums):
        return False
    python_sorted = sorted(origin_nums)
    for your_num, python_num in zip(your_sort_nums, python_sorted):
        if your_num != python_num:
            raise Exception('你的排序算法不正确！')
    print("你的排序算法正确！")


def test_your_sort_algorithm(your_sort_algorithm):
    desc_nums = generate_desc_nums(10, 900)
    origin_nums = desc_nums.copy()
    begin = time.time()
    your_sort_algorithm(desc_nums)
    end = time.time()
    check_sorted(origin_nums, desc_nums)
    print('倒序数组排序测试通过！使用时间：{}'.format(end - begin))

    desc_nums = generate_random_nums(2000, 1, 2000)
    origin_nums = desc_nums.copy()
    begin = time.time()
    your_sort_algorithm(desc_nums)
    end = time.time()
    check_sorted(origin_nums, desc_nums)
    print('随机数组排序测试通过！使用时间：{}'.format(end - begin))

    desc_nums = generate_asc_nums(10, 900)
    origin_nums = desc_nums.copy()
    begin = time.time()
    your_sort_algorithm(desc_nums)
    end = time.time()
    check_sorted(origin_nums, desc_nums)
    print('正序数组排序测试通过！使用时间：{}'.format(end - begin))


def swap(nums, index1, index2):
    if index1 == index2:
        return
    temp = nums[index1]
    nums[index1] = nums[index2]
    nums[index2] = temp


def generate_random_array(n):
    return [random.randint(10, 100) for _ in range(n)]


def generate_asc_array(min, max):
    return [_ for _ in range(min, max)]


def simple_check_sorted(nums):
    for i in range(0, len(nums) - 1):
        if nums[i] > nums[i + 1]:
            raise Exception('数组不是排好序的')
    print("排序正确！")

select_sort.py 这个文件在引入 sort_helper.py 文件的时候，有个包名，朋友们可以自行在自己的环境中作调整。