选择排序

简介

选择排序（selection sort）的工作原理非常简单：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。

特性

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$
• 非稳定性排序

示例

Python

def selection_sort(nums: list[int]):
    """选择排序"""
    n = len(nums)
    # 外循环：未排序区间为 [i, n-1]
    for i in range(n - 1):
        # 内循环：找到未排序区间内的最小元素
        k = i
        for j in range(i + 1, n):
            if nums[j] < nums[k]:
                k = j  # 记录最小元素的索引
        # 将该最小元素与未排序区间的首个元素交换
        nums[i], nums[k] = nums[k], nums[i]


"""Driver Code"""
if __name__ == "__main__":
    nums = [4, 1, 3, 1, 5, 2]
    selection_sort(nums)
    print("选择排序完成后 nums =", nums)

Go

/* 选择排序 */
func selectionSort(nums []int) {
    n := len(nums)
    // 外循环：未排序区间为 [i, n-1]
    for i := 0; i < n-1; i++ {
        // 内循环：找到未排序区间内的最小元素
        k := i
        for j := i + 1; j < n; j++ {
            if nums[j] < nums[k] {
                // 记录最小元素的索引
                k = j
            }
        }
        // 将该最小元素与未排序区间的首个元素交换
        nums[i], nums[k] = nums[k], nums[i]

    }
}