选择排序

选择排序

选择排序(Select Sort)是以中简单直观的排序算法。它的基本思想是:
对于一个给定的未排序序列,经过第一轮比较后得到最小的元素,然后将该元素和序列中的第一个元素进行交换;
然后在从剩余的序列中选择的最小的元素和第二个元素交换位置;
重复该过程,直到需要比较的元素只有一个为止。

选择排序说明

下面以数列{20,40,30,10,60,50}为例,演示它的选择排序过程(如下图)。
image
排序流程

第1趟:i=0。找出a[1...5]中的最小值a[3]=10,然后将a[0]和a[3]互换。 数列变化:20,40,30,10,60,50 -- > 10,40,30,20,60,50
第2趟:i=1。找出a[2...5]中的最小值a[3]=20,然后将a[1]和a[3]互换。 数列变化:10,40,30,20,60,50 -- > 10,20,30,40,60,50
第3趟:i=2。找出a[3...5]中的最小值,由于该最小值大于a[2],该趟不做任何处理。
第4趟:i=3。找出a[4...5]中的最小值,由于该最小值大于a[3],该趟不做任何处理。
第5趟:i=4。交换a[4]和a[5]的数据。 数列变化:10,20,30,40,60,50 -- > 10,20,30,40,50,60

代码实现

/**
 * SelectSort
 */
public class SelectSort {

    public static void selectSort(int[] array) {
        int len = array.length;
        if (len <= 0) {
            return;
        }
        for (int i = 0; i < len; i++) {
            int min = Integer.MAX_VALUE;
            int pos = 0;
            for (int j = i; j < len; j++) {
                if (array[j] < min) {
                    min = array[j];
                    pos = j;
                }
            }
            swap(array, i, pos);
        }
    }

    public static void swap(int[] array, int pos1, int pos2) {
        int tmp = array[pos1];
        array[pos1] = array[pos2];
        array[pos2] = tmp;
    }
    public static void main(String[] args) {
        int[] a = {20,40,30,10,60,50};
        selectSort(a);
        System.out.printf("after  sort:");
        for (int i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
     }
}

选择排序的时间复杂度和稳定性

选择排序的时间复杂度是O(N^2)。
假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N),需要遍历多少次呢?N-1!因此,选择排序的时间复杂度是O(N^2)。
选择排序稳定性
选择排序是稳定的算法,它满足稳定算法的定义。

版权声明:本文为weixin_30505225原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30505225/article/details/96524053

智能推荐

使用Xdebug进行远程调试

为什么要用? 方便联调: 和客户端一起联调,是die(); exit(); 会影响其他人员是使用。 关注数据变化: 正常情况下,我们在调试和开发时,更关注数据的变化。频繁断点、效率比较低。 简单: 之前的开发自己比较懒,一直没用,用起来发现很简单。 原理 运行xdebug需要客户端IDE(phpstorm)、远程服务器配合,首先是客户端配置好端口,发送debug请求,请求会通过浏览器或者IDE的h...

【教程向】通过windows在树莓派3B上安装Ubuntu MATE 16.04.2 (Xenial)

本文参考了http://www.ituring.com.cn/article/273613 ================================================================= 1:因为树莓派3B的性能问题,所以使用这个特别为树莓派设计的版本。 2:准备: 树莓派3B * 1 16GB TF/Micro SD卡 *1(尽量用速度快一些的卡,因为以后这相...

LeetCode(7 整数反转)

如题 这就不用分析了,直接依次取每位即可,难点就是个越界判断...

Caused by: java.rmi.ConnectIOException: error during JRMP connection establishment; nested exception

启动RMI报如下错误: 最后发现是端口冲突造成的,当时用的5003端口启动服务端的RMI刚好和本地的一个服务端口冲突。 输入netstat -aon|findstr "5003"查询它的pid为3056 继续输入tasklist|findstr "3056",查看是哪个进程或者程序占用了5003端口,结果是:magentproc.exe 找到PID后可以直接...

猜你喜欢

【LeetCode(Java) - 322】零钱兑换

文章目录 1、题目描述 2、解题思路 3、解题代码 1、题目描述 2、解题思路   定义 dp[i] 表示对于组成金额 i 的最少硬币个数。   如果方案存在,那么至少有一个硬币至少出现了一次:   如果是第 0 个硬币出现了一次,则:dp[i] = dp[i-coins[0]] + 1   如果是第 1 个硬币出现了...

在Visual Studio 2013中配置Entity Framework使用MySQL

环境 使用的软件及版本 - Microsoft Visual Studio Ultimate 2013 (版本 12.0.40629.00 Update 5) - Microsoft.Net Framework 版本 4.6.01055 - MySQL版本: 5.6.17 步骤 1. 创建空的MVC项目 2. 安装扩展 3. 在数据库中建立对应的表 必须在数据库内先新建表,否则asp.net mv...

Python才是世界上最好的言语,php,java靠边站

伟大的入门编程语言有什么特征呢?或者换一种方式问,“当我们教他们编程时,应该给予他们什么?”对于成年人和青少年学生,我认为以下五点非常重要。 学生从入门语言获得的五样东西 非常棒的首次体验,就像一本书的第一页,首先需要“入迷”,学习新知识不可避免的会遇到挫折,但要有持续的热情和好奇心,这对于那些从未接触过编码的年轻人来说是至关重要的; Web编程的能...

动态调整docker容器cpu资源

目的:动态调整系统cpu核数后,如何在不停止容器服务的情况下,docker动态使用最新的CPU资源 事件由来:     1、在ucloud上购买了一台可以热升级的机器,热升级指的是动态更改系统cpu和内存资源     2、随着业务的扩展,发现cpu、内存负载过高,需要在不停止业务的情况下动态扩容,因此使用了ucloud提供的热升级服务,从4核12G扩容为8核...

用python itchat包 爬取微信好友头像形成矩形头像集

原创作品,转载请注明作者 abysscarry-袁杰丶 初学python,我们必须干点有意思的事!从微信下手吧! 头像集样例如下: 大家可以发朋友圈开启辨认大赛哈哈~ 话不多说,直接上代码,注释我写了比较多,大家应该能看懂 运行结果: ok!!!...