专栏首页不止思考算法一看就懂之「 选择排序 」

算法一看就懂之「 选择排序 」

上一篇文章咱们已经聊过「 冒泡排序 」「 插入排序 」了,今天我们来看一看「 选择排序 」。「 选择排序 」虽然在实际应用中没有「 插入排序 」广泛,但它也是我们学习排序算法中必不可少的一种。「 冒泡排序 」和「 插入排序 」都是在两层嵌套循环中慢慢比较元素,不停的调整元素的位置。而「 选择排序 」就比较直接了,属于不出手则已,一出手,相应的元素就必须要到位,元素的位置就不会再变了。

下面我们来详细了解下一下它的逻辑。

一、「 选择排序 」是什么?

选择排序 也是一种很简单的排序算法,它的思路也是将一组待排序的数据,分成2段,一段是“已排序”了的数据,另一段是“未排序”的数据。当然,在最开始的时候,“已排序”区段里是没有数据的。排序开始后,每次都从“未排序”的数据中取出一个最小的元素(注意,这里是取最小的元素,这一点与「 插入排序 」是不同的),然后将这个最小的元素插入到“已排序”数据中末尾元素的后面(这里其实是将这个最小元素与“已排序”数据的末尾紧邻的下一位元素进行交换),这样保持了“已排序”中的数据永远是有序的。一直这么循环的去处理,直到所有的“未排序”的数据都已交换完,则整个排序全部完成。

下面用图示例讲解一下:

(图片来源网络)

从上图可以看到,初始数组是

元素

29

72

98

13

87

66

52

51

36

下标

0

1

2

3

4

5

6

7

8

要对这个数组进行从小到大排序,默认初始状态是全部无序的,因此对这个数组开始遍历找最小元素。

  1. 第一遍大循环时,在整个数组中找到最小元素“13”,将这个最小元素“13”与数组的开头位置元素“29”进行交换。交换后数组为: 元素137298298766525136下标012345678
  2. 第二遍大循环时,元素“13”属于“已排序”区段了,剩下所有元素都属于“未排序”的区段。从剩下元素中找到最小元素“29”,将这个最小元素“29”与元素“72”进行交换(因为元素“72”是已排序数组紧邻的后一位元素),交换后数组为: 元素132998728766525136下标012345678
  3. 第三遍大循环时,“已排序”区段里已经有元素“13”、“29”了,剩下其它元素都属于“未排序”的。从剩下元素中找到最小元素“36”,将这个最小元素“36”与元素“98”进行交换(因为元素“98”是已排序数组紧邻的后一位元素),交换后数组为: 元素132936728766525198下标012345678
  4. 第四遍大循环时,“已排序”区段里已经有元素“13”、“29”、“36”了,剩下其它元素都属于“未排序”的。从剩下元素中找到最小元素“51”,将这个最小元素“51”与元素“72”进行交换(因为元素“72”是已排序数组紧邻的后一位元素),交换后数组为: 元素132936518766527298下标012345678
  5. 第五遍大循环时,“已排序”区段里已经有元素“13”、“29”、“36”、“51”了,剩下其它元素都属于“未排序”的。从剩下元素中找到最小元素“52”,将这个最小元素“52”与元素“87”进行交换(因为元素“87”是已排序数组紧邻的后一位元素),交换后数组为: 元素132936515266877298下标012345678
  6. 第六遍大循环时,“已排序”区段里已经有元素“13”、“29”、“36”、“51”、“52”了,剩下其它元素都属于“未排序”的。从剩下元素中找到最小元素“66”,发现这个最小元素“66”已经是位于已排序数组紧邻的后一位元素了,因此无需交换,数组保持不变: 元素132936515266877298下标012345678
  7. 第七遍大循环时,“已排序”区段里已经有元素“13”、“29”、“36”、“51”、“52”、“66”了,剩下其它元素都属于“未排序”的。从剩下元素中找到最小元素“72”,将这个最小元素“72”与元素“87”进行交换(因为元素“87”是已排序数组紧邻的后一位元素),交换后数组为: 元素132936515266728798下标012345678
  8. 第八遍大循环时,“已排序”区段里已经有元素“13”、“29”、“36”、“51”、“52”、“66”、“72”了,剩下其它元素都属于“未排序”的。从剩下元素中找到最小元素“87”,发现这个最小元素“87”已经是位于已排序数组紧邻的后一位元素了,因此无需交换,数组保持不变: 元素132936515266728798下标012345678
  9. 第九遍大循环时,“已排序”区段里已经有元素“13”、“29”、“36”、“51”、“52”、“66”、“72”、“87”了,剩下未排序的元素只有“98”这一个了,直接保持其位置不变即可,即,此时全部排序完成,数组最终状态为: 元素132936515266728798下标012345678

下面我们来看一个选择排序的代码示意:

算法题:对数组arr进行从小到大的排序,假设数组arr不为空,arr的长度为n思路:采用选择排序方法
public void selectionSort(int[] arr){    int i,j;    int n = arr.length;        //每一次大循环都能找出剩余元素的最小值    for(i=0; i<n; i++){        //min变量是用于存放最小值的下标的,在刚开始的时候,假设位置i是最小值,初始时将i赋值给min        int min = i;        //子循环是用于比较大小,从i的后面一位开始遍历,遍历后面所有元素        for(j=i+1; j<n; j++){            //如果有元素小于min位的值,则将此元素的下标赋值给min            if(arr[j] < arr[min]){                min = j;            }        }        //如果min不等于i,说明刚在在子循环里,找到了最小值,则需要交换元素位置        if(min!=i){            //swap方法是用于交换数组中2个位置的值(传入数组、下标),swap方法省略不写了。            swap(arr,min,i);        }    }}

二、「 选择排序 」的性能怎么样?

我们按照之前文章中讲到的排序算法评估方法来对「 选择排序 」进行一下性能评估:

  • 时间复杂度: 选择排序原理就是在两层嵌套循环里进行对比和交换,所以简单来讲,其一般情况下的时间复杂度就是O(n*n)了。但如果仔细去分析的话,就得看具体的数据情况。但无论数据情况是怎样的,其元素比较的次数是一样的,因此无论是最好情况还是最坏情况,它的元素比较次数没区别。那再看看元素交换次数,如果待排序的数据本身就是有序的,其根本不需要交换元素,交换次数为0,但如果待排序的数据全部都是逆序的,那需要做n-1次元素交换。 因此,其选择排序的最好、最坏、平均情况下,其时间复杂度都是:O(n*n)。
  • 空间复杂度: 选择排序完全就是比较和交换数据,只需要一个辅助空间用来存储待比较的元素的小标,并没有消耗更多的额外空间,因此其空间复杂度是O(1)。
  • 排序稳定性: 选择排序算法不是稳定性排序算法。这里再解释一下稳定性排序是指:2个相等的元素,在排序前的相对前后位置和排序完成后的,相对前后位置保持一致。 选择排序为啥不是稳定性排序呢,举个例子:数组 6、7、6、2、8,在对其进行第一遍循环的时候,会将第一个位置的6与后面的2进行交换。此时,就已经将两个6的相对前后位置改变了。因此选择排序不是稳定性排序算法。
  • 算法复杂性: 选择排序的算法无论是其设计思路上,还是代码的编写上都不复杂,其算法复杂性是较为简单的。

以上,就是对数据结构中「 选择排序 」的一些思考,您有什么疑问吗?

本文分享自微信公众号 - 不止思考(bzsikao),作者:奎哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法一看就懂之「 插入排序 」

    今天咱们来看一看「 插入排序 」。「 插入排序 」与「 冒泡排序 」一样都属于时间复杂O(n*n)的排序算法,并且也都是基于元素之间比较的方式来完成排序的。不过...

    奎哥
  • 算法一看就懂之「 排序算法 」

    之前的文章咱们已经聊过了「 数组和链表 」、「 堆栈 」、「 队列 」和「 递归 」,这些要么是基础的数据结构,要么就是巧妙的编程方法。从今天起咱们来进入真正的...

    奎哥
  • 算法一看就懂之「 冒泡排序 」

    上一篇文章「 排序算法 」已经整体的把排序算法的分类和评估方法介绍了一下,今天起咱们就开始依次介绍一下各种排序算法的原理和特性。咱们就从最容易理解的「 冒泡排序...

    奎哥
  • 动画:什么是鸡尾酒排序和地精排序?

    冒泡排序的每一个元素都可以像小气泡一样,根据自身大小,一点一点向着数组的一侧移动。

    五分钟学算法
  • 每天学习一点儿算法--快速排序

    快速排序是一种常用的优雅的排序算法,它使用分而治之的策略。 那么分而治之(D&C)是一种怎样的策略呢? 分而治之 分而治之(D&C)的要点只有两个: 找出简单...

    爱吃西瓜的番茄酱
  • 常见排序算法的稳定性分析

    我们知道堆的结构是节点i的孩子为 2*i 和 2*i+1 节点,大顶堆要求父节点大于等于其 2 个子节点,小顶堆要求父节点小于等于其 2 个子节点。

    Leophen
  • 算法面试必问:Top K问题浅析

    最近为了扩大团队规模,一直时刻保持脉脉上动态的更新,希望能认识一些新朋友新伙伴。发现脉脉确实挺有意思的哈,有人吐槽职场,有人招聘,有人分享面经,我今天看到有人发...

    写代码的阿宗
  • 普林斯顿大学算法公开课笔记——插入排序

    现有一组数组 arr = [5, 6, 3, 1, 8, 7, 2, 4],共有八个记录,排序过程如下:

    尾尾部落
  • 面试汇总(九):数据结构与算法常见面试总结(二)——堆与栈、数组、排序

      上一篇文章我们介绍了在面试中数据结构中树的常见的面试题。这篇文章我们继续给大家介绍常见的问题。

    stefan666
  • 算法基础:五大排序算法Python实战教程

    排序是每个软件工程师和开发人员都需要掌握的技能。不仅要通过编程面试,还要对程序本身有一个全面的理解。不同的排序算法很好地展示了算法设计上如何强烈的影...

    加米谷大数据

扫码关注云+社区

领取腾讯云代金券