首页 > 编程语言 >(动画版)排序算法 -选择排序

(动画版)排序算法 -选择排序

时间:2024-11-11 12:49:14浏览次数:3  
标签:minIndex 动画版 int 元素 arr 选择 算法 排序

文章目录

1. 选择排序(Selection Sort)

1.1 简介

选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理是反复地从未排序部分选择最小(或最大)的元素,将其放到已排序部分的末尾。

1.2 选择排序的步骤

  1. 初始化:设定一个数组,假设其长度为 n
  2. 找到最小元素:从未排序部分中找到最小元素。
  3. 交换:将这个最小元素与未排序部分的第一个元素交换位置,这样最小元素就被放到了已排序部分的末尾。
  4. 缩小未排序部分:将未排序部分的第一个元素(即刚才交换后的位置)之后的元素作为新的未排序部分。
  5. 重复:重复步骤2到步骤4,直到整个数组排序完成。

1.3 选择排序的C实现

#include <stdio.h>

// 选择排序函数
void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;

    // 遍历数组
    for (i = 0; i < n - 1; i++) {
        // 假设当前元素为最小值
        minIndex = i;

        // 在未排序部分找到最小值的索引
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // 将找到的最小值与当前位置的值交换
        if (minIndex != i) {
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

// 打印数组函数
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 主函数
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前的数组: \n");
    printArray(arr, n);

    selectionSort(arr, n);

    printf("排序后的数组: \n");
    printArray(arr, n);

    return 0;
}

1.4 选择排序的时间复杂度

  • 最坏情况:O(n2),因为无论输入数组是什么,都需要进行 n(n-1)/2 次比较。
  • 平均情况:O(n2),与最坏情况相同。
  • 最好情况:O(n2),同样与最坏情况相同,因为每次都需要扫描未排序部分以找到最小值。

1.5 选择排序的空间复杂度

  • 空间复杂度:O(1),因为选择排序是原地排序算法,不需要额外的存储空间。

1.6 选择排序的动画

Selection Sort

标签:minIndex,动画版,int,元素,arr,选择,算法,排序
From: https://blog.csdn.net/qq_46538985/article/details/143678309

相关文章

  • 数组算法练习题
    第一题:寻找锦鲤公司年会有一个寻找锦鲤的游戏,每一个员工随意写一个字,如果在“锦鲤”词库中有这个字,那么就奖励500元锦鲤红包,否则就没有,每人只能玩一次。现有锦鲤字库如下,它们按照Unicode编码值从小到大排序:char[]koiFishWords={'一','今','地','定','年','开','我','果','......
  • [数组排序] 0384. 打乱数组
    文章目录1.题目大意2.题目大意3.示例4.解题思路5.参考代码1.题目大意384.打乱数组-力扣(LeetCode)2.题目大意描述:给定一个整数数组nums。要求:设计算法来打乱一个没有重复元素的数组。打乱后,数组的所有排列应该是等可能的。实现Solutionclass:Sol......
  • 算法性能测试基础
    算法的性能测试是一个综合评估算法在不同条件下的表现和效率的过程。在进行算法性能测试时,需要关注多个关键指标,以确保全面、准确地评估算法的性能。以下是对算法性能测试的详细解释和需要关注的指标的归纳:一、算法性能测试概述算法性能测试的目的是验证算法在各种输入情况下的......
  • 69.《排序》
    可算结束了简单数据结构的学习收官!壹排序的基本概念排序主要分为内部排序和外部排序(我考试主要涉及内部排序因此外部排序略过)对于内部排序算法都需要做的是比较和移动重点---稳定性:经过排序后能使关键字相同的元素保持原顺序中的相对位置不变(排序算法内允许有相同......
  • 后缀排序
    后缀排序即对字符串\(S\)的所有后缀根据字典序排序实现算法1:暴力排序直接\(O(n)\)比较,时间复杂度\(O(n^2\logn)\)算法2:倍增优化我们考虑长为\(2^k\)的串的比较,该串可以分为前后均长\(2^{k-1}\)的串,那么只要知道这两个串的排名,就可以对所有\(2^k\)的串进行双关键字排序于是......
  • 912. 排序数组
    题目链接本题使用的是快排解决。思路:「荷兰国旗」问题,具体思路跳转75.颜色分类代码classSolution{public:voidswap(vector<int>&nums,inti,intj){inttmp=nums[i];nums[i]=nums[j];nums[j]=tmp;}//[L,......
  • 毕业设计:python考研院校推荐系统 混合推荐 协同过滤推荐算法 爬虫 可视化 Django框架(
    毕业设计:python考研院校推荐系统混合推荐协同过滤推荐算法爬虫可视化Django框架(源码+文档)✅1、项目介绍技术栈:Python语言MySQL数据库Django框架协同过滤推荐算法requests网络爬虫pyecharts数据可视化html页面、爬取院校信息:https://yz.chsi.com.cn/sch/(研招网......
  • 基于game-based算法的动态频谱访问matlab仿真
    1.算法运行效果图预览(完整程序运行后无水印)   展示了负载因子P和次级传输功率不同的HPE。         从图中可以看出,随着|hPE|²扩大,用户P更好的为二级用户分配更多的频谱机会,以便刺激二级用户传输更多的干扰功率,因此,导致ρ的减少和Psu的增加。 ......
  • 基于免疫算法的TSP问题求解matlab仿真
    1.程序功能描述旅行商问题(TravellingSalesmanProblem,TSP)是一个经典的组合优化问题,其目标是在给定一组城市及其相互之间的距离情况下,寻找一条经过每个城市恰好一次且返回起点的最短回路。TSP因其NP完全性及广泛应用背景而备受关注。免疫算法(ImmuneAlgorithm,IA),作为......
  • 操作系统调度算法
    操作系统使用各种算法来有效地调度处理器上的进程。调度算法的目的最大CPU利用率公平分配CPU最大吞吐量最短周转时间最短的等待时间最短响应时间有以下算法可用于计划作业。1.先来先服务这是最简单的算法。最短到达时间的过程将首先获得CPU。到达时间越少,进程得到CPU的......