【和我一起学算法】排序篇——冒泡排序

与前一篇的讲的冒泡排序相比，选择排序更加简单粗暴，就是在数列中不断的寻找最大或最小的那个数。

目录

选择排序

原理

举例

第一轮排序

第二轮排序

第三轮排序

第四轮排序

第五轮排序

算法伪代码

 完整源码

选择排序

原理

选择排序总是在数列中寻找最大或最小的那个数，将这个最大或最小数放在合适的位置，然后再抛开这个数，从其他数中再找一个最大或最小数，一直到子序列为空为止。选择排序和冒泡排序不同的是，选择排序并不是像冒泡排序那样比较相邻两个数的大小，而是在整个数列里找最大或最小数。

举例

还是以数列[7,3,5,1,9,4]为例，初始数列如下：

初始队列

7

3

5

1

9

4

第一轮排序

以数列中的第一个数7为基准，找数列中最小的那个数，如果找到了最小的那个数，就交换位置。

以7为基准，找最小，1最小，1和7互换位置。

第一轮 7和1互换位置

1

3

5

7

9

4

第二轮排序

以数列中第二个数3为基准，在抛开1的子序列中找最小的那个数，子序列中没有比3更小的，不用交换位置。

第三轮排序

以数列中第三个数5为基准，在抛开1和3的子序列中找最小数，子序列中4比5小，4和5互换一下位置。

第三轮排序 4和5互换位置

1

3

4

7

9

5

第四轮排序

以数列中第四个数7为基准，在子序列7、9、5中找比7小的数，5比7小，互换位置。

第四轮 7和5互换位置

1

3

4

5

9

7

第五轮排序

以数列中第五个数9为基准，在子序列9、7中找最小数，7比9小，互换位置。

第五轮 9和7互换位置

1

3

4

5

7

9

选择排序完成，一个六个数，排序了五次，理论上选择排序的时间复杂度是，但是在Python中有点特殊，Python中有个min(iList[i:])可以找到最小数，因此时间复杂度会降到。因此在Python版本在的排序算法中，选择排序是最快速的。

算法伪代码

for i in range(0, len(iList)-1):
    minIndex = i
    for j in range(i+1, len(iList)-1):
        if iList[j] <= iList[minIndex]:
            minIndex = j

 完整源码

from randomList import randomList
import timeit

iList = randomList(20)

def selectionSort(iList):
    if len(iList) <= 1:
        return iList
    for i in range(0, len(iList)-1):
        if iList[i] != min(iList[i:]): #使用min函数找到剩余数列中最小的那个数
            minIndex = iList.index(min(iList[i:])) #minIndex是最小数的序号(下标)
            iList[i], iList[minIndex] = iList[minIndex], iList[i]
        # print("第 %d 轮排序结果:" %(i+1), end="")
        # print(iList)
    return iList

if __name__ == "__main__":
    print(iList)
    print(selectionSort(iList))
    print(timeit.timeit("selectionSort(iList)", "from __main__ import selectionSort,iList", number=100))

晚上在更一篇插入排序，排序算法算是比较简单的，我会尽快过掉，排序篇过后会写查找篇，查找也属于基础算法，也会尽快过。之后是数组、字符串、链表、树相关算法，最后会讲讲动态规划之类的。我一有时间就更，不会鸽的。【狗头】