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

选择排序(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;
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏hbbliyong

nodejs 的序列化与反序列化

1.序列化 stringify函数的作用就是序列化对象,也就是说将对象类型转换成一个字符串类型(默认的分割符("&")和分配符("=")),先介绍它的基本用法,...

3257
来自专栏流媒体

C语言数组

1553
来自专栏逆向技术

C语言第五讲,语句 顺序循环选择.

括号的内容我们给真假就行, 对应到高级语言中 则是 true (真) 和 false(假)

3865
来自专栏日常学python

深入理解python中的类和对象

刚开始学习python的时候或者其他的是面向对象的编程语言的时候,难免会对类和对象理解得不太清楚。所以今天和大家分享下python中的类和对象,深入理解下pyt...

1040
来自专栏用户2442861的专栏

C/C++求职宝典21个重点笔记(常考笔试面试点)

http://blog.csdn.net/lanxuezaipiao/article/details/41557307

971
来自专栏北京马哥教育

Python 运算符,你知道多少?

糖豆贴心提醒,本文阅读时间5分钟,文末有秘密! ? 编辑 | 糖豆 图 | 来源网络 ? 什么是运算符? 本章节主要说明Python的运算符。举个简...

4354
来自专栏数据结构与算法

03:八进制小数

03:八进制小数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 八进制有限小数均可以用十进制有限小数精确地表示。比如,八...

3577
来自专栏十月梦想

JavaScript数组元素排序

使用for循环遍历出数组;然后判断i号元素和i+1号大小,如果判断大于,存储小的元素,如果判断小于存储大的元素

883
来自专栏WebDeveloper

python,详说正则表达式(对常用的关键字符的讲解)

[...]如果匹配的是个范围,可以这个写[0-9a-zA-B]表示0到9并a到z并A到B

1212
来自专栏desperate633

LintCode 两个字符串是变位词题目分析代码

写出一个函数 anagram(s, t) 判断两个字符串是否可以通过改变字母的顺序变成一样的字符串。

912

扫码关注云+社区

领取腾讯云代金券