7.选择排序-python

[ruotongyu (Dongle)]

选择排序与插入排序类似。

维护有序序列：

# 选择排序
class SelectionSort:
    def sort(self, data):
        length = len(data)
        if length <= 1:
            return
        # 选择每一个元素
        for i in range(length):
            min_index = i
            min_value = data[i]
            # 找出后续最小元素的值和位置
            for j in range(i, length):
                if data[j] < min_value:
                    min_index = j
                    min_value = data[j]
            # 交互位置
            data[i], data[min_index] = data[min_index], data[i]

if __name__ == '__main__':
    selection_sort = SelectionSort()
    data = [5, 2, 1, 4, 10, 3, 6, 7]
    selection_sort.sort(data)
    assert data == [1, 2, 3, 4, 5, 6, 7, 10]

时间复杂度

• 最好：O(n²)
• 最坏：O(n²)
• 平均：O(n²)

空间复杂度
O(1)

稳定