直接选择排序最好最坏情况时间复杂度均为O(n^2)，不稳定，其优势在于最多只需交换n次，交换操作...
直接选择排序最好最坏情况时间复杂度均为O(n^2)，不稳定，其优势在于最多只需交换n次，交换操作比比较操作耗时。
1. 算法思想
从待排序序列中选择最小的元素，放入有序序列的末尾；如此循环直至待排序序列为空。
2. 时间复杂度
最好情况 O(n^2)：序列正序有序，无需交换元素，但比较时间为O(n^2)最坏情况 O(n^2)：序列逆序有序，交换n次，比较O(n^2)
3. 空间复杂度 O(1)
就地排序，辅助空间为常数级
4. 稳定性
不稳定。存在不相邻元素的交换
5. 代码实现（C语言）
void SelectSort(int *A, int n){ int i, j, k; int min, tmp; for (i = 0; i < n - 1; ++i) { k = i; min = A[i]; for (j = i + 1; j < n; ++j) { if (A[j] < min) { k = j; min = A[j]; } } if (k != i) { tmp = A[i]; A[i] = min; A[k] = tmp; } }}版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
