一、原理
选择排序 （Selection sort） 是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小 （或最大） 的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小 （大） 元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
选择排序无论在最坏或是最好的情况，时间复杂度都是 O(\(n^2\))
排序逻辑：
|
1 2 3 4 5 |
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++实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
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 实现
|
1 2 3 4 5 6 7 8 9 |
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 语言实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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]); } } |