选择排序(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$遍以后，该列表就被排好序了。

## 示意
你可以通过查看下面的动态图来获得直观的感受： 
![](https://leanote.com/api/file/getImage?fileId=58a6a303ab64414b06002ebf)[^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.