Python实现选择排序

标签: 选择  排序  算法

选择排序简介
选择排序(Selection sort)是一种简单直观的排序算法。
简单来说就是从无序队列里面挑选最小的元素,和无序队列头部元素替换(放到有序队列中),最终全部元素形成一个有序的队列。
选择排序原理
首先在未排序序列中找到最小(大)元素,和无序队列的第一个元素替换位置,(即形成有序队列)
以此类推,直到所有元素全部进入有序队列,即排序完毕。

 

上代码:

def section_sort(alist):
    n = len(alist)
    # 定义外围循环次数
    for j in range(n - 1):
        # 定义min_index最小值的索引为j,目的找出最小值
        min_index = j
        # cur下标移动的范围,比较次数的范围限定
        for i in range(j + 1, n):
            # 元素比较,找出最小的值对应的索引
            if alist[i] < alist[min_index]:
                # 移动到最小元素的位置
                min_index = i

        # 保证最新的min_index不在无序队列的首位,那么就将它和无序队列的首位替换
        if min_index != j:
            alist[j], alist[min_index] = alist[min_index], alist[j]


if __name__ == "__main__":
    alist = [9, 8, 7, 6, 5, 4, 3, 2, 1]
    print("排序前:",alist)
    section_sort(alist)
    print("排序后:",alist)

关键点:
    1、mix标签初始化:min_index = j
    2、比较循环的范围:for i in range(j+1,n)
    3、元素替换的条件:if min_index != j
    4、排序次数范围的确定:for j in range(n-1)

时间复杂度

最优时间复杂度:O(n2) 
对于无序队列选取最小元素时候,所有数值都进行了比较。所以内部的最优时间复杂度是O(n)
对于选择排序的外部循环,只和无序列表元素个数相关,元素个数是n个,,所以外部的最优时间复杂度是O(n)
所以整体来说,对于选择排序的时间复杂度就是O(n2)

最坏时间复杂度:O(n2)
因为最好的时间复杂度就是O(n2)了,所以最坏的时间复杂度还是O(n2)

稳定性: 稳定(看情况)

 

思考:
改那个地方,结果是降序?
if alist[i] < alist[min_index]: 代码中的 < 改为 >
本节内容小结:
1、选择排序原理:无序最小第一交换,数次over。
2、选择排序实践步骤:无序选小,小一替换-外部选择循环-异常考虑

原文链接:加载失败,请重新获取