当前位置: 首页 > article >正文

算法实现 - 选择排序(Selection sort) - 理解版

算法介绍

一种简单直观的排序算法,其基本思想是每次从待排序的元素中选择最小(或最大)的元素,放到已排序序列的末尾,以此类推,直到所有元素排序完成。

选择排序适用于数据量小或者对排序效率要求不高的场景,常用于教学和学习排序算法的基本概念。

算法分析

核心思想

  1. 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
  2. 从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
  3. 重复第二步,直到所有元素均排序完毕。

图解运行过程

使用数列a[] = {40, 20, 30, 60, 10, 50} 进行分析
在这里插入图片描述

分析:
第1轮(i=0):

  • 当前数组: {40, 20, 30, 60, 10, 50}
  • 找到最小值:
    • 与 40 比较:20 是更小的,更新 minIndex = 1
    • 与 20 比较:30 > 20,不更新
    • 与 30 比较:60 > 20,不更新
    • 与 60 比较:10 是更小的,更新 minIndex = 4
    • 与 10 比较:50 > 10,不更新
  • 最小值为 10,位置为 4,交换 40 和 10。

第2轮(i=1):

  • 当前数组: {10, 20, 30, 60, 40, 50}
  • 找到最小值:
    • 与 20 比较:30 > 20,不更新
    • 与 20 比较:60 > 20,不更新
    • 与 20 比较:40 > 20,不更新
    • 与 20 比较:50 > 20,不更新
  • 最小值为 20,位置为 1,不需要交换。

第3轮(i=2):

  • 当前数组: {10, 20, 30, 60, 40, 50}
  • 找到最小值:
    • 与 30 比较:60 > 30,不更新
    • 与 30 比较:40 > 30,不更新
    • 与 30 比较:50 > 30,不更新
  • 最小值为 30,位置为 2,不需要交换。

第4轮(i=3):

  • 当前数组: {10, 20, 30, 60, 40, 50}
  • 找到最小值:
    • 与 60 比较:40 是更小的,更新 minIndex = 4
    • 与 60 比较:50 > 40,不更新
  • 最小值为 40,位置为 4,交换 60 和 40。

第5轮(i=4):

  • 当前数组: {10, 20, 30, 40, 60, 50}
  • 找到最小值:
    • 与 60 比较:50 是更小的,更新 minIndex = 5
  • 最小值为 50,位置为 5,交换 60 和 50。

第6轮(i=5):

  • 当前数组: {10, 20, 30, 40, 50, 60}
  • 这是最后一个元素,不需要再查找。
  • 最终结果数组: {10, 20, 30, 40, 50, 60}

算法稳定性和复杂度

稳定性

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

选择排序不稳定的原因在于其工作原理:在每一轮选择最小(或最大)元素的过程中,如果存在多个相同的最小(或最大)元素,选择排序可能会将它们的位置交换,从而导致这些相同元素的相对位置发生改变。

示例分析:

考虑数组 { 4 a 4_a 4a, 3, 4 b 4_b 4b, 2} 进行选择排序的过程:

第一轮: 找到最小值 2,交换到最前面。结果为 {2, 3, 4, 4 a 4_a 4a}。

第二轮: 找到下一个最小值 3,已在正确的位置,无需交换。结果仍为 {2, 3, 4, 4 a 4_a 4a}。

第三轮: 找到下一最小值 4,发现最后的 4 与当前 4 交换,结果变为 {2, 3, 4 a 4_a 4a, 4 b 4_b 4b}。

在整个排序过程中,两个 4 的相对位置没有发生变化。但如果选择排序选择了交换的策略,比如有多个相同最小值造成的交换,会使 4 的相对顺序发生变化。

时间复杂度

最差情况

基本操作:
循环遍历:遍历未排序部分以找到最小(或最大)元素。
交换元素:将找到的最小(或最大)元素与未排序部分的第一个元素交换位置。

执行次数:
对于长度为 n 的数组,选择排序需要进行 n-1 轮选择。在第 i 轮选择中,算法需要在剩余的 n-i 个元素中找到最小(或最大)元素,这需要 n-i 次比较。因此,总比较次数是:
C ( n ) = ( n − 1 ) + ( n − 2 ) + . . . + 2 + 1 = ( n − 1 ) n 2 C(n) = (n-1) + (n-2) + ... + 2 + 1 = \frac{(n-1)n}{2} C(n)=(n1)+(n2)+...+2+1=2(n1)n

交换操作在最坏情况下也需要 n-1 次,因为每次都需要交换找到的最小(或最大)元素与未排序序列的第一个元素。

大O表示:

总操作次数(比较和交换)接近于 n 2 2 \frac{n^2}{2} 2n2,因此最差情况下的时间复杂度为 O(n^2)

平均情况

基本操作:
平均情况下,选择排序的基本操作与最差情况相同,因为每一轮都需要在剩余的未排序元素中找到最小(或最大)元素。

执行次数:
平均情况下,每轮选择操作的次数仍然是 n-i 次比较,总比较次数仍然是 n(n-1)/2。交换操作的次数仍然是 n-1。

大O表示:

总操作次数(比较和交换)接近于 n 2 2 \frac{n^2}{2} 2n2,因此最差情况下的时间复杂度为 O(n^2)

空间复杂度

选择排序是一种原地排序算法,不需要额外的存储空间,因此:

空间复杂度: O(1)

代码实现

老规矩,上原滋原味的代码💙C语言💙,

#include <stdio.h>

/**
 * Selection sort by C Lang.
 *
 *  params:
 *      array -- the data need to sort
 *      n -- the length of array
 */
void selectSort(int arr[], int n)
{
    // Notice: outter loop max running time is `n-2`
    for (size_t i = 0; i < n - 1; i++)
    {
        // Assume the current position holds the minimum element
        int minIndex = i;

        // Find the minimun in arr[i+1...n].
        for (size_t j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[minIndex])
            {
                // Update minIndex if a smaller element is found
                minIndex = j;
            }
        }

        // Move minimum element to its correct position
        if (minIndex != i)
        {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

/**
 * show array
 */
void printArray(int arr[], int n)
{
    for (size_t i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
}

int main()
{
    int arr[] = {40, 20, 30, 60, 10, 50};
    // calculate the length of a array
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("before sort: \n");
    printArray(arr, n);

    selectSort(arr, n - 1);

    printf("after sort: \n");
    printArray(arr, n);

    return 0;
}

欢迎⭐️,附上我的Github,选择排序源代码>>


http://www.kler.cn/a/376219.html

相关文章:

  • 刘艳兵-DBA021-升级到Oracle Database 12c时,关于使用Export/Import方法迁移数据的说法是正确的?
  • 杂项——USB键盘与鼠标流量分析——BUUCTF——流量分析
  • 告别繁琐统计,一键掌握微信数据
  • CSS例子: 横向排列的格子
  • webrtc agc2实现原理
  • 台式电脑如何改ip地址:全面解析与实操指南
  • STM32 HAL库 SPI驱动1.3寸 OLED屏幕
  • Django目录结构最佳实践
  • git常见用法【持续补充……】
  • 河南高校大数据实验室建设案例分享
  • Qt 实战(10)模型视图 | 10.6、自定义 QTableView
  • [MRCTF2020]PYWebsite1
  • jenkins 构建报错 Cannot run program “sh”
  • Uniapp的H5以及App不支持后端传FormData类型参数的解决方案
  • C#笔记——委托(2)
  • 浅谈人工智能之DB-GPT环境安装
  • SpringBoot3使用MyBatisPlus时遇到的问题 Invalid bean definition with name
  • python编程-类的特殊方法
  • Rust 力扣 - 2653. 滑动子数组的美丽值
  • 使用Docker Compose搭建多服务应用
  • Matlab车牌识别课程设计报告模板(附源代码)
  • Flutter鸿蒙next 封装 Dio 网络请求详解:登录身份验证与免登录缓存
  • layui tree customSelet选中的内容重写,查找父级
  • Flume的安装配置
  • 服务器文件访问协议
  • go语言回调函数的使用