目录
一、Selection Sort的基本思路
通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小(最大)的记录，并和第i(1<=i<=n)个记录交换
嗯，说人话就是例如从第一个开始比较，把第一个和第二个比，如果第二个大则把第二个和第三个比，如果第一个大则把第一个和第三个比。目的就是找到最大(最小)的那一个元素，然后把他放和第一个位置的元素进行交换。
再简单一点就是找最大(最小)的把他往前面放
通过代码的实现我们可以发现，这跟冒泡排序很像。因为冒泡排序是把大(小)的往后面放，而这个选择排序则是把大(小)的往前面放。
二、Selection Sort的各个复杂度
平均时间复杂度：n^2
最坏时间复杂度：n^2
最好时间复杂度：n^2
空间复杂度：1
稳定性：不稳定
(选择排序不是稳定的排序算法。在选择排序过程中，可能会发生相同值元素位置的交换，这可能导致原始顺序中相等元素的相对顺序发生变化。)
三、Selection Sort的实现
#include "algorithm.h"
#define DEBUG
void Swap(int data[], int i, int j) {
int temp=data[i];
data[i] = data[j];
data[j] = temp;
}
void SelectionSort(int data[], size_t size) {
//从小到大
int i, j, min;
for (i = 0; i < size - 1; i++) {
min = i;
for (j = i+1; j < size; j++)
if (data[j] < data[min]) {
min = j;
}
Swap(data, i, min);
#ifdef DEBUG
printf("第%2d次排序:", i+1);
Show_data(data, size);
#endif
}
}
void SelectionTest() {
int data[] = { 12,5,2,9,7,13,7,11,1 };
printf("排序前数组:");
Show_data(data, sizeof(data) / sizeof(int));
SelectionSort(data, sizeof(data) / sizeof(int));
printf("排序后数组:");
Show_data(data, sizeof(data) / sizeof(int));
}
int algorithm015() {
SelectionTest();
return 0;
}
Show_data()函数我在冒泡排序里实现了，就不贴出了。
四、实验结果(输出结果）
这次我把每次挪动位置都打印了出来，相信可以帮助更好的理解它排序的原理
标签：Sort,Selection,int,issue,复杂度,排序,data From： https://blog.csdn.net/weixin_46481335/article/details/143775380