跳转至

选择排序

假设你的计算机存储了很多乐曲。对于每个乐队,你都记录了其作 品被播放的次数。

你要将这个列表按播放次数从多到少的顺序排列,从而将你喜欢的乐队排序。该如何做呢? 一种办法是遍历这个列表, 找出作品播放次数最多的乐队, 并将该乐队添加到一个新列表中

再次这样做,找出播放次数第二多的乐队。

继续这样做,你将得到一个有序列表。

python实现

需要额外的存储空间

def select_sort(seq):
    new_seq = []
    seq_cp = list.copy(seq)

    for i in range(len(seq)):
        min_elem = min(seq_cp)
        new_seq.append(min_elem)
        seq_cp.remove(min_elem)

    return new_seq


def test_select_sort():
    seq = list(range(10))

    import random
    random.shuffle(seq)

    assert(select_sort(seq)==sorted(seq))

不需要额外的空间

def select_sort(seq):
    for i in range(len(seq)):
        seq[i] = min(seq[i:])


def test_select_sort():
    seq = list(range(10))

    import random
    random.shuffle(seq)
    select_sort(seq)

    assert(seq==sorted(seq))
def select_sort(seq):

    for i in range(len(seq)):
        _min = seq[i]

        for j in range(i+1, len(seq)):
            if seq[j] < _min:
                _min = seq[j]
        seq[i] = _min


def test_select_sort():
    seq = list(range(10))

    import random
    random.shuffle(seq)
    select_sort(seq)

    assert(seq==sorted(seq))
    assert(0)