Day2 选择排序

交作业：
def selection_sort(mylist):
for i in range(len(mylist)):
current_max = select_max(mylist[:len(mylist)-i])
mylist[-1-i],mylist[mylist.index(current_max)]= mylist[mylist.index(current_max)] ,mylist[-1-i]
return mylist

def select_max(list1):
mymax = list1[0]
for i in list1[1:]:
if mymax < i:mymax =i
return mymax

def test_selection_sort():
assert selection_sort([0, 5, 2, 3, 2]) == [0, 2, 2, 3, 5]
assert selection_sort([-2, -45, -5]) == [-45, -5, -2]
assert selection_sort([-23, 0, 6, -4, 34]) == [-23, -4, 0, 6, 34]

---

title: day2：选择排序
date: 2020-05-24 19:00:24
tags: python
categories: 算法原理

---

1. 算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

2. 动图演示

image

3.时间复杂度与空间复杂度

• 无论是有序还是逆序列表，选择排序需要的比较次数均为(n-1)*n/2，所以:

C_min = C_max = =O(n²)

• 如果是有序列表，那么交换顺序为0，如果是逆序列表，那么交换顺序为3*n，所以：

M_min = 0, M_max==O(n)

• 从这里来看，选择排序是以牺牲时间换空间的一种排序方式，即增加了数据的读取，而减少了内存的占用

4.选择排序算法的实现步骤

错误示范

def select_fun(list1):
    n = len(list1)
    for i in range(n-1):  # 开启循环，只需要循环n-1次即可,
        # 假设第i个值为最小值，min_value = list1[i]
        for j in range(i+1, n):  # j 输入i后面的数字
            if list1[j] < list1[i]:  # 如果发现后面存在比最小值档还小的数
                list1[i], list1[j] = list1[j], list1[i]  # 交换顺序
    return list1


if __name__ == '__main__':
    list2 = [3, 5, 6, 1, 2]
    print(select_fun(list2))
    """
    # 输出结果
    [1, 2, 3, 5, 6]
    """

• 此代码中虽然也没有太大问题，但是循环中只要找到小的就交换一次，增加了内存占用。
• 实际应该为在单次循环时不进行位置交换，而是单次循环后再进行位置交换

正确示范

def select_fun(list1):
    n = len(list1)
    count = 0  # 统计更改次数
    for i in range(n-1):  # 开启循环，只需要循环n-1次即可,
        min_index = i
        for j in range(i+1, n):  # j 输入i后面的数字
            if list1[j] < list1[min_index]:  # 如果发现后面存在比最小值档还小的数
                min_index = j  # 这里暂时不更改位置，等循环结束后再更改
        if min_index != i:  # 判断当前的最小值是不是i所在位置
            list1[i], list1[min_index] = list1[min_index], list1[i]
            count += 1
    print('交换次数', count)
    return list1


if __name__ == '__main__':
    list2 = [3, 5, 6, 1, 2]
    print(select_fun(list2))
    """
    # 输出结果
    交换次数 4
    [1, 2, 3, 5, 6]
    """

• 每交换一次都会增加额外的内存地址，可以看出真正的选择算法可以明显减少内存空间占用。
• 感兴趣的小伙伴可以看看上面的交换次数是多少次