概念
选择排序(selection sort):一种简单直观的排序算法。
原理
每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
处理流程
- 从待排序序列中,找到关键字最小的元素;
- 如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换;
- 从余下的 N - 1 个元素中,找出关键字最小的元素,重复(1)、(2)步,直到排序结束。
算法描述(C语言)
void selection_sort(int *a, int len) {
int temp, min_index;
for (int i = 0; i < len; i++) {
min_index = i;
for (int j = i + 1; j < len; j++) {
if (a[j] < a[min_index]) {
min_index = j;
}
}
if (i != min_index) {
temp = a[i];
a[i] = a[min_index];
a[min_index] = temp;
}
}
}
int main() {
int a[] = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
int len = sizeof(a)/sizeof(int);
selection_sort(a, len);
for (int i = 0; i < len; i++) {
printf("%d\n", a[i]);
}
return 0;
}
算法稳定性
选择排序两个相同的元素排序结束后位置可能发生变化,所以选择排序是不稳定的排序算法。
算法分析
时间复杂度:O(n²)