Python3排序算法02 - 选择排序

  • 原创
  • Madman
  • /
  • /
  • 0
  • 1622 次阅读

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

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

1. 算法介绍

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

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

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: ', L1)
    
                                
                            
未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3排序算法02 - 选择排序

分享

作者

作者头像

Madman

如需 Linux / Python 相关问题付费解答,请按如下方式联系我

0 条评论

暂时还没有评论.