排序算法视频版 | 简单选择排序
在文章【】中,我们介绍了暴力排序和冒泡排序这两种排序算法,算是一个引子。同时指出暴力排序和冒泡排序的缺点硬伤。
本文介绍的简单选择排序则“医治”了上面提到的暴力排序和冒泡排序的“硬伤”。
核心思想:从数组的第一个元素开始,将其作为基准元素,然后找出基准元素之后所有元素中最小的那个,如果这个最小的元素小于基准元素,则交换二者;否则不用交换。
像这样,通过若干次比较和一次交换,最小值一定被排好了,此时说一轮排序完成了,经过若干轮的排序后,排序就完成了。
我们需要三个变量:
-
变量 i
:用于控制轮数; -
变量 j
:基准元素之后的元素的下标; -
变量 min
:找到的最小元素的下标。
需要两个嵌套循环:
-
外层循环用于控制轮数; -
内层循环用于控制每轮的若干次比较和最多一次的交换。
动态过程如下:
暴力排序和冒泡排序更像是“没脑子”的交换排序,就是说,在该轮排序结束前,我们并不知道最大值或最小值是谁,所以只能靠遍历,边比较边交换该轮的所有元素,等到该轮排序结束后,自然就排好一个元素了。通常表现为一轮排序中有若干次比较、若干次交换。
而简单选择排序则是“有脑子”的排序,就是说,我们在交换前,先比较该轮的所有元素,(如果)找到最小的那个元素,直接将其交换到它该待的位置。通常表现为一轮排序中有若干次比较、最多一次交换。
代码实现如下:
/*
* 简单选择排序
* array : 数组
* length : 数组长度
*/
void simple_selection_sort(int *array, int length)
{
int i, j, min;
for (int i = 0; i < length - 1; i++) {
min = i; // 最小元素初始化为基准元素
// 找最小元素
for (int j = i + 1; j < length; j++) {
if (array[min] > array[j]) {
min = j;
}
}
// 在基准元素之后的元素中找到了比基准元素小的值
if (i != min) {
swap(array, i, min); // 交换
}
}
}
完整代码请移步至 GitHub[1] | Gitee[2] 获取。
如有错误,还请指正。
推荐阅读
参考资料
GitHub: https://github.com/xingrenguanxue/Simple-DS-and-Easy-Algo
[2]Gitee: https://gitee.com/xingrenguanxue/Simple-DS-and-Easy-Algo