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

22
• 阅读 1892

本文为系列专题【数据结构和算法:简单方法】的第 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 获取。

如有错误,还请指正。

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

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

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
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
22 22
2年前
【排序算法动画解】排序介绍及冒泡排序
本文为系列专题的第12篇文章。1.2.3.4.5.6.7.8.9.10.11.本文先简单介绍一下什么是排序,然后再结合动画介绍暴力排序和冒泡排序。1.什么是排序?排序在日常生活中无处不在。比如考试成绩的排名、体育课的从低到高的队形、网购时按价格升序排列或降序排列等等。|姓名|学号|班级|成绩|||||
22 22
2年前
【排序算法动画解】直接插入排序
本文为系列专题的第14篇文章。1.2.3.4.5.6.7.8.9.10.11.12.13.前面介绍了已经介绍了三种排序,暴力排序、冒泡排序和简单选择排序,一个共同点都是基于交换。我们可以用另一种视角来看待排序,即将一个待排序的数组看成两个部分:有序区和乱序区。在排序开始前,整个数组都是乱序区,而有序区则为空:排序开始后,有序区
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Wesley13 Wesley13
2年前
java中几种排序的实现
1.最简单的冒泡排序/\\\冒泡排序\/publicstaticvoidbubbleSort(){int\\arr{5,8,1,2,9,8,7,4};System.out.println("排序前的数组为:");for(intnum:arr){System.o
Stella981 Stella981
2年前
JS 对象数组Array 根据对象object key的值排序sort,很风骚哦
有个js对象数组varary\{id:1,name:"b"},{id:2,name:"b"}\需求是根据name或者id的值来排序,这里有个风骚的函数函数定义:function keysrt(key,desc) {  return function(a,b){    return desc ? ~~(ak
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Wesley13 Wesley13
2年前
Java面试总结(排序算法)
1.冒泡排序算法描述:两两比较,大的放后面2.选择排序算法描述:在m元数组中找到最小值的位置,然后将最小值的位置和第n(n0,1,2,....m1)位的值对调,排序k次则m元数组中前k(k<m)位的值已经排序好,m元数组中前k位的值不需要再进行排序,此时需要排序的元素只有mk个3.插入排序算
Stella981 Stella981
2年前
JavaScript常用基础算法
基础算法一、排序1.冒泡排序//冒泡排序functionbubbleSort(arr){for(vari1,lenarr.length;i<len1;i){for(varj0;j<
菜园前端 菜园前端
8个月前
什么是冒泡排序
原文链接:什么是冒泡排序(bubbleSort)?冒泡排序是所有排序算法中最简单的一种,当然也是性能最差的一种。冒泡排序的思想其实很简单,就如它的名字一样在水中"冒泡"。水中有很多散乱的小气泡,然后一个个气泡往水面上冒出。例如一组无序的数组,最左边就是水底