6.2选择排序（python数据结构与算法）

红太狼 2021-05-12 11:50 465阅读 0赞

**选择排序 \[Selection sort\]** 是一种简单直观的排序算法。  
**工作原理如下**：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

选择排序算法运作如下（从小到大排列）：

*  第一次找最大的放至最后，第二次找次大的放至最后，以此类推…
 *  需要加入一个变量记录每次找到最大的值的索引，然后与最后一个进行交换
 *  一开始，令0索引为最大值所对应的索引，直至找到真正最大值的索引，将最大值与最后位置的元素，互换位置，这样第一次迭代就结束了。然后是找次大的，再是找第三大的…

# 选择排序分析 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70]

*  红色表示当前最小值
 *  黄色表示已排好的序列
 *  蓝色表示当前位置

![在这里插入图片描述][20200621191638773.gif]

#### 实现： ####

def select_sort(alist):
        """选择排序"""
        length = len(alist)
    
        # 外层for循环决定需要排几次
        for iter_num in range(length-1):
            max_value_index = 0
    
            # 内层for 循环找最大的索引
            for index in range(1, length-iter_num):
                if alist[index] > alist[max_value_index]:
                    max_value_index = index
    
            # 找完后，将最大的放至最后
            alist[max_value_index], alist[length-1-iter_num] = alist[length-1-iter_num], alist[max_value_index]
    
    
    if __name__ == "__main__":
        alist = [26,54,93,17,77,31,44,55,20]
        # alist = [17, 20, 26, 31, 44, 54, 55, 77, 93]
        select_sort(alist)
        print(alist)

## 时间复杂度 ##

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

## 选择排序演示 ##

时间复杂度：O( n 2 n^2 n2)

*  稳定性：不稳定（考虑升序每次选择最大的情况）

## 选择排序演示 ##

![在这里插入图片描述][20200621191702594.gif]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70]: /images/20210511/17fdaa17a3cd455da6164f96d3c86728.png
[20200621191638773.gif]: /images/20210511/367c4d1a17334cb3b4e423e5690aace0.png
[20200621191702594.gif]: /images/20210511/92d20788ad7f4d89a5374fbc789f8e84.png