「DSA」C++排序算法之选择排序_Selection Sort

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

在这里插入图片描述

✨博客主页
何曾参静谧的博客
📌文章专栏
「C/C++」C/C++程序设计
📚全部专栏
「VS」Visual Studio	「C/C++」C/C++程序设计	「UG/NX」BlockUI集合
「Win」Windows程序设计	「DSA」数据结构与算法	「UG/NX」NX二次开发
「QT」QT5程序设计	「File」数据文件格式	「PK」Parasolid函数说明

目录

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

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

一、引言

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

二、算法步骤

初始状态：假设有一个数组arr，长度为n。
第一轮排序：
- 在数组arr[0]到arr[n-1]中找到最小元素，假设它的位置是minIndex。
- 将arr[minIndex]与arr[0]交换位置。
第二轮排序：
- 在数组arr[1]到arr[n-1]中找到最小元素，假设它的位置是minIndex。
- 将arr[minIndex]与arr[1]交换位置。
重复步骤：
- 依次类推，直到数组的最后一个元素。
  
  动图来源：博主：双鱼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;
}

五、代码解析

函数selectionSort：
- 接受一个整数向量arr作为参数。
- 使用两层循环，外层循环控制当前排序的位置i，内层循环在未排序部分寻找最小元素的位置minIndex。
- 使用std::swap函数交换最小元素与当前位置i的元素。
函数printArray：
- 接受一个整数向量arr作为参数。
- 使用范围for循环遍历并打印数组中的每一个元素。
主函数main：
- 初始化一个待排序的数组arr。
- 打印排序前的数组。
- 调用selectionSort函数对数组进行排序。
- 打印排序后的数组。