今天看啥  ›  专栏  ›  Python之战

python实现选择排序算法

Python之战  · 简书  ·  · 2019-04-15 23:06

文章预览

选择排序,简单而直观,其原理是把序列中的最小值或者最大值找出来放在起始位置,然后再从剩下的序列中找出极值放到起始位置之后,以此类推最后就完成排序。

完成这个过程大致思想:首先需要一个记录器,记录排序排到第几个位置了,然后在剩余的序列中找到极值下标,最后将记录器位置和极值位置元素交换,完成本次选择排序。

用python实现比较简单:

def select_sort(items):
    n = len(items)
    for cur in range(n-1):
       item_max = cur
       for i in range(cur+1, n):
           if items[i] > items[item_max]:
               items[i], items[item_max] = items[item_max], items[i]
       if item_max != cur:
           items[cur], items[item_max] = items[item_max], items[cur]

image

关于选择排序的时间复杂度:

选择排序的交换操作介于 0 和 (n - 1) 次之间。选择排序的比较操作为 n (n - 1) / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1) 次之间。

比较次数O(n^2),比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。交换次数O(n),最好情况是,已经有序,交换0次;最坏情况交换n-1次,逆序交换n/2次。交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。

………………………………

原文地址:访问原文地址
快照地址: 访问文章快照
总结与预览地址:访问总结与预览