C++如何实现选择排序 C++选择排序的代码实现与优化-C++-PHP中文网

C++如何实现选择排序 C++选择排序的代码实现与优化

尼克

发布： 2025-06-23 20:14:01

原创

526人浏览过

选择排序的时间复杂度是o(n²)，因为外层循环遍历n-1次，内层循环平均遍历n次寻找最小值，即使已排序仍需完整执行循环。空间复杂度为o(1)，因其是原地排序算法无需额外空间。优化方法包括减少不必要的交换、使用高效比较操作、尝试并行化处理，但效果有限，更佳方案是选用更高效算法。选择排序优点为简单直观、内存占用少、交换次数少；缺点为时间复杂度高、排序不稳定。相比其他算法，冒泡排序交换次数更多，插入排序在基本有序数据中效率更高，归并和快速排序则适合大规模数据。

C++如何实现选择排序 C++选择排序的代码实现与优化

C++实现选择排序，核心在于每次从未排序的部分找到最小（或最大）元素，然后将其放到已排序部分的末尾。简单来说，就是不断选择剩余元素的最小值。

#include <iostream>
#include <vector>
#include <algorithm> // 为了使用 std::swap

void selectionSort(std::vector<int>& arr) {
    int n = arr.size();
    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) {
            std::swap(arr[i], arr[minIndex]);
        }
    }
}

int main() {
    std::vector<int> data = {64, 25, 12, 22, 11};
    selectionSort(data);
    std::cout << "排序后的数组: \n";
    for (int val : data) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
    return 0;
}

登录后复制

选择排序的时间复杂度是多少？为什么？

选择排序的时间复杂度是O(n^2)，这是因为外层循环需要遍历n-1次，内层循环每次需要遍历未排序的部分找到最小值，平均下来也是接近n次。即使在最好的情况下（数组已经排序），选择排序仍然需要完整的内外循环来确认最小值，所以时间复杂度不会改变。空间复杂度是O(1)，因为它是一个原地排序算法，不需要额外的空间。

如何优化C++选择排序的性能？

选择排序本身的优化空间不大，因为它必须遍历所有元素来找到最小值。不过，可以考虑以下几点：

立即学习“C++免费学习笔记（深入）”；

减少不必要的交换： 在minIndex != i时才进行交换，避免了自身与自身的交换。
使用更快的比较操作： 对于复杂的数据类型，自定义比较函数可能会有性能提升空间，但对于基本类型如int，提升有限。
并行化： 理论上，可以尝试将寻找最小值的过程并行化，但这会增加额外的开销，对于小规模数据可能得不偿失。对于大规模数据，可以考虑使用更高效的排序算法，比如归并排序或快速排序。

实际上，与其优化选择排序本身，不如直接选择更高效的排序算法。选择排序通常只在教学或小规模数据排序时使用。