概念

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下：

  • 首先在未排序序列中找到最小（大）元素，存放在排序序列的起始位置，即第一个位置。
  • 然后再将剩余未排序元素中继续寻找最小（最大）元素，放在第二个位置。
  • 以此类推，直到所有元素均排序完毕。

总结：先找出最大（最小）的元素，放在第一位或者最后一位。以找出最大的放在第一位为例，先找出最大的放在第一位，再在剩下的元素找出最大的元素，放在第二位，依次进行，直到遍历到最后一个元素，排序结束。选择选的就是最大或者最小的的，相当于挑高个，挑完最高的，再挑次高的，直到结束。

排序过程

image.png
image.png

时间复杂度

最优时间复杂度：O（n^2）
最坏时间复杂度：O(n^2)
稳定性：不稳定（考虑升序每次选择最大的情况）

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def selection_sort(alist):
    """
    :param alist:
    :return: alist
    思想就是不断找出最小的放在最前面
    以alist = [10,1,3,2,5,7,6,4]为例，n=8
    第一次是把1放在最前面
    """
    n = len(alist)  # 8
    for i in range(n): # 0-7
        # 下面一段代码是为了找到最小值
        min_index = i
        for j in range(i,n): #0-7
            if alist[min_index] > alist[j]:
                min_index = j
        # 下面一段代码是为了交换最小值
        if min_index != i:
            alist[i],alist[min_index] = alist[min_index],alist[i]

    return alist

程序可以看成两段，一段是找到剩下里面最小的元素，一段是交换最小值，这两步就可以完成排序，时间复杂度为O(n^2)，注意写代码的时候，这两段要分开写，思路更加清晰一些，注意索引的值，可以代入最小时和最大时去检验,这样可以有效避免索引出错。