一、原理
选择排序(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]); } } |
评论