排序算法 —— 直接选择排序
目录
1.直接选择排序思想
2.直接选择排序实现
3.直接选择排序总结
1.直接选择排序思想
思想:每次从剩余的待排序序列中选出最小or最大的元素,放在正确的位置,当把最后一个元素也放在正确的位置的时候,排序完成。
步骤如下:
- 在元素集合array[i] ~ array[n-1]中选择关键码最大(小)的数据元素。
- 若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换。
- 在剩余的array[i] ~ array[n-2](array[i+1] ~ array[n-1])集合中,重复上述步骤,直到集合剩余1个元素。
2.直接选择排序实现
#include <stdio.h>
void swap(int* p1, int *p2)
{
int t = *p1;
*p1 = *p2;
*p2 = t;
}
void SelectSort(int *nums, int n)
{
int i = 0;
for(i = 0; i < n; ++i) // 枚举起始元素
{
int j = 0;
int min_i = i; // 记录最小元素的下标
// 从起始区间开始寻找最小元素的下标
for(j = i; j < n; ++j)
{
min_i = nums[min_i] < nums[j] ? min_i : j;
}
swap(&nums[min_i], &nums[i]);
}
}
int main()
{
int nums[] = {5,4,8,9,6,3,2,1,7,0};
SelectSort(nums,10);
int i = 0;
while(i < sizeof(nums) / sizeof(int))
{
printf("%d ",nums[i]);
i++;
}
return 0;
}
需要注意的是:
- 我们每次寻找的并不是最小的元素,而是最小元素的下标。
代码优化:上面的代码中,在选择元素的时候,我们每次遍历剩余数据,都只能选出一个最小的数据,然后放在正确的位置上;其实我们不仅仅可以在遍历的时候,选出最小的元素,还能够选出最大的元素,把小的元素从左往右放入正确位置,把大的元素从右到左放入正确位置。
优化后的代码如下:
void swap(int* p1, int *p2)
{
int t = *p1;
*p1 = *p2;
*p2 = t;
}
// 时间复杂度:O(N^2)
void SelectSort(int* nums, int n)
{
int left = 0, right = n - 1;
while (left < right)
{
// [left, right]
int min_i = left, max_i = left;
for (int i = left; i <= right; i++)
{
if (nums[i] > nums[max_i])
{
max_i = i;
}
if (nums[i] < nums[min_i])
{
min_i = i;
}
}
swap(&nums[left], &nums[min_i]);
// max如果被换走了,修正一下
if (max_i == left)
{
max_i = min_i;
}
swap(&nums[right], &nums[max_i]);
++left;
--right;
}
}
3.直接选择排序总结
- 直接选择排序思考非常好理解,但是效率不是很好,实际中很少使用。
- 时间复杂度为:O(N^2);
- 空间复杂度为:O(1);
- 稳定性:不稳定,如下图所示。