[数据结构]排序之 直接选择排序
1
基本思想:
每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的
数据元素排完 。
2
直接选择排序
:
在元素集合
array[i]--array[n-1]
中选择关键码最大
(
小
)
的数据元素
若它不是这组元素中的最后一个
(
第一个
)
元素,则将它与这组元素中的最后一个(第一个)元素交换
在剩余的
array[i]--array[n-2]
(
array[i+1]--array[n-1]
)集合中,重复上述步骤,直到集合剩余
1
个元素
// 选择排序
void SelectSort(int* a, int n)
{
int left = 0;
int right = n - 1;
while (left < right)
{
int mini = left, maxi = left;//记录下标
for (int i = left+1; i <= right; i++)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[left], &a[mini]);
// 检查最大值位置是否被改变
if (maxi == left) {
maxi = mini;
}
Swap(&a[right], &a[maxi]);
++left;
--right;
}
}
为什么要在两个Swap之间写一个if?
考虑这样一种情况:当
left
位置的元素就是当前未排序部分的最大值时,在第一次交换
a[left]
和
a[mini]
之后,原本
maxi
指向的最大值元素已经被交换到了
mini
位置,而时
maxi
仍然指向原来的
left
位置,所以在进行第二次交换
a[right]
和
a[maxi]
时,实际上交换的并不是最大值,从而导致排序结果出错。

直接选择排序的特性总结:
1.
直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
2.
时间复杂度:
O(N^2) 最坏情况和最好情况都是
O(N^2),之前的序列对排序没有影响,所以直接选择排序很烂,基本不会用
3.
空间复杂度:
O(1)
4.
稳定性:不稳定
原文地址:https://blog.csdn.net/m0_74978334/article/details/146273824
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/586542.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/586542.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!