图解排序算法及实现——选择排序（Selection sort）

柔情只为你懂 2022-05-14 05:15 140阅读 0赞

**选择排序（Selection sort）**是一种简单直观的排序算法，也叫直接选择排序。

## 思路 ##

设 左边为有序区，右边乱序区。从右边剩下的乱序数字中找最小，放到左边。（反过来也是可以的）

具体操作： 多次比较，一次交换。每次从右边剩余数字中选最小，与乱序区最左边的元素交换，使左边有序区边界右移。

### 复杂度 ###

平均时间复杂度 О(n²)  
最坏时间复杂度 О(n²)  
最优时间复杂度 О(n²)

## 图例 ##

推荐[VisuAlgo][]，一个数据结构和算法动态可视化的网站。

![这里写图片描述][SouthEast]  
图片来源： [【图解算法】排序算法——冒泡排序、选择排序][Link 1]  
![selection_sort_animation.gif][]  
![这里写图片描述][Selection-Sort-Animation.gif]  
来源：维基百科

## python实现 ##

def SelectionSort(arr):
        ''' 
        选择排序思路：左边有序区，右边乱序区。从右边剩下的乱序数字中找最小，放到左边。（反过来也是可以的）
    
        具体操作： 多次比较，一次交换。每次从右边剩余数字中选最小，与乱序区最左边的元素交换，
                  使左边有序区边界右移。
    
        复杂度： O(n^2)
        '''
        n = len(arr)
    
        # arr为空和arr只有一个元素时，不进入以下循环，不执行任何操作。 
        # 即暗含了边界检查： if n==1 or n==0: return lst
        # 以下各Sort()函数同理
        for i in range(n):
    
            # 多次比较：寻找[i, n-1]区间里的最小值
            minIndex = i
            for j in range(i+1,n):
                if arr[j]<arr[minIndex]:
                    minIndex = j
    
            # 一次交换
            if i != minIndex:
                arr[i],arr[minIndex] = arr[minIndex],arr[i]

[VisuAlgo]: https://visualgo.net/zh
[SouthEast]: /images/20220514/202b2816a0fd44148fdc84ae854fe178.png
[Link 1]: https://blog.csdn.net/xiaoping0915/article/details/72615195
[selection_sort_animation.gif]: http://bubkoo.qiniudn.com/selection_sort_animation.gif
[Selection-Sort-Animation.gif]: http://bubkoo.qiniudn.com/Selection-Sort-Animation.gif