普林斯顿大学算法公开课笔记——选择排序-阿里云开发者社区

开发者社区> xmuwww> 正文

普林斯顿大学算法公开课笔记——选择排序

简介: 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
+关注继续查看

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。——维基百科

复杂度

简单选择排序的特点是交换移动次数很少(至多n-1次),其时间复杂度为 O(n²) (时间主要花在比较上,总的比较次数为N=(n-1)+(n-2)+...+1=n*(n-1)/2),与冒泡排序一样,但性能上优于冒泡。

示例代码

public class Selection
{
    public static void sort(Comparable[] a){
        int N = a.length;
        for (int i=0; i<N; i++){
            int min = i;
            for (int j=i+1; j<N; j++ )
                if(less(a[j], a[min]))
                    min = j;
            exch(a, i, min);
        }
    }
    private static boolean less(Comparable v, Comparable w)
    {
        return v.compareTo(w)<0;
    }
    private static void exch(Comparable[] a, int i, int j)
    {
        Comparable swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
LDD3学习笔记(2):建立和运行模块
1、建立开发环境 在开始编写代码以及研究代码之前,你需要有一个开发环境,也就是一个linux系统。通常我们的做法是在windows下安装一个虚拟机软件,然后在虚拟机软件中安装一个linux系统的发行版本,在众多的发行版本中我推荐ubuntu,不过具体还要看个人爱好。
938 0
python实现选择排序算法
选择排序,简单而直观,其原理是把序列中的最小值或者最大值找出来放在起始位置,然后再从剩下的序列中找出极值放到起始位置之后,以此类推最后就完成排序。 完成这个过程大致思想:首先需要一个记录器,记录排序排到第几个位置了,然后在剩余的序列中找到极值下标,最后将记录器位置和极值位置元素交换,完成本次选择排序。
1192 0
JavaScript ~ 排序算法(选择排序)
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Title</title> <link type="text/css" rel="stylesheet" href="style/flex.
943 0
LDD3学习笔记(3):字符驱动1
1、scull( Simple Character Utility for Loading  Localities)的设计 Scull是一个字符驱动,它操作一块内存区域,就好像它是一个设备,因此在以下的介绍中我们可以互换的使用设备和scull操作的内存区。
707 0
运算符 - PHP手册笔记
原文:运算符 - PHP手册笔记 运算符优先级 每种编程语言都有运算符,运算符要学会灵活使用。 运算符拥有不同的优先级和结合方向。
767 0
可显示Android设备选择列表,并进入指定Android设备Console的Shell脚本
      如果PC上连接多部Android设备(包括Android模拟器),在进入Console时还需要使用adb -s deviceid shell。
1034 0
+关注
132
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载