博客

选择排序算法

算法描述

选择排序算法（Selection Sort）的基本思路是：
– 首先，找到数组中最小的元素并记录其下标；
– 其次，将最小的元素与数组第一个元素进行交换；
– 然后，在剩下的元素中找到最小的元素并记录其下标，将最小元素与数组中的第二个元素进行交换；
– 如此重复，直到整个数组排序完成。

算法实现

Python代码：

def selection_sort(arr):
    n = len(arr)
    for i in range(n-1):
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

算法分析

选择排序算法的时间复杂度为$O(n^2)$，因为每一轮需要遍历剩余元素一遍。虽然其时间复杂度很高，但是简单易懂，实现容易，而且不需要额外的空间，因此在某些特殊情况下选用选择排序仍然是不错的选择。

示例说明

示例一

我们来看一个选手比赛得分排序的例子：

grade = [88, 70, 95, 99, 82, 75, 92]

sorted_grade = selection_sort(grade)

print(sorted_grade)

输出结果为：

[70, 75, 82, 88, 92, 95, 99]

示例二

下面我们来看一个字符串列表排序的例子：

words = ['hello', 'world', 'apple', 'banana', 'cat', 'dog']

sorted_words = selection_sort(words)

print(sorted_words)

输出结果为：

['apple', 'banana', 'cat', 'dog', 'hello', 'world']

可以发现，选择排序算法并不仅限于数字的排序，同样适用于字符串的排序。