「DSA」C++排序算法 之 选择排序_Selection Sort_O(n²)

目录

• • @[TOC](目录)
  • 选择排序（Selection Sort）详解与C++实现
  • • 一、引言
    • 二、算法步骤
    • 三、时间复杂度分析
    • 四、C++实现
    • 五、代码解析
    • 六、总结

选择排序（Selection Sort）详解与C++实现

一、引言

选择排序是一种简单直观的排序算法，其基本思想是在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

二、算法步骤

1. 初始状态：假设有一个数组arr，长度为n。
2. 第一轮排序：
   • 在数组arr[0]到arr[n-1]中找到最小元素，假设它的位置是minIndex。
   • 将arr[minIndex]与arr[0]交换位置。
3. 第二轮排序：
   • 在数组arr[1]到arr[n-1]中找到最小元素，假设它的位置是minIndex。
   • 将arr[minIndex]与arr[1]交换位置。
4. 重复步骤：
   • 依次类推，直到数组的最后一个元素。
     
     动图来源：博主：双鱼211《六大排序》

三、时间复杂度分析

• 最坏情况：O(n²)
  • 每一轮都需要扫描未排序部分以找到最小元素，总共需要进行n-1次扫描。
• 最好情况：O(n²)
  • 即使数组已经有序，选择排序的时间复杂度仍然是O(n²)，因为每一轮都需要扫描整个未排序部分。
• 空间复杂度：O(1)
  • 选择排序是原地排序算法，只需要常数级别的额外空间。

四、C++实现

下面是一个用C++实现选择排序的完整代码：

#include <iostream>
#include <vector>

// 选择排序函数
void selectionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        // 假设当前元素i是最小值
        int minIndex = i;
        // 在i+1到n-1范围内找到最小值
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 将找到的最小值与arr[i]交换
        std::swap(arr[minIndex], arr[i]);
    }
}

// 打印数组函数
void printArray(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

    std::cout << "排序前的数组: ";
    printArray(arr);

    selectionSort(arr);

    std::cout << "排序后的数组: ";
    printArray(arr);

    return 0;
}

五、代码解析

1. 函数selectionSort：

   • 接受一个整数向量arr作为参数。
   • 使用两层循环，外层循环控制当前排序的位置i，内层循环在未排序部分寻找最小元素的位置minIndex。
   • 使用std::swap函数交换最小元素与当前位置i的元素。

2. 函数printArray：

   • 接受一个整数向量arr作为参数。
   • 使用范围for循环遍历并打印数组中的每一个元素。

3. 主函数main：

   • 初始化一个待排序的数组arr。
   • 打印排序前的数组。
   • 调用selectionSort函数对数组进行排序。
   • 打印排序后的数组。

六、总结

选择排序是一种简单但效率较低的排序算法，适用于小规模数据的排序。虽然其时间复杂度较高，但由于其实现简单，易于理解和实现，因此在某些特定场景下仍然有一定的应用价值。

希望这篇文章能帮助你更好地理解选择排序及其C++实现。如果有任何问题或需要进一步的解释，请随时提问！