专栏首页武培轩的专栏排序算法-选择排序

排序算法-选择排序

算法简介

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

算法描述

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

代码实现

    /**
     * 选择
     *
     * @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 条评论
登录 后参与评论

相关文章

  • 排序算法-冒泡排序

    算法简介 冒泡排序(Bubble Sort)是一种典型的交换排序算法,持续比较相邻元素,大的挪到后面,因此大的会逐步往后挪,故称之为冒泡。 算法描述 比较相邻的...

    武培轩
  • 剑指Offer-旋转数组的最小数字

    package Array; /** * 旋转数组的最小数字 * 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 * 输入一个非递减...

    武培轩
  • Leetcode#500. Keyboard Row(键盘行)

    给定一个单词列表,只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。

    武培轩
  • iOS数组排序方法

    先回忆一下,大学期间学到的排序算法你还记得多少?? 那先充电一下常用排序算法总结,当然,google搜索"排序算法"会非常多,这个链接只是随意看到查看的,仅供...

    sweet说好的幸福
  • [PHP] 排序和查找算法

    冒泡排序的原理可以顾名思义:把每个数据看成一个气泡,按初始顺序自底向上依次对两两气泡进行比较,对上重下轻的气泡交换顺序(这里用气泡轻、重表示数据大、小),保证轻...

    陶士涵
  • Python实现归并排序

    归并排序(Merge Sort)是建立在归并操作上的一种效率很高的排序算法,比较占用内存。该算法是分治法(Divide and Conquer)的一个典型应用。

    Python碎片公众号
  • 【学点数据结构和算法】04-散列表

    前面已经陆陆续续写了几篇介绍数据结构的博客,包含数组,链表,栈和队列…本篇博客,我们再来学习一种有趣的数据结构——散列表。

    大数据梦想家
  • 大量GitHub用户遭黑客勒索:不交比特币就公开私有代码

    在 GitHub 上托管代码,请保护好自己的账户。近日,一名黑客入侵了大量 GitHub 账户的行动引发了人们的关注,据称他实施的攻击已经删除了很多人们托管的代...

    机器之心
  • 程序员遇到bug后的七种反应

    每一个被bug缠身的程序员,都想拥有孙悟空的本领。要么七十二变,要么一转眼灰飞烟灭 ? 1、谁动了我的代码 ? 这确实是一种曾相识的感觉,我经过无数次的解释都没...

    Java高级架构
  • 一个简易小工具,七牛Uploader for Octopress

    春节假期,带着电脑回家,蹭着邻居的网,除夕晚上用ruby写了一个简单的工具。安利一下,广而告之。

    技术小黑屋

扫码关注云+社区

领取腾讯云代金券