C++选择排序算法实例详解

C++选择排序算法实例详解

选择排序算法简介

选择排序是一种简单直观的排序算法，其思想是首先找到序列中的最小值，然后将其放到序列的最前面。接着，从剩余序列中找到次小值，将其放到已排序序列的末尾。以此类推，直到排序完成。

选择排序算法的时间复杂度为$O(n^2)$，空间复杂度为$O(1)$，并且由于其算法思想简单，代码实现容易，所以在实际应用中还是比较常见的排序算法之一。

C++选择排序实现

以下是C++中选择排序的实现代码：

#include <iostream>
#include <vector>
using namespace std;

void selectionSort(vector<int>& arr) {
    int n = arr.size(); // 计算数组的大小
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i; // 定义最小值的下标为i
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j; // 更新最小值的下标
            }
        }
        swap(arr[i], arr[minIdx]); // 将当前最小值放到正确的位置
    }
}

int main() {
    vector<int> arr{9, 2, 1, 4, 3, 7, 5};
    selectionSort(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

代码中的selectionSort函数接受一个整型数组作为参数，将其进行排序。n表示数组的大小，第一个for循环用于遍历数组的除最后一个元素以外的所有元素，每次循环找到未排序序列中的最小值，并将其放到已排序序列的末尾。内层的for循环用于查找未排序序列中的最小值，minIdx变量记录当前最小值的下标。swap函数用于交换数组中的元素。

选择排序示例1

假设现有一个数组arr为 {9, 4, 6, 1, 3}，按照选择排序的方法对其进行排序。

1. 首先，最小值为1，将此值与第一个元素9交换位置，现在数组变为{1, 4, 6, 9, 3}。
2. 接着，找到次小值3，将其与第二个元素4交换位置，现在数组变为{1, 3, 6, 9, 4}。
3. 然后，找到次小值4，将其与第三个元素6交换位置，现在数组变为{1, 3, 4, 9, 6}。
4. 然后，找到次小值6，将其与第四个元素9交换位置，现在数组变为{1, 3, 4, 6, 9}。
5. 最后，遍历完成后，得到已经排好序的数组{1, 3, 4, 6, 9}。

选择排序示例2

假设现有一个数组arr为 {5, 8, 1, 3, 6, 4}，按照选择排序的方法对其进行排序。

1. 首先，最小值为1，将此值与第一个元素5交换位置，现在数组变为{1, 8, 5, 3, 6, 4}。
2. 接着，找到次小值3，将其与第三个元素5交换位置，现在数组变为{1, 8, 3, 5, 6, 4}。
3. 然后，找到次小值4，将其与第四个元素5交换位置，现在数组变为{1, 8, 3, 4, 6, 5}。
4. 接下来，找到次小值5，将其与最后一个元素6交换位置，现在数组变为{1, 8, 3, 4, 5, 6}。
5. 遍历完成后，得到已经排好序的数组{1, 3, 4, 5, 6, 8}。

结语

以上就是C++中选择排序的实现方法，希望对大家有所帮助。