Python3排序算法02 - 选择排序

原创

Madman

9361 次阅读

Synopsis: 选择排序算法每次从 "未排序序列" 中继续寻找最小（大）元素，然后放到 "已排序序列" 的末尾。它的时间复杂度为O(n^2)，当待排序序列的元素个数很多时，性能很差

代码已上传到 https://github.com/wangy8961/python3-algorithms ，欢迎star

1. 算法介绍

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下：

首先在未排序序列中找到最小（大）元素，存放到已排序序列的起始位置
然后，再从剩余未排序序列中继续寻找最小（大）元素，然后放到已排序序列的末尾
以此类推，直到所有元素均排序完毕

Selection Sort 01

2. Python实现

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

Selection Sort 02

def selection_sort(L):
    '''选择排序，升序'''
    n = len(L)
    if n <= 1:
        return

    for i in range(n-1):  # 共需要n-1次选择操作
        min_index = i  # 首先假设 "未排序列表"(上图中非绿色框) 的最小元素是它的第1个元素，第1次选择操作则假设L[0]是最小的，第2次操作则假设L[1]是最小的

        for j in range(i+1, n):  # 找出 "未排序列表" 中真正的最小元素的下标
            if L[j] < L[min_index]:
                min_index = j

        if min_index != i:  # 如果 "未排序列表" 中真正的最小元素，不是之前假设的元素，则进行交换
            L[i], L[min_index] = L[min_index], L[i]


if __name__ == '__main__':
    L1 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print('Before: '