【排序算法动画解】简单选择排序

二十二画程序员
• 阅读 1634

本文为系列专题【数据结构和算法:简单方法】的第 13 篇文章。

  1. 数据结构 | 顺序表
  2. 数据结构 | 链表
  3. 数据结构 | 栈
  4. 数据结构 | 队列
  5. 数据结构 | 双链表和循环链表
  6. 数据结构 | 二叉树的概念和原理
  7. 数据结构 | 二叉树的创建及遍历实现
  8. 数据结构 | 线索二叉树
  9. 数据结构 | 二叉堆
  10. 算法 | 顺序查找和二分查找
  11. 数据结构(视频) | 二叉查找树
  12. 排序算法(视频) | 排序基本介绍和冒泡排序

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

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

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

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

我们需要三个变量:

  • 变量 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 | Gitee 获取。

如有错误,还请指正。

微信扫描下方二维码,一起学习更多计算机基础知识。

【排序算法动画解】简单选择排序

点赞
收藏
评论区
推荐文章
【排序算法动画解】排序介绍及冒泡排序
本文为系列专题的第12篇文章。1.2.3.4.5.6.7.8.9.10.11.本文先简单介绍一下什么是排序,然后再结合动画介绍暴力排序和冒泡排序。1.什么是排序?排序在日常生活中无处不在。比如考试成绩的排名、体育课的从低到高的队形、网购时按价格升序排列或降序排列等等。|姓名|学号|班级|成绩|||||
blmius blmius
1年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
【排序算法动画解】直接插入排序
本文为系列专题的第14篇文章。1.2.3.4.5.6.7.8.9.10.11.12.13.前面介绍了已经介绍了三种排序,暴力排序、冒泡排序和简单选择排序,一个共同点都是基于交换。我们可以用另一种视角来看待排序,即将一个待排序的数组看成两个部分:有序区和乱序区。在排序开始前,整个数组都是乱序区,而有序区则为空:排序开始后,有序区
徐小夕 徐小夕
1年前
程序员必备的几种常见排序算法和搜索算法总结
前言最近为了巩固一下自己的算法基础,又把算法书里的基本算法刷了一遍,特地总结一下前端工程师需要了解的排序算法和搜索算法知识,虽然还有很多高深算法需要了解,但是基础还是要好好巩固一下的.本文将以图文的形式为大家介绍如下算法知识,希望在读完之后大家能有所收获:冒泡排序及其优化选择排序插入排序归并排序快速排序顺序搜索二分搜索
Wesley13 Wesley13
1年前
Java日期时间API系列36
  十二时辰,古代劳动人民把一昼夜划分成十二个时段,每一个时段叫一个时辰。二十四小时和十二时辰对照表:时辰时间24时制子时深夜11:00凌晨01:0023:0001:00丑时上午01:00上午03:0001:0003:00寅时上午03:00上午0
Wesley13 Wesley13
1年前
MySQL查询按照指定规则排序
1.按照指定(单个)字段排序selectfromtable_nameorderiddesc;2.按照指定(多个)字段排序selectfromtable_nameorderiddesc,statusdesc;3.按照指定字段和规则排序selec
Stella981 Stella981
1年前
JavaScript常用基础算法
基础算法一、排序1.冒泡排序//冒泡排序functionbubbleSort(arr){for(vari1,lenarr.length;i<len1;i){for(varj0;j<
Wesley13 Wesley13
1年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Stella981 Stella981
1年前
Lua 排序算法
冒泡排序(BubbleSort,台湾译为:泡沫排序或气泡排序)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。算法步骤1.有一个长度为n
helloworld_34035044 helloworld_34035044
5个月前
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
二十二画程序员
二十二画程序员
Lv1
公众号『二十二画程序员』专注于计算机基础知识分享,如数据结构和算法、计算机网络、操作系统、组成原理等,会点Java,会点Go。
16
文章
5
粉丝
14
获赞