目录
1.基本思想
2.代码实现
代码思路
代码实现
代码测试
3.复杂度分析
1)时间复杂度
2)空间复杂度
4.特性总结
1.基本思想
选择排序是一种简单直观的比较排序算法。该算法的基本思想是在每一轮中选出当前未排序部分的最小(或最大)元素,然后将其放置到未排序序列的起始位置,这个过程一直重复直至整个数组被排序。
2.代码实现
代码思路
★ 从数组的当前未排序部分选择最小(或最大)的一个元素。
★ 将这个最小(或最大)元素与未排序序列的第一个元素交换位置。
★ 然后从剩余未排序的元素中继续这个过程,将每一次找到的最小(或最大)元素放到未排序序列的开始。
★ 这个过程一直进行到整个数组的所有元素都被排为有序状态。
代码实现
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
//找最大和最小下标进行交换
int min = begin;
int max = begin;
for (int i = begin; i <= end; i++)
{
if (a[i] < a[min])
{
min = i;
}
if (a[i] > a[max])
{
max = i;
}
}
//如果最大最初的在首位,那么交换后,就改变了max的位置,无法使end位置为最大
Swap(&a[begin], &a[min]);
if (max == begin)
{
max = min;
}
Swap(&a[end], &a[max]);
begin++;
end--;
}
}
代码测试
3.复杂度分析
1)时间复杂度
无论数组的初始顺序如何,选择排序都需要比较所有未排序的元素来找到最小(或最大)的元素,并执行这个过程 n-1 次(对于 n 个元素的数组)。每次选择操作需要比较的次数从 n-1 次减少到 1 次,总共的比较次数是 (n-1) + (n-2) + … + 1 = n(n-1)/2,这是一个二次函数,因此时间复杂度为 O(n^2)。
2)空间复杂度
原地排序算法0(1)
4.特性总结
1. 选择排序思考非常好理解,但是效率不是很好。实际中很少使用。
2. 时间复杂度:O(N^2)
3. 空间复杂度:O(1)
4. 稳定性:不稳定5. 复杂性:简单
如有错误,劳烦各位指正