文档章节

选择排序详解

fengsehng
 fengsehng
发布于 2016/11/09 09:11
字数 825
阅读 0
收藏 0
点赞 0
评论 0

概述

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

思想

选择排序法的第一层循环从起始元素开始选到倒数第二个元素,主要是在每次进入的第二层循环之前,将外层循环的下标赋值给临时变量,接下来的第二层循环中,如果发现有比这个最小位置处的元素更小的元素,则将那个更小的元素的下标赋给临时变量,最后,在二层循环退出后,如果临时变量改变,则说明,有比当前外层循环位置更小的元素,需要将这两个元素交换.

代码

public static void selectSort(int[]a)
{
    int minIndex=0;
    int temp=0;
    if((a==null)||(a.length==0))
        return;
    for(int i=0;i<a.length-1;i++)
    {
        minIndex=i;//无序区的最小数据数组下标
        for(intj=i+1;j<a.length;j++)
        {
            //在无序区中找到最小数据并保存其数组下标
            if(a[j]<a[minIndex])
            {
                minIndex=j;
            }
        }
        if(minIndex!=i)
        {
            //如果不是无序区的最小值位置不是默认的第一个数据,则交换之。
            temp=a[i];
            a[i]=a[minIndex];
            a[minIndex]=temp;
        }
    }
}

复杂度

选择排序的交换操作介于 0 和 (n - 1) 次之间。选择排序的比较操作为 n (n - 1) / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1) 次之间。
比较次数O(n^2),比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+…+1=n*(n-1)/2。交换次数O(n),最好情况是,已经有序,交换0次;最坏情况交换n-1次,逆序交换n/2次。交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。

稳定性

选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果一个元素比当前元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。比较拗口,举个例子,序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中两个5的相对前后顺序就被破坏了,所以选择排序是一个不稳定的排序算法。

其他排序算法的情况

这里写图片描述

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧

微信订阅号二维码如下:

这里写图片描述

© 著作权归作者所有

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进...

IceRainYWC
2014/03/17
0
0
JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进...

闫三
2012/05/08
0
0
史上最简单!冒泡、选择排序的Python实现及算法优化详解

1、排序概念 内部排序和外部排序 根据排序过程中,待排序的数据是否全部被放在内存中,分为两大类: 内部排序:指的是待排序的数据存放在计算机内存中进行的排序过程; 外部排序:指的是排序...

马哥教育
2017/10/25
0
0
Python天天美味(32) - python数据结构与算法之堆排序

1. 选择排序 选择排序原理是先选出最小的数,与第一个数交换,然后从第二个数开始再选择最小的数与第二个数交换,…… def selection_sort(data): for i in range(len(data) - 1): min = dat...

zting科技
2017/01/11
0
0
链表各类操作详解

仅供学习使用,附转载连接:http://blog.csdn.net/hackbuteer1/article/details/6591486 链表概述    链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要...

陈国成
2017/06/17
0
0
排序——简单选择排序

一、选择排序概念 选择排序(Selection Sort)的基本思想:对n个记录进行扫描,选择最小的记录,将其输出,接着在剩下的n-1个记录中扫描,选择最小的记录将其输出……不断重复这个过程,直到...

翼动动空
2016/06/06
1K
0
排序算法篇_选择排序法

image   选择排序(Selection Sort)也是比较简单的排序算法,思路也比较直观。选择排序算法在每一步中选取最小值来重新排列,从而达到排序的目的。 选择排序算法 选择排序算法通过选择和交...

一笑小先生
01/30
0
0
直接选择排序(Straight Selection Sort)

1、定义 选择排序(Selection Sort)的基本思想是:每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕。 常用的选择排序方法有直接选择排序...

野渡书生
2016/05/03
6
0
一个Java小白通向数据结构算法之旅(5) - 选择排序

前言 今天去东鹏特饮面试,我很生气。面的技术岗,卷子竟然是营销的。浪费了我一晚上的时间,害得我差点没赶上地铁的末班车。你能敢相信?这是面的试卷。生气归生气,学习还是要继续的。 im...

cmazxiaoma
2017/11/07
0
0
【算法】——选择排序

前言: 近期很多时间用来学习算法上了,之前每一次学习算法都是纸上谈兵,打嘴炮,看看,说说,以为思路搞清楚了就万事大吉了,不去理会大家说的一定要去自己做,动手就想着我动手了啊,我明...

R_s_x
2017/09/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

1.14 救援模式

确保开机启动时连接镜像文件,如果是真机服务器,就需要:U盘或光盘镜像启动进入BIOS 不同主板进入bios按键不同,一般是F12或Esc 光标:移动到Boot(开机启动项) 减号移动:光标选中行,按-...

小丑鱼00
15分钟前
0
0
ES11-全文检索

高级别全文检索通常用于在全文本字段(如电子邮件正文)上运行全文检索。 他们了解如何分析被查询的字段,并在执行之前将每个字段的分析器(或search_analyzer)应用于查询字符串。 1.term查...

贾峰uk
18分钟前
0
0
java 复制对象有哪些方式

java 复制对象有哪些方式 Apache的 Common beanutils库 org.apache.commons.beanutils.BeanUtils.copyProperties(dest,origin); Springframework 的BeanUtil 依赖: <dependency> ......

黄威
33分钟前
1
0
jstack的简单使用

公司测试反应, 一个java应用的机器, 即使不做交易, cpu始终是30%多, 于是想到了jstack, 实践步骤记录一下: 1, 找出java应用的进程号 ps -ef|grep 应用名|grep -v grep 2, 找出pid下的cpu占用...

零二一七
40分钟前
1
0
崛起于Springboot2.X之项目war打包部署(18)

将springboot项目打包步骤: 1、启动类 extends SpringBootServletInitializer 2、启动类添加覆盖方法 @Overrideprotected SpringApplicationBuilder configure(SpringApplicationBuilder......

木九天
49分钟前
2
0
导入CSV文件就行数据整理分析

#-*-coding:utf-8-*-import csv,os,re,mathlocalPath=input("请输入所有群文件的根目录:") #所有QQ群文件的物理根目录路径def info(): info_dic=[] dirList=os.listdi...

Kefy
55分钟前
5
0
CoreText进阶(六)-内容大小计算和自动布局

CoreText进阶(六)-内容大小计算和自动布局 其它文章: CoreText 入门(一)-文本绘制 CoreText入门(二)-绘制图片 CoreText进阶(三)-事件处理 CoreText进阶(四)-文字行数限制和显示更...

aron1992
57分钟前
1
0
一个Unity高人的博客,涉猎范围很广,深度也很深。

https://blog.csdn.net/ecidevilin/article/list/

爽歪歪ES
59分钟前
0
0
Spring Cloud Config-Git后端

EnvironmentRepository的默认实现使用Git后端,这对于管理升级和物理环境以及审核更改非常方便。要更改存储库的位置,可以在Config Server中设置“spring.cloud.config.server.git.uri”配置...

itcloud
今天
1
0
centos7 卸载mysql

[root@zyf ~]# rpm -qa|grep -i mysqlmysql-community-libs-5.6.34-2.el7.x86_64mysql-community-server-5.6.34-2.el7.x86_64mysql-community-release-el7-5.noarchmysql-community-......

Yao--靠自己
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部