选择排序是什么

小嘿 QA 2020-04-14 15:54:50 阅读(...)

选择排序是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

选择排序是什么

基本选择排序

选择排序输出的是原序列的一个重排<a1*,a2*,a3*,…,an*>;,使得 a1*<=a2*<=a3*<=…<=an*

排序算法有很多,包括插入排序,冒泡排序,堆排序,归并排序,选择排序,计数排序,基数排序,桶排序,快速排序等。插入排序,堆排序,选择排序,归并排序和快速排序,冒泡排序都是比较排序,它们通过对数组中的元素进行比较来实现排序,其他排序算法则是利用非比较的其他方法来获得有关输入数组的排序信息。

算法性能

时间复杂度

选择排序的交换操作介于 0 和 (n – 1) 次之间。选择排序的比较操作为 n (n – 1) / 2 次之间。选择排序的赋值操作介于 0 和 3 (n – 1) 次之间。

比较次数 O(n^2),比较次数与关键字的初始状态无关,总的比较次数 N=(n-1)+(n-2)+…+1=n*(n-1)/2。交换次数 O(n),最好情况是,已经有序,交换 0 次;最坏情况交换 n-1 次,逆序交换 n/2 次。交换次数比冒泡排序少多了,由于交换所需 CPU 时间比比较所需的 CPU 时间多,n 值较小时,选择排序比冒泡排序快。

0个人收藏 收藏

评论交流

泪雪默认头像 请「登录」后参与评论
  1. 加载中..

相关推荐

  • sort 排序

    排序算法稳定性是指什么

    排序算法稳定性指假定在待排序的记录序列中,存在多个具有相同的关键字的记录,经过排序这些记录的相对次序保持不变,则是稳定的;否则为不稳定。不稳定的算法在某种条件下可以变为稳定的算法,而稳定的算法在某种条件下也可以变为不稳定的算法。
  • 排序算法是什么

    排序算法是什么

    所谓排序就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。
  • Excel

    Excel筛选怎么用

    Excel 表格筛选功能的用法就是排序数据、文本筛选和数字筛选。首先打开 excel 表格,选择需要筛选的数据,然后点击主菜单中的“数据”菜单,选择筛选工具,然后就可以根据自己的需要对数据进行筛选或排序了。
  • program 程序

    快速排序算法是什么

    快速排序(Quicksort)是对冒泡排序的一种改进。它通过一趟排序将要排序的数据分割成独立的两部分,一部分的所有数据都比另一部分所有数据都小,再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,让整个数据变成有序序列。
  • programming 编程

    冒泡排序是什么

    冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序错误就把他们交换过来。
  • 打印机 printer

    为什么打印机总是显示脱机状态

    打印机总是显示脱机状态一般是连接出了问题;网络打印机可能是没有联网;打印机更改了设置;还有可能是不是打印组件不好,更换组件;打印后台服务程序处理失败而未能够打印任务会导致打印队列堵塞;驱动异常可以关闭所有打印机任务重启打印机。