👦个人主页：Weraphael
✍🏻作者简介：目前正在学习c++和算法
✈️专栏：数据结构
🐋 希望大家多多支持，咱一起进步！😁
如果文章有啥瑕疵
希望大佬指点一二
如果文章对你有帮助的话
欢迎 评论💬 点赞👍🏻 收藏 📂 加关注😍
目录
- 一、基本思想
- 二、传统算法思路
- 三、传统代码实现
- 四、优化版本思路
- 五、优化版本代码实现
- 六、特性总结
一、基本思想
基本思想：每一次从原数组的元素中选出一个最大/最小的元素，放在序列的起始位置（选最大还是最小看排的是升序还是降序），直至全部待排序的数据全部排完。
二、传统算法思路
以排列升序为例
- 在元素集合
array[0]--array[n-1]中选择随机选择一个数据元素。假设array[0]是最小的（注意是假设） - 然后再从元素集合
array[1]--array[n-1]遍历，如果集合中还有元素比array[0]小，则更新。 - 重复上述步骤，直到集合剩余
1个元素
三、传统代码实现
#include <stdio.h>
void Swap(int *x, int *y)
{
int t = *x;
*x = *y;
*y = t;
}
void select_sort(int a[], int n)
{
// 1. 规划区间
int l = 0, r = n - 1;
// 5. 直到集合剩余一个元素为止
while (l < r)
{
// 2. 假设最小值是a[0],下标是l = 0
int Min = l;
// 3. 遍历区间[l + 1, r]，
for (int i = l + 1; i <= r; i++)
{
if (a[i] < a[Min])
{
// 更新最小值下标
Min = i;
}
}
// 4. 当循环结束后，直接让下标为l和下标为Min直接交换
Swap(&a[l], &a[Min]);
l++;
}
}
int main()
{
int a[] = {10, 1, 6, 9, 4, 7, 2, 3, 8, 5};
int aSize = sizeof(a) / sizeof(a[0]);
select_sort(a, aSize);
for (int i = 0; i < aSize; i++)
{
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
【结果展示】
四、优化版本思路
- 定义
left和right分别表示数组的头和尾 - 每次遍历
left~right区间里的元素，找到最小的数与left为下标的元素进行交换；同理，找到最大的元素与以right为下标的元素进行交换，完成交换后分别缩小left和right之间的范围 - 重复上述步骤，直到集合剩余一个元素为止
注意：这里会有一个大家忽略的问题：重叠问题
如上图所示，a[l] 和a[MinIdx]交换后，此时maxIdx指向的元素就是最小值了，再对a[r]和a[MaxIdx]就会出错，因此，再次交换之前需要将MaxIdx指向MinIdx
五、优化版本代码实现
#include <stdio.h>
void Swap(int *x, int *y)
{
int t = *x;
*x = *y;
*y = t;
}
void select_sort(int a[], int n)
{
// 1. 规定区间
int l = 0, r = n - 1;
// 直到集合剩余一个元素为止
while (l < r)
{
// 2. 假设最大值和最小值都是下标为0的元素
int MinIdx = l, MaxIdx = l;
// 3. 遍历[l + 1, r]
for (int i = l + 1; i <= r; i++)
{
// 分别更新最大值和最小值的下标
if (a[i] > a[MaxIdx])
{
MaxIdx = i;
}
if (a[i] < a[MinIdx])
{
MinIdx = i;
}
}
// 当for循环结束后，说明已经找到区间内的最大值和最小值
// 直接分别和下标为l、r交换即可
Swap(&a[l], &a[MinIdx]);
// 可能存在left和Max重叠
if (l == MaxIdx)
{
MaxIdx = MinIdx;
}
Swap(&a[r], &a[MaxIdx]);
// 更新区间
l++;
r--;
}
}
int main()
{
int a[] = {10, 1, 6, 9, 4, 7, 2, 3, 8, 5};
int aSize = sizeof(a) / sizeof(a[0]);
select_sort(a, aSize);
for (int i = 0; i < aSize; i++)
{
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
【结果展示】
六、特性总结
- 时间复杂度
首先先来分析传统版本，每次排好一个数是n - 1次，第二个数是n - 2次…，是一个等差数列。因此时间复杂度是O(N2)
同理的，优化版本排好一个数是n - 2次，第二个就是n - 4次…，同样也是一个等差数列。因此时间复杂度还是O(N2)
总之，直接选择排序效率极低，实际中很少使用。
- 空间复杂度：O(1)
- 稳定性：不稳定
那么如果对一个有序序列进行选择排序（使用优化版），它的效率又会是如何呢？我们可以来测试一下
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void Swap(int* x, int* y)
{
int t = *x;
*x = *y;
*y = t;
}
// 优化版
void select_sort(int a[], int n)
{
// 1. 规定区间
int l = 0, r = n - 1;
// 直到集合剩余一个元素为止
while (l < r)
{
// 2. 假设最大值和最小值都是下标为0的元素
int MinIdx = l, MaxIdx = l;
// 3. 遍历[l + 1, r]
for (int i = l + 1; i <= r; i++)
{
// 分别更新最大值和最小值的下标
if (a[i] > a[MaxIdx])
{
MaxIdx = i;
}
if (a[i] < a[MinIdx])
{
MinIdx = i;
}
}
// 当for循环结束后，说明已经找到区间内的最大值和最小值
// 直接分别和下标为l、r交换即可
Swap(&a[l], &a[MinIdx]);
// 可能存在left和Max重叠
if (l == MaxIdx)
{
MaxIdx = MinIdx;
}
Swap(&a[r], &a[MaxIdx]);
// 更新区间
l++;
r--;
}
}
int main()
{
srand(time(0));
const int N = 100000; // 十万测试数据
int* a1 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; i++)
{
a1[i] = rand();
}
// 先排好序
select_sort(a1, N);
int begin = clock();
select_sort(a1, N);
int end = clock();
printf("快速选择排序：%d\n", end - begin);
return 0;
}
【运行结果】
需要差不多9秒
因此，直接选择排序是一个鸡肋的排序算法
