选择排序基本信息

选择排序是一种排序算法，特别是就地比较排序。它具有 O(n2) 时间复杂度，使其在大型列表上效率低下，并且通常比类似的插入排序更差。选择排序因其简单性而着称，并且在某些情况下具有优于更复杂算法的性能优势，特别是在辅助存储器有限的情况下。

该算法将输入列表分为两部分：已经排序的项目子列表，在列表的前面（左侧）从左到右构建，以及剩余要排序的项目的子列表占用其余部分。名单。最初，排序的子列表为空，未排序的子列表是整个输入列表。该算法通过查找未排序子列表中的最小（或最大，取决于排序顺序）元素，与最左边的未排序元素（将其按排序顺序）交换（交换），并将子列表边界向右移动一个元素来继续。

选择排序的伪代码：

function select(list[1..n], k)
 for i from 1 to k
     minIndex = i
     minValue = list[i]
     for j from i+1 to n
         if list[j] < minValue
             minIndex = j
             minValue = list[j]
     swap list[i] and list[minIndex]
 return list[k]

选择排序的可视化：

https://i.stack.imgur.com/LZepY.gif

选择排序示例：

https://i.stack.imgur.com/CaSlf.jpg

辅助空间： O(n)
时间复杂度： O(n^2)