选择排序 本页面将简要介绍选择排序。
简介 选择排序（英语：Selection sort）是一种简单直观的排序算法。它的工作原理是每次找出第 i A_{i..n} i
性质 稳定性 由于 swap（交换两个元素）操作的存在，选择排序是一种不稳定的排序算法。
时间复杂度 选择排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 O(n^2)
代码实现 伪代码 \begin{array}{ll} 1 & \textbf{Input. } \text{An array } A \text{ consisting of }n\text{ elements.} \\ 2 & \textbf{Output. } A\text{ will be sorted in nondecreasing order.} \\ 3 & \textbf{Method. } \\ 4 & \textbf{for } i\gets 1\textbf{ to }n-1\\ 5 & \qquad ith\gets i\\ 6 & \qquad \textbf{for }j\gets i+1\textbf{ to }n\\ 7 & \qquad\qquad\textbf{if }A[j]<A[ith]\\ 8 & \qquad\qquad\qquad ith\gets j\\ 9 & \qquad \text{swap }A[i]\text{ and }A[ith]\\ \end{array} C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14 // C++ Version
void selection_sort ( int * a , int n ) { for ( int i = 1 ; i < n ; ++ i ) { int ith = i ; for ( int j = i + 1 ; j <= n ; ++ j ) { if ( a [ j ] < a [ ith ]) { ith = j ; } } int t = a [ i ]; a [ i ] = a [ ith ]; a [ ith ] = t ; } }
Python # Python Version
def selection_sort ( a , n ):
for i in range ( 1 , n ):
ith = i
for j in range ( i + 1 , n + 1 ):
if a [ j ] < a [ ith ]:
ith = j
a [ i ], a [ ith ] = a [ ith ], a [ i ]
build 本页面最近更新：更新历史 edit 发现错误？想一起完善？ 在 GitHub 上编辑此页！ people 本页面贡献者：OI-wiki copyright 本页面的全部内容在 CC BY-SA 4.0 和 SATA 