排序之选择排序

选择排序就是构建有序序列，对于未排序的下一个位置，在未排序序列中从前往后扫描，选择合适的元素。

图片来源：维基百科

• 选择排序是一种不稳定的排序方法。
• 选择排序的时间复杂度为 O(n²)。
• 选择排序的空间复杂度为 O(1)。

插入排序跟选择排序很相似。
插入排序是从选择下一个元素，然后在已经排序好的序列中从后往前遍历，插入到合适的位置。
选择排序是从选择下一个位置，然后从该位置的元素从前往后遍历，选择最小的值排序。

选择排序的伪代码：

FOR i = 0 to length(A) - 1
  minIndex ← i
  j ← i + 1
  WHILE j < length(A)
    IF A[j] < A[minIndex] THEN
      minIndex ← j
    ENDIF
    j ← j + 1
  ENDWHILE
  swap A[i] and A[minIndex]
ENDFOR