本文共 4463 字，大约阅读时间需要 14 分钟。

（1）基本逻辑

选择排序（Selection sort）是一种简单直观的排序算法，先假定最左边索引就是最小值，然后再把这个假定的值和其他比较，如果确实是最小值就不变动位置，否者变动位置。

先找最小值，升序排序步骤如下：

• 首先，假设最左边元素为最小值(min_index = 0)
• 其次，假设的最小值和其他元素比较，从左到右，相邻2个元素依次比较大小，最终找到最小值的索引
• 然后，判断假设的最小值的索引是否与真实的最小值的索引一样，不一样就直接互换元素的位置，这样第一次循环就确定了所有元素中最小值的位置
• 最后，紧接着假设min_index = 1,依次重复如上步骤，找到其余元素中的最小值，直到假设的最小索引为倒数第二个元素的索引为止（倒数第二个与最后一个比较一次就结束了）

选择排序的主要优点:

• 每次循环一遍，比较完所有元素之后，找到最小（大）值之后，才会互换位置，否者不会互换位置
• 如果某个元素位于正确的最终位置上，则它不会被移动
• 如果列表为n个元素，那么所有元素最多进行n-1次交换（每个元素都换到非自己本身的位置）
• 如果所有元素都需要移动位置，选择排序属于非常好的一种

下图是每次找到最小值的索引，然后替换：

如下图是每次找到一个最大值的索引，然后替换：

（2）算法分步解析

1.升序中：假设最左边索引位置是最小值

myList = [12, 2, 3, 22, 1, 9, 10, 11]n = len(myList)min_index = 0  # 假设最左边为最小值for i in range(1, n):  						# 需要拿最小索引右边的所有元素与假设的比较    if myList[min_index] > myList[i]:        min_index = i        print("------>", min_index, myList[min_index])    print("==", min_index, myList[min_index])if min_index != 0:    myList[min_index], myList[0] = myList[0], myList[min_index]print(myList)

------> 1 2		# 第一次假设，发现索引1的位置，值为2的为最小值== 1 2== 1 2== 1 2------> 4 1		# 第四次假设，发现索引4的位置，值为1的为最小值== 4 1== 4 1== 4 1== 4 1[1, 2, 3, 22, 12, 9, 10, 11]

• 第0次假设，拿myList[0] 与 （1， n-1）区间索引的值依次比较，哪个值小，哪个就是最小值索引，最终判断是否需要替换，把最小值放在了最左边了
• 我们假设n-1次（n是列表的总数），就能确定n个数的具体位置

2.升序中：假设最右边索引位置是最大值

myList = [12, 2, 3, 22, 1, 9, 10, 11]n = len(myList)max_index = n - 1                       # 假设最右边为最大值的索引for i in range(n-1):                    # 需要拿n-1索引对应的数值与索引0---->n-2对应的数值依次比较，最终确定最大值的索引    if myList[max_index] < myList[i]:        max_index = i        print("------>", max_index, myList[max_index])    print("==", max_index, myList[max_index])if max_index != n-1:    myList[max_index], myList[n-1] = myList[n-1], myList[max_index]print(myList)

------> 0 12== 0 12== 0 12== 0 12------> 3 22== 3 22== 3 22== 3 22== 3 22[12, 2, 3, 11, 1, 9, 10, 22]

• 第0次假设，拿myList[n-1] 与 （0， n-2）区间索引的值依次比较，哪个值最大，哪个就是最大值索引，最终判断是否需要替换，把最大值放在了最右边
• 我们假设n-1次（n是列表的总数），就能确定n个数的具体位置

3.倒序中：假设最左边索引位置是最大值

myList = [12, 2, 3, 22, 1, 9, 10, 11]n = len(myList)max_index = 0                      for i in range(1, n-1):                        if myList[max_index] < myList[i]:        max_index = i        print("------>", max_index, myList[max_index])    print("==", max_index, myList[max_index])if max_index != 0:    myList[max_index], myList[0] = myList[0], myList[max_index]print(myList)

4.倒序中：假设最右边索引位置是最小值

myList = [12, 2, 3, 22, 1, 9, 10, 11]n = len(myList)min_index = n-1for i in range(n-1):    if myList[min_index] > myList[i]:        min_index = i        print("------>", min_index, myList[min_index])    print("==", min_index, myList[min_index])    if min_index != n-1:    myList[min_index], myList[n-1] = myList[n-1], myList[min_index]print(myList)

（3）完整算法

1.升序：假设最左边为最小值

myList = [12, 2, 3, 22, 1, 9, 10, 11]n = len(myList)min_index = 0  # 假设最左边为最小值for m in range(n - 1):    min_index = m					# 每次外循环的时候，能确定内循环里面假设的最小索引位置    for i in range(1 + m, n):       # 需要拿最小索引右边的所有元素与假设的比较        if myList[min_index] > myList[i]:            min_index = i            print("------>", min_index, myList[min_index])                if min_index != m:        myList[min_index], myList[m] = myList[m], myList[min_index]    print("==", min_index, myList[min_index], myList)

------> 1 2------> 4 1== 4 12 [1, 2, 3, 22, 12, 9, 10, 11]== 1 2 [1, 2, 3, 22, 12, 9, 10, 11]== 2 3 [1, 2, 3, 22, 12, 9, 10, 11]------> 4 12------> 5 9== 5 22 [1, 2, 3, 9, 12, 22, 10, 11]------> 6 10== 6 12 [1, 2, 3, 9, 10, 22, 12, 11]------> 6 12------> 7 11== 7 22 [1, 2, 3, 9, 10, 11, 12, 22]== 6 12 [1, 2, 3, 9, 10, 11, 12, 22]

2.倒序：假设最右边为最大值

myList = [8, 2, 3, 6, 1, 9, 22, 11]n = len(myList)for m in range(n-1, 0, -1):		# 最外层，解决的是设置最大值索引的循环    max_index = m    for i in range(m):      	 # 需要对比的是，0---->m-1 索引的值与假设值的对比,range()函数左闭右开        if myList[max_index] < myList[i]:            max_index = i            print("------>", max_index, myList[max_index])    if max_index != m:        myList[max_index], myList[m] = myList[m], myList[max_index]    print("==", max_index, myList[max_index], myList)

注意点：

• 升序时候，假设最右边n-1为最大值的时候：需要与0--------> n-2对应的值对比，最终找到最大值
• 每次最外层循环，确定最大值索引位置的时候，需要max_index = m赋值，然后假设失败再修改max_index这个值
• 注意，内循环的时候，如果设定右为最大值或最小值，range(m)本身就是0------> m-1

------> 6 22== 6 11 [8, 2, 3, 6, 1, 9, 11, 22]== 6 11 [8, 2, 3, 6, 1, 9, 11, 22]== 5 9 [8, 2, 3, 6, 1, 9, 11, 22]------> 0 8== 0 1 [1, 2, 3, 6, 8, 9, 11, 22]== 3 6 [1, 2, 3, 6, 8, 9, 11, 22]== 2 3 [1, 2, 3, 6, 8, 9, 11, 22]== 1 2 [1, 2, 3, 6, 8, 9, 11, 22]

（4）时间复杂度

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

（5）选择排序演练

转载地址：http://yteab.baihongyu.com/