不断在未排序列中，选择最小元素，添加到已排序列末尾
算法步骤（升序）：

• 先从未排序列中找到最小元素，存放在已序序列起始位置
• 从未排序列中继续寻找最小元素，然后放到已排序列末尾
• 重复第二步，直到未排序列没有元素

代码实现

// 选择排序
public void SelectionSort(int[] arr)
{
    for (int i = 0; i < arr.Length - 1; i += 1)
    {
        int min = arr[i];
        for (int j = i + 1; j < arr.Length; j += 1)
        {
            if (arr[j] < min)
            {
                int temp = arr[j];
                arr[j] = min;
                min = temp;
            }
        }
        arr[i] = min;
    }
}

优化思路

上面的算法中，是保存最小值来一一比对，一旦最小值发生变化，就会交换数组的两个值。而每一次对未排序列的遍历，我们最终只需要知道一个结果，那就是最小值在哪个位置，和未排序列的第一个元素交换就行，不需要每次都交换数组两个值。所以通过保存最小值下标的方式来实现。

// 选择排序
public static void Selection(int[] arr)
{
    for (int i = 0; i < arr.Length - 1; ++i)
    {
        int min = i;// 假定第一个元素是最小的，保存下标
        for (int j = i + 1; j < arr.Length; ++j)// 遍历未排序列，遇到更小元素，则下标值改变
        {
            if (arr[j] < arr[min])
            {
                min = j;
            }
        }

        // 遍历完后，这一次遍历的最小元素添加到已排序列末尾（未排序列开头位置）
        int tmp = arr[i];
        arr[i] = arr[min];
        arr[min] = tmp;
    }
}

算法复杂度

	平均	最好	最坏	空间复杂度	稳定不？
选择排序					不稳定

必须遍历全部未排序列，不能通过一次遍历就知道序列是否有序，所以时间复杂度最好也是