排序----选择排序

public class Selection {
    public static void sort(Comparable[] a){
        int N = a.length;
        for(int i=0;i<N;i++){   //第一层循环找出第I小的数并放到正确位置
            int min = i;
            for(int j=i+1;j<N;j++)    //为实现第一层循环的目标,第二层循环寻找剩下元素中最小值并交换到正确位置
                if (less(a[j],a[min]))	min = j;
            exch(a,i,min);  
        }
    }
    //less()、exch()、isSorted()、main()方法见“排序算法模板”
}

长度为N的数组,选择排序需要大约N^2/2次比较和N次交换。算法的时间复杂度为O(N^2).

他有两个很鲜明的特点:

  • 运行时间和输入无关。前一遍扫描数组不能为下一次扫描提供任何信息。
  • 数据移动是最少的。只会移动N次元素。

下一篇:插入排序

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏九彩拼盘的叨叨叨

学习纲要:JavaScript 基础语法

12330
来自专栏Python小屋

Python从序列中选择k个不重复元素

集合中的元素不允许重复,Python集合的内部实现为此做了大量相应的优化,判断集合中是否包含某元素时比列表速度快很多。下面的代码用于返回指定范围内一定数量的不重...

36060
来自专栏python成长之路

集合常用操作

17740
来自专栏ACM算法日常

leetcode题解 | 78. 子集

这个题目很容易想到使用DFS的方式来解决,因为组合的题容易产生转移方程,这样也是没有什么问题的。

17530
来自专栏Python私房菜

翻译 | 更快的Python(一)

更快的Python使用代码示例来说明如何书写Python代码能带来更高的性能。本文对代码进行了讲解,从性能和可读性等角度来选择出最适合的写法。

8920
来自专栏生信小驿站

R语言字符串处理①R语言字符串合并与拆分

30820
来自专栏章鱼的慢慢技术路

LeetCode_832. Flipping an Image_Solution

题目所描述的意思是对每个数组先进行取反,并且对数组中的每个元素进行取反转换,所以一共要执行两个操作。

9120
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》 附录A NumPy高级应用A.1 ndarray对象的内部机理A.2 高级数组操作A.3 广播A.4 ufunc高级应用A.5 结构化和记录式数组A.6 更多

在这篇附录中,我会深入NumPy库的数组计算。这会包括ndarray更内部的细节,和更高级的数组操作和算法。 这章包括了一些杂乱的章节,不需要仔细研究。 A.1...

73760
来自专栏蜉蝣禅修之道

基于Huffman编码的压缩软件的Python实现

24640
来自专栏小L的魔法馆

C++创建学生类练习

37360

扫码关注云+社区

领取腾讯云代金券