vlambda博客
学习文章列表

排序算法视频版 | 简单选择排序

在文章【】中,我们介绍了暴力排序和冒泡排序这两种排序算法,算是一个引子。同时指出暴力排序和冒泡排序的缺点硬伤。

本文介绍的简单选择排序则“医治”了上面提到的暴力排序和冒泡排序的“硬伤”。

核心思想:从数组的第一个元素开始,将其作为基准元素,然后找出基准元素之后所有元素中最小的那个,如果这个最小的元素小于基准元素,则交换二者;否则不用交换。

像这样,通过若干次比较和一次交换,最小值一定被排好了,此时说一轮排序完成了,经过若干轮的排序后,排序就完成了。

我们需要三个变量:

  • 变量 i:用于控制轮数;
  • 变量 j:基准元素之后的元素的下标;
  • 变量 min:找到的最小元素的下标。

需要两个嵌套循环:

  • 外层循环用于控制轮数;
  • 内层循环用于控制每轮的若干次比较和最多一次的交换。

动态过程如下:



暴力排序和冒泡排序更像是“没脑子”的交换排序,就是说,在该轮排序结束前,我们并不知道最大值或最小值是谁,所以只能靠遍历,边比较边交换该轮的所有元素,等到该轮排序结束后,自然就排好一个元素了。通常表现为一轮排序中有若干次比较、若干次交换。

而简单选择排序则是“有脑子”的排序,就是说,我们在交换前,先比较该轮的所有元素,(如果)找到最小的那个元素,直接将其交换到它该待的位置。通常表现为一轮排序中有若干次比较、最多一次交换。

代码实现如下:

/*
 * 简单选择排序
 * array : 数组
 * length : 数组长度 
 */

void simple_selection_sort(int *arrayint 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] 获取。

如有错误,还请指正。

推荐阅读

参考资料

[1]

GitHub: https://github.com/xingrenguanxue/Simple-DS-and-Easy-Algo

[2]

Gitee: https://gitee.com/xingrenguanxue/Simple-DS-and-Easy-Algo