选择排序

选择排序和插入排序类似，也是分为已排序区域和未排序区域

插入排序是把key插入到已排序区域中合适的位置，使得已排序区域增长

而选择排序是将未排序区域中最小的元素放在第一个位置，来使得已排序区域增长

伪码如下：

SELECTION-SORT(A)
for i ← 1 to n do
 minIndex ← i
 for j ← i+1 to n do
  if A[j] < A[minIndex]
   then minIndex ← j
 end for
end for
 swapped with A[i] and A[minIndex]

C++代码：

void SelectionSort(vector<int> &arr){
    for(int i=0;i < arr.size();++i){
        int minIndex=i;
        for(int j=i+1;j < arr.size();++j){
            if(arr[minIndex] > arr[j])
                minIndex=j;
        }
        swap(arr[i],arr[minIndex]);
    }
}

算法正确性

循环不变式：

子序列$A[0…i-1]$保持有序

$Proof:$

初始：$A[0…-1]$没有元素
维持：假设$A[0…i-1]$有序，在下一次循环前，通过选择minIndex得到$A[i+1,n]$中最小元素的索引，并将它与$A[i]$交换，$A[0…i]$保持有序，由于递增，所以子序列$A[0…i-1]$有序
终止：终止时，$i=n$，$A[0…i-1]$有序，而$A[i]$是长度为1的序列最小值，同时也是整个序列的最大值，此时$A[0…n]$排序完成