选择排序

选择排序的思想是有 n 个数，先假定第一个数最小，然后从剩下 n-1 个数中选择一个最小的与第一个数交换（如果当前数已经是最小的就不需要交换了）。同理从剩余数列中再选择一个最小的与第二个数交换，以此类推，直到数列中只剩下一个数。

#!/usr/bin/env python3
def select_sort(arr):
    i = 0
    n = len(arr)
    while i < n - 1:  # 总共需要进行 n-1 趟排序
        d = i
        for j in range(i + 1, n): # 从剩余数列中寻找最小的
            if arr[j] < arr[d]:
                d = j

        if d != i: # 找到了最小的则交换
            arr[i], arr[d] = arr[d], arr[i]

        i += 1

l = [46, 3, 23, 18, 99, 234, 2, 6]
print(l)
select_sort(l)
print(l)

总共需要进行 n-1 趟排序，第一趟需要比较 n-1 次，第 i 趟需要比较 n-i 次， 最后一趟只需比较 1 次，所以总共需要比较 1 + 2 +3 + ... + n-1 = n(n-1)/2
所以选择排序的时间复杂度是 O(n^2)

当 n 很大时低阶项、系数和常数都可忽略，只取最高阶，所以是 O(n^2)

选择排序是不稳定排序算法

如果数列中两个相等的数排序后相对位置不变就是稳定排序，否则是不稳定排序