选择排序之python

选择排序( Selection sort）

1.算法描述：

通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n)个记录进行交换。

对尚未完成排序的所有元素，从头到尾比一遍，记录下最小的那个元素的下标，也就是该元素的位置，
把该元素交换到当前遍历的最前面。
其效率之处在于，每一轮中比较了很多次，但只交换一次，
因此虽然它的时间复杂度也是O(n^2)，但比冒泡算法还是要好一点。

2.算法属性:

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：不稳定
不稳定性介绍：list里面重复元素可能会因选择后改变前后顺序
O(1) 额外的空间
O(n2 ) 对比
O(n) 互换
不具有适应性：不像冒泡那样可以加flag来改善

3.代码实现

#kumata's code

#算法复杂度O(n^2)

#找到最小的元素就和第一个index交换

#从小到大排

import time

def selection_sort(nums=list):

    start = time.time()

    #第一层选择第n小的元素下标

    for i in range(len(nums)):    # n

        pos_min = i     # Index

        #第二层遍历找出需要交换的元素下标

        for j in range(i + 1,len(nums)):

            if nums[pos_min] > nums[j]:

                pos_min = j

        #交换嘻嘻

        nums[i],nums[pos_min] = nums[pos_min],nums[i]

    t = time.time() - start

    return nums,t

nums = [1,2,5,8,4,3,6]

selection_sort(nums)

#输出结果

([1, 2, 3, 4, 5, 6, 8], 0.0)

巴特西

选择排序之python

选择排序( Selection sort）

1.算法描述：

2.算法属性:

3.代码实现

最新文章

热门文章