选择排序(python实现）

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。

算法步骤

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

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

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

# -*- coding:utf-8 -*-
def selection_sort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        min_index = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        # i 不是最小数时，将 i 和最小数进行交换
        if i != min_index:
            arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr


if __name__ == '__main__':
    array = [2, 4, 1, 3, 5, 8, 7, 8, 4, 9]
    print selection_sort(array)

选择排序复杂度

1.时间复杂度：

• 平均时间复杂度：O(n^2)
• 最大时间复杂度：O(n^2)
• 最小时间复杂度：O(n^2)

2. 空间复杂度：O(1)
3. 稳定性：不稳定
   比如序列5 8 5 2 9，第一遍选择第1个元素5和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

选择排序VS冒泡排序

• 冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置
• 选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。