一、原理

选择排序（Selection sort）是一种简单直观的排序算法，它的工作原理是：从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

选择排序无论在最坏或是最好的情况，时间复杂度都是O($n^2$)

排序逻辑：

for i in (i, n-1)
    min = data[i]
    for j in (j, n)
        如果min>data[j]，标记当前位置，重新设置min，继续循环
    把最小的元素min和data[i]替换

图解

以序列[3, 1, 5, 4, 7]为例，执行第一趟排序时，找到的最小元素是1，把它放到最前面和3对换：

第二趟排序，未排序数组为[3, 5, 4, 7]，此时数组内最小的元素是3，刚好就是当前数组最开头的位置，因此无需替换，继续下一趟排序。

第三趟排序，未排序数组为[5, 4, 7]，此时数组内最小的元素是4，放到最前面和5对换：

执行完第三趟排序后，数组就已经有序了。但是对计算机而言却并不知情，它还会继续判断后面的[5, 7]，但是刚好每次排序的时候，他们就处于应该在的位置。

二、代码实现

2.1 C++实现

template <typename T>
void select_sort(vector<T> &v) {
    size_t i, j;
    // 记录最小的下标
    T min_idx;

    if (v.size() < 2)
        return;

    // 只用执行n-1趟排序
    for (i = 0; i < v.size() - 1; i++) {
        min_idx = i;

        // 找到最小的下标
        for (j = i + 1; j < v.size(); j++) {
            if (v[j] < v[min_idx])
                min_idx = j;
        }

        // 替换最小的
        if (min_idx != i) {
            my_swap(v[i], v[min_idx]);
        }
    }
}

2.2 python实现

def select_sort(data):
    size = len(data)
    for i in range(size - 1):
        k = i
        for j in range(i + 1, size):
            if data[j] < data[k]:
                k = j
        if k != i:
            data[k], data[i] = data[i], data[k]

2.3 c语言实现

int select_sort(int* data, unsigned int len) {
    unsigned int i, j, min;

    for (i = 0; i < len - 2; i++) {
        min = i;
        for (j = i + 1; j < len - 2; j++) {
            if (data[j] < data[i])
                min = j;
        }
        if (min != i)
            swap(data[min], data[i]);
    }
}