排序算法之详解选择排序

引入

  • 选择排序顾名思义是需要进行选择的,那么就要问题了,选择到底是选择什么呢?
  • 选择排序的选择是选择数组中未排序的数组最小的值,将被选择的元素放在未排序数组首位

如果你对 ‘未排序数组’ , ‘选择’ 的概念不理解,那么你可以看看下面的图

排序算法之详解选择排序

思路

  • 有了上面的一些基础之后,我们再来说说选择排序算法的思路
    1. 不断的选择未排序数组中最小的值,将其与未排序数组的首位元素进行换位
    2. 选择完一个最小值,未排序的数组长度就要减一,且是从下标为0处开始减
    3. 当未排序数组就剩两个数时,就是最后一次选择,完成此次排序,算法结束,数组排序完成
  • 乍一看,选择排序算法有点像冒泡排序,只不过冒泡排序是选择大的数往后走,选择排序是选择小的数往前走
    1. 其实并不是这样的,数往前后走并没有关系
    2. 冒泡排序是经过不断的相邻换位,来完成排序的
    3. 而选择排序,只需选择(保存)最大或最小的数及这个数的下标,遍历完未排序数组之后,再进行一次换位
    4. 冒泡排序是通过数去找位置,选择排序是给定位置去找数
  • 如果你还不明白,那么就再看看下面这张图,说明:该图转载于菜鸟教程

选择排序.gif

具体实现过程

  • 下面我们就以 [ -8 , 10 , 30 ,6 , 9 , 10 , 100 , 76 ] 为例,讲解选择排序的具体过程

第一次排序

  • 我们先进行选择,将未排序数组的第一个元素作为被选则的元素 【value = -8 ,index = 0】
  • 用一个指针从未排序数组的第一个元素往后逐渐遍历 ,如果有小于当前 value 的 ,就将 value 和 index 的值替换为更小的元素的 值 和 下标
  • 遍历完成,由于没有小于 -8 的元素 ,所以value 和 index 不做改动 【即不交换】
  • 完成第一次排序之后,未排序的数组(逻辑意义上的数组)就变成了 [ 10 , 30 ,6 , 9 , 10 , 100 , 76 ] ,前面已排序的数组 [-8 ]

第二次排序

  • 我们先进行选择,将未排序数组的第一个元素作为被选则的元素 【value = 10 ,index = 1】
  • 用一个指针从未排序数组的第一个元素往后逐渐遍历 ,如果有小于当前 value 的 ,就将 value 和 index 的值替换为更小的元素的 值 和 下标
  • 先找到了 value1 = 6 , index1 = 3 ,改变 value 与 index的值 value= value1 , index = index1
  • 遍历完成,由于index经过了改变 ,所以需要进行换位 , 未排序数组第一个元素 与 index下标元素进行换位
  • 完成第二次排序之后,未排序的数组(逻辑意义上的数组)就变成了 [ 30 ,10 , 9 , 10 , 100 , 76 ] ,前面已排序的数组 [-8 , 6]

......

  • 就这样不断地重复,选择未排序数组中最小的值,将其与未排序数组的首位元素进行换位

最后一次排序

  • 不断地进行排序之后,数组变成了个样子 [ -8 , 6 , 9 ,10 , 10 ,30 , 100 ,76 ]
  • 此时已排序的数组变成了 [ -8 , 6 , 9 ,10 , 10 ,30 ] , 未排序的数组为 [ 100 ,76 ]
  • 我们只需进行最后一次排序,就可以完成整个数组的排序
  • 选择未排序数组的第一个元素 , index = 6 , value = 100
  • 通过指针遍历未排序数组 ,试着寻找 比 value小的数
    • 找到则交换 ,交换后进行下次寻找 ,直至数组遍历完成
  • 最终 ,index = 7 , value = 76
  • 由于此时 index已经改变 ,所以需要进行换位 ,未排序数组第一个元素 与 index下标元素进行换位

代码实现

// 选择排序算法
public static int[] selectSort(int[] array){
    // for循环 ,i表示需要正在选择 第 i 个 最小值 ,从0开始  
    // 一共需要找 array.length-1个最小值
    for (int i = 0; i < array.length-1; i++) {
        // val用于存储被选则的值 ,即最小值 
        // 默认选择未排序数组的第一个元素 ,如果有更小的则更新
        int val = array[i];
        // index用于存储当前最小值对应的数组下标
        // 默认选择未排序数组的第一个元素的下标 ,最小值更新,i也随之更新
        int index = i;     
        // 遍历未选择的数组
        for (int j = i+1; j < array.length; j++) {
            // 试图寻找比被选择的值 更小 的元素 ,如果有 ,则对 val 和 index 进行更新
            if (val > array[j]){
                val = array[j];
                index = j;
            }
        }
        // 如果 i == index ,则代表被选则的值并未改变,即还是未排序数组的第一个元素,所以不用交换
        if (i != index){
            array[index] = array[i];
            array[i] = val;
        }
    }
    return array;
}

原文链接:https://www.cnblogs.com/fzdkx/p/17353867.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:排序算法之详解选择排序 - Python技术站

(0)
上一篇 2023年4月25日
下一篇 2023年4月27日

相关文章

  • Python实现隐马尔可夫模型的前向后向算法的示例代码

    Python实现隐马尔可夫模型的前向后向算法 隐马尔可夫模型(Hidden Markov Model,HMM)是一种常用的统计模型,它可以用于序列数据的建模和预测。在这篇文章中,我们将介绍如何使用Python实现隐马尔可夫模型的前向后向算法,并详细讲解实现原理。 实现原理 隐马尔可夫模型是一种基于状态转移的模型,它包含两个部分:状态序列和观测序列。状态序列是…

    python 2023年5月14日
    00
  • python算法学习之桶排序算法实例(分块排序)

    下面是详细讲解“python算法学习之桶排序算法实例(分块排序)”的完整攻略,包含两个示例说明。 桶排序算法简介 桶算法是一种线性排序算法,它的基本思想是将数据分到有限数量的桶中,然后对每个桶中的数据进行排序,最后将所有桶中的数据依次取出,即可得到有序序列。桶排序算法适用于数据分布均的情况,时间复杂度为O(n)。 Python实现桶排序算法 下面是Pytho…

    python 2023年5月14日
    00
  • python机器学习之决策树分类详解

    下面是详细讲解“Python机器学习之决策树分类详解”的完整攻略。 1. 什么是决策树分类 决策树分类是一种基于树形结构的分类方法,它通过数据集进行划分,构建一棵决策树来进行分类。决策树分类具有可解释性、易于理解和实现等优点,因此在实际应用中得到了广泛的应用。 2. 决策树分类原理 决策树分类的原理是通过对数据集进行划分,构建一棵决策树来进行分类。具体实现过…

    python 2023年5月14日
    00
  • C++数据结构之链表详解

    C++数据结构之链表详解 链表是一种重要的数据结构,它可以动态的分配内存空间,实现灵活的元素插入,删除等操作。本文将详细讲解链表的定义、实现、常见操作以及链表的应用。 定义与特点 链表是一种线性表数据结构,由一系列节点组成,每个节点包含数据和指向下一个节点的指针。链表分为单向链表和双向链表,其中单向链表的每个节点只包含一个指针,指向下一个节点,而双向链表的每…

    数据结构 2023年5月17日
    00
  • C数据结构中串简单实例

    下面我将为您详细讲解C语言中串的简单实例。 1. 什么是串 在C语言中,串(String)是由一系列字符组成的序列,是一种常见的数据类型。在C语言中,串通常是以字符数组(Char Array)的方式进行存储的。 2. 定义和初始化串 在C语言中,定义和初始化串可以通过以下方式进行: #include <stdio.h> #include <…

    数据结构 2023年5月17日
    00
  • Python机器学习之Kmeans基础算法

    以下是关于“Python机器学习之Kmeans基础算法”的完整攻略: 简介 Kmeans是一种常见的聚类算法,它可以将数据集分成多个簇。Python中有多种库可以实现Kmeans算法,例如scikit-learn和numpy。本教程将介绍如何使用Python实现Kmeans基础算法,并提供两个示例。 Kmeans算法 Kmeans算法是一种迭代算法,它将数据…

    python 2023年5月14日
    00
  • python实现机械分词之逆向最大匹配算法代码示例

    以下是关于“Python实现机械分词之逆向最大匹配算法代码示例”的完整攻略: 简介 逆向最大匹配算法是一种常用的机械分词算法,它通过从后往前的方式在文本中查找词语。本教程将介绍如何使用Python实现逆向最大匹配算法,并提供两个示例。 算法实现 逆向最大匹配算法是一种常用的机械分词算法,它通过从后往前的方式在文本中查找词语。具体来说,我们将文本从后往前切割成…

    python 2023年5月14日
    00
  • Java数据结构顺序表的详细讲解

    Java数据结构顺序表的详细讲解 什么是顺序表? 顺序表是一种线性结构,它通过一段连续的存储空间来存储一组元素,每个元素占用一个固定大小的存储单元,元素之间按照一定的顺序紧密排列。 顺序表的实现 在Java中,顺序表可以通过数组实现。数组是一种非常基础的数据结构,它可以用来存储相同类型的数据,数组元素的地址是连续的,因此可以通过下标访问数组中的元素。 实现步…

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部