传习Chuanxi

选择排序

选择排序

掌握排序算法中的选择排序的算法思想、排序步骤及代码实现。

选择排序每轮在未排序区间里选出最小（或最大）元素，放到已排序区间末尾。内层扫描找最小下标 minIdx，外层与位置 i 交换。比较次数相对固定，与初始顺序关系不大。

GESP 四级爱考：交换次数上限、是否稳定（一般不稳定）、与冒泡/插入的对比。手算时记录「当前 i 到 n-1 谁最小」，交换一次即可。

void selection(int a[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        int minIdx = i;
        for (int j = i + 1; j < n; ++j)
            if (a[j] < a[minIdx]) minIdx = j;
        if (minIdx != i) swap(a[i], a[minIdx]);
    }
}

选择排序交换次数不超过 n-1，但元素移动少不等于总体更快——仍要记清 O(n²) 量级。与冒泡相比，选择排序每轮交换至多一次，因此交换次数往往更少，但比较次数仍与 n² 同阶。

选择排序是稳定的排序算法。

对数组 arr[] = {4, 3, 1, 5, 2} 进行升序排序，执行第一轮选择排序后数组 arr 中的内容是 {1, 4, 3, 5, 2}。

无论初始数组是否有序，选择排序都执行 O(n2)O(n^2) 次比较。

以下 C++ 代码，尝试对有 nn 个整数的数组 arr 进行排序。这个代码实现了选择排序算法。

for (int i = 0; i < n - 1; ++i) {
    int minIndex = i;
    for (int j = i + 1; j < n; ++j) {
        if (arr[j] < arr[minIndex])
            minIndex = j;
    }
    if (minIndex != i)
        swap(arr[i], arr[minIndex]);
}

下面代码试图实现选择排序，使其能对数组 nums 排序为升序，则横线上应分别填写（ ）。

void selectionSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < n; ++j) {
            if ( __________ ) {     // 在此处填入代码
                minIndex = j;
            }
        }
       ____________________; // 在此处填入代码
    }
}

A. 

nums[j] < nums[minIndex]
swap(nums[i], nums[minIndex])

B. 

nums[j] > nums[minIndex]
swap(nums[i], nums[minIndex])

C. 

nums[j] <= nums[minIndex]
swap(nums[j], nums[minIndex])

D. 

nums[j] <= nums[minIndex]
swap(nums[i], nums[j])

下面的函数 selectTopK() 实现从 nn 个学生中选出前 kk 名成绩最好的学生颁发奖学金（不需要对所有学生完全排序，只需要找出前 kk 名），则横线上应填写（ ）。

struct Student {
    string name;
    int score;
};

void selectTopK(Student students[], int n, int k) {
    for (int i = 0; i < k; i++) {
        int maxIdx = i;
        for (__________________) {  // 在此处填入代码
            if (students[j].score > students[maxIdx].score) {
                maxIdx = j;
            }
        }

        if (maxIdx != i) {
            Student temp = students[i];
            students[i] = students[maxIdx];
            students[maxIdx] = temp;
        }
    }
}

由于选择排序和插入排序的时间复杂度均为 O(n2)O(n^2)，在任何实际场景下两者的性能表现几乎相同，可以互相替代。

下面代码使用某种排序算法，将数组中的元素按从小到大排序。这段代码使用的排序算法是（ ）。

void mystery_sort(double arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minPos = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minPos]) {
                minPos = j;
            }
        }
        double temp = arr[i];
        arr[i] = arr[minPos];
        arr[minPos] = temp;
    }
}