选择排序就是重复“从待排序的数据中寻找最小值,将其与序列最左边的数字进行交换”。这一操作的算法。在序列中寻找最小值时使用的是线性查找。(每一趟比较出最小的数)

Example:
排序前:3 1 4 5 2
第1趟:1 3 4 5 2
第2趟:1 2 4 5 3
第3趟:1 2 3 5 4
第4趟:1 2 3 4 5

选择排序使用了线性查找来寻找最小值,因此在第 1 轮中需要比较 n -1 个数字,第2 轮需要比较 n -2 个数字……到第 n -1 轮的时候就只需比较 1 个数字了。因此,总的比较次数与冒泡排序的相同,都是 (n-1)+(n-2)+…+1 ≈ n2/2 次。每轮中交换数字的次数最多为 1 次。如果输入数据就是按从小到大的顺序排列的,便不需要进行任何交换。选择排序的时间复杂度也和冒泡排序的一样,都为 O(n^2)。

void selection(int num[], int n)
{
    int temp;
    for (int i = 0; i < n - 1; i++) //开始选择排序
        //每次以num[i]为基准值 num[i]为当前最小值
        for (int j = i + 1; j < n; j++)
            if (num[i] > num[j])
            {
                //遍历数组中的元素进行比较 小于基准值就进行交换
                temp = num[i];
                num[i] = num[j];
                num[j] = temp;
            }
}
参考书籍:1.《算法图解》作者:[美] Aditya Bhargava;译者:袁国忠;ISBN:978-7-115-44763-0
2.《我的第一本算法书》 作者:(日)石田保辉,(日)宫崎修;译者:张贝;ISBN:978-7-115-49524-2