选择排序(Selection sort) gaunthan Posted on Feb 17 2017 ? Sorting ? ? Algorithm ? > **选择排序**(Selection sort)是排序算法的一种,它是蛮力思想的一个体现。 ## 思想 选择排序开始的时候,我们扫描整个序列,找到它的最小元素,然后和第一个元素交换,将最小元素放到它在有序表中的最终位置上。然后我们从第二个元素开始扫描列表,找到最后$n-1$个元素中的最小者,再和第二个元素交换位置,把第二小的元素放在它的最终位置上。一般来说,在对该列表做第$i$遍扫描的时候($i$的值从$0$到$n-2$),该算法在最后$n-i$个元素中寻找最小元素,然后拿它和$A_i$交换。在$n-1$遍以后,该列表就被排好序了。 ## 示意 你可以通过查看下面的动态图来获得直观的感受: [^wiki] [^wiki]:[Wikipedia - Selection sort](https://en.wikipedia.org/wiki/Selection_sort). ## 伪代码 下面是该算法的伪代码,其中假设列表是由数组实现的: ```cpp // 使用选择排序对给定的数组排序 // @input 一个待排序的数组A[0..n-1] // @output 升序排序的数组A[0..n-1] SelectionSort(A[0..n-1]) for i = 0 to n - 2 do min = i for j = i + 1 to n - 1 do if A[j] < A[min] min = j swap A[i] with A[min] ``` ## 效率分析 对于选择排序的分析是很简单的。输入的规模由元素的个数$n$决定,基本操作是键值比较`A[j] < A[min]`。这个比较的执行次数仅仅依赖于数组的规模,并由下面的求和公式给出: $$ C(n) = \sum_{i=0}^{n-2}\sum_{j=i+1}^{n-1}1 = \sum_{i=0}^{n-2}[(n-1)-(i+1)+1]=\sum_{i=0}^{n-2}(n-1-i)={(n-1)n\over2} \in \theta(n^2) $$ 因此,对于任何输入来说,选择排序都是一个$\theta(n^2)$的算法。然而,注意键的交换次数仅为$\theta(n)$,更精确一点是$n-1$次。这个特点使得选择排序在有些时候优于许多其它的排序算法。 ## References - 莱维汀, A.). 算法设计与分析基础(第3版)[M]. 清华大学出版社, 2015. 赏 Wechat Pay Alipay 选择问题(selection problem) 图搜索算法:广度优先查找