应用场景

当主键都相同或部分相同的数组。

原理

循环遍历 N 次，每次循环都找到最小值并交换到左面。保持左侧有序。

伪代码

for(i = 0; i < N; i++)
    min = i
    for(j = i + 1; j < N; j++)
        if a[j] < a[min]
            min = j
    交换a[i], a[min]

时间与空间复杂度

时间复杂度：O(N^2)对于长度是N，需要N次交换和N(N-1)/2比较
空间复杂度：O(1)

特性

1. 运行时间和输入无关；
2. 数据移动是最少的，即交换次数和数组的大小成线性关系。
3. 当主键都相同或部分相同，有比较大的优势

代码-Python实现

# 选择排序
def selection(a):
    n = len(a)
    for i in range(n):
        min = i
        j = i
        for j in range(i + 1, n):
            if less(a[j], a[min]):
                min = j

        exch(a, i, j)


def less(a, b):
    if a <= b:
        return True
    else:
        return False


def exch(a, i, j):
    a[i], a[j] = a[j], a[i]