排序算法-选择排序

算法简介

选择排序就是找到数组中最小元素将其和数组第一个元素交换位置,然后在剩下的元素中找到最小元素并将其与数组第二个元素进行交换,以此类推,直至整个数组排序结束。

算法描述

  • 找到数组中最小元素并将其和数组第一个元素交换位置
  • 在剩下的元素中找到最小元素并将其与数组第二个元素交换,直至整个数组排序

代码实现

    /**
     * 选择
     *
     * @param array
     */
    private static void selectionSort(int[] array) {
        if (array == null || array.length == 0 || array.length == 1)
            return;
        int min;
        for (int i = 0; i < array.length - 1; i++) {
            min = i;
            for (int j = array.length - 1; j > i; j--) {
                if (array[j] < array[min])
                    min = j;//将最小数的索引保存
            }
            //最小元素与第i位置元素互换
            if (array[i] > array[min]) {
                int temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
        }
    }

性能分析

最好情况:交换 0 次,但是每次都要找到最小的元素,因此时间复杂度为$ O(n^2) $。

最坏情况:交换 \(n-1\)次,但是每次都要找到最小的元素,因此时间复杂度为$ O(n^2) $。

平均情况下时间复杂度为$ O(n^2) $。

因为需要一个临时变量来交换元素位置和一个变量记录最小位置,(另外遍历序列时自然少不了用一个变量来做索引),所以其空间复杂度为\(O(1)\)。

由于每次都是选取未排序序列R中的最小元素 a 与 R 中的第一个元素交换,很可能破坏了元素间的相对位置,因此选择排序是不稳定的。

排序算法

平均时间复杂度

最好情况

最坏情况

空间复杂度

稳定性

选择排序

\(O(n^2)\)

\(O(n^2)\)

\(O(n^2)\)

\(O(1)\)

不稳定

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习思考者

Python学习(二) 正则表达式

Python正则表达式 正则表达式是一个特殊的字符序列,它能帮助你方便的检查一个字符串是否与某种模式匹配。re 模块使 Python 语言拥有全部的正则表达式功...

20890
来自专栏猿人谷

qsort(),sort()排序函数

一.qsort()函数 功 能: 使用快速排序例程进行排序 头文件:stdlib.h 用 法: void qsort(void *base,int nelem,...

26080
来自专栏python学习指南

python列表

本篇将介绍python中的列表,更多内容请参考:Python学习指南 一、序列 在python中有六种内建的序列:列表、元祖、字符串、Unicode字符串...

37650
来自专栏测试开发架构之路

C++之类和对象的使用(三)

对象数组 如果构造函数只有一个参数,在定义数组时可以直接在等号后面的花括号内提供。Student stud[3]={90,92,01};//合法 如果构造函数...

34390
来自专栏小樱的经验随笔

关于int *a[常量]与int (*a)[常量]的分析与区分(详解)

前言: 小伙伴私信我说,int *a[常量]与int (*a)[常量]这个区分不开,C指针,确实是C中最难的部分,也是学C++,JAVA,包括你以后上岗用的非常...

27530
来自专栏算法channel

Python|高阶函数

01 函数名也是变量! abs(-100) 对于abs()这个函数,完全可以把函数名abs看成变量,它指向一个计算绝对值的函数! 因此,函数名其实就是指向...

38760
来自专栏大前端开发

ES6特性之:解构

解构(destructuring assignment), 也称解构赋值,这种语法可以方便的将数组元素或对象属性赋成新的变量。

6920
来自专栏desperate633

LintCode 编辑距离题目分析代码

给出两个单词word1和word2,计算出将word1 转换为word2的最少操作次数。

9920
来自专栏我爱编程

Day5函数式编程1/3

高阶函数 map map()函数接收两个参数,一个是函数,一个是Iterable,map将传入的函数依次作用到序列的每个元素,并把结果作为新的Iterator返...

29680
来自专栏Brian

C++ Virtual And Pure Virtual Explained

---- Virtual Virtual Function是成员函数,其行为在派生类中被覆盖。与非虚函数不同的是,即使没有关于类的实际类型的编译时信息,也会保留...

35960

扫码关注云+社区

领取腾讯云代金券