【C++】c++排序算法入门之选择排序

  • 开发
  • 46

文章目录

前言

本章节主要讲述选择排序的相关内容。

学习路线：C++从入门到NOI学习路线

学习大纲：C++全国青少年信息学奥林匹克竞赛（NOI）入门级-大纲

上一站：c++排序算法入门之插入排序

下一站：

一、选择排序

1.1 基本思想

选择排序算法的主要思想是通过逐步寻找并交换当前未排序部分的最小（或最大）元素来构建有序序列。

选择排序的详细步骤：

  1. 初始化：从待排序序列的第一个元素开始。
  2. 查找最小（或最大）值：在剩余未排序的所有元素中，找到一个最小（或按降序排列时的最大）的元素。
  3. 交换位置：将找到的最小（或最大）元素与未排序部分的第一个元素交换位置。这样，该元素就被放置到了正确的位置上——已排序序列的末尾。
  4. 更新范围：接下来的过程只针对剩余未排序的元素进行，不再考虑已经排序的部分。
  5. 重复过程：重复上述步骤，即在新的未排序部分中继续寻找剩余元素中的最小（或最大）值，并将其移动到已排序序列的末尾。
  6. 终止条件：当整个序列都被遍历过一遍且所有元素都经过了这样的比较和交换后，排序完成。

选择排序的时间复杂度分析：

  • 最好情况：无论输入数据如何，选择排序的时间复杂度都是固定的。即使数组已经完全有序，它仍然需要遍历所有元素进行比较和可能的交换，因此最好、最坏和平均时间复杂度均为
    O(n²)。
  • 空间复杂度：由于选择排序是原地排序算法，只需要常数级的额外空间，所以空间复杂度为 O(1)。

尽管选择排序易于理解并实现，但由于其较高的时间复杂度，在处理大量数据时效率较低，不适用于对性能要求较高的场景。但在实际应用中，对于小规模数据或者特定场合（如内存非常有限），选择排序仍有一定的价值。

1.2 排序过程

假设你正在整理一叠扑克牌，你想按照点数从小到大进行排列。

  1. 初始状态：桌上有一堆乱序的扑克牌。
    ![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/f45c03381c224e0391bbd0a822ba550d.png
  2. 第一步：你从这堆牌中任意拿起一张，然后查看剩下的所有牌，从中找出点数最小的那张。

在这里插入图片描述
假设我们都先拿未排序的第一张，然后用一个变量记录下它在的位置，注意这个变量始终会记住最小牌的下标。

在这里插入图片描述
用Q与后面的牌进行比较大小。

在这里插入图片描述

如果出现一张牌比Q小，那么将新的牌位置去替换旧牌的位置，注意这里并不是要将他们交换，而是将minIndex的值换成4的下标。

在这里插入图片描述
当然后续比较大小时，牌就变成了4。

在这里插入图片描述
我们是要找到最小数，因此对于大于4的牌都不用理会。

重复上面的过程，我们会找到最小数2。

  1. 交换位置：将找到的最小点数的牌放在手边已排序部分的顶部，即你现在只有一张排好序的牌。

在这里插入图片描述

交换以后的牌序如下图所示：

在这里插入图片描述

  1. 重复上述过程，每次都在剩余的未排序扑克牌中找出最小点数的牌并放置到已排序部分的末尾。

第二轮：在剩余未排序的七张牌中找到最小点数的牌，这里是黑桃3。

在这里插入图片描述

第三轮：在剩余未排序的六张牌中找到最小点数的牌，这里是黑桃4。

在这里插入图片描述

第四轮：在剩余未排序的五张牌中找到最小点数的牌，这里是方片5。

在这里插入图片描述

第五轮：在剩余未排序的四张牌中找到最小点数的牌，这里是梅花7。

在这里插入图片描述

第六轮：在剩余未排序的三张牌中找到最小点数的牌，这里是梅花J。

在这里插入图片描述

第七轮：在剩余未排序的两张牌中找到最小点数的牌，这里是红桃Q。

在这里插入图片描述

至此，经过七轮选择排序后，我们得到按照点数从小到大排列的扑克牌序列。

在这里插入图片描述

二、例题讲解

问题一：1010 - 数组元素的排序

对数组的元素按从小到大进行排序。

在这里插入图片描述

1.分析问题

  1. 已知：n个整数的数组
  2. 未知：更新后的数组
  3. 关系：从小到大进行排序-冒泡排序

2.定义变量

根据分析的已知，未知按需要定义变量。

	//二、数据定义 
	int n,a[10];

3.输入数据

从键盘读入。

//三、数据输入 
	cin>>n;
	for(int i=0;i<n;i++){
   
		cin>>a[i];
	}

4.数据计算

选择排序。

	//排序1：选择 
	 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) {
   
            swap(arr[i], arr[minIndex]);
        }
    }

5.输出结果

#include<iostream>
using namespace std;
int main(){
   
	//一、分析问题
	//已知：n个整数的数组
	//未知：更新后的数组 
	//关系：从小到大进行排序-冒泡排序 
	//二、数据定义 
	int n,arr[10];
	//三、数据输入 
	cin>>n;
	for(int i=0;i<n;i++){
   
		cin>>arr[i];
	}
	//四、数据计算 
	//排序1：选择 
	 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) {
   
            swap(arr[i], arr[minIndex]);
        }
    }
	//五、输出结果 
	for(int i=0;i<n;i++){
   
		cout<<arr[i]<<" ";
	}
	
	return 0;
}

问题二：1166 - 数的排序

输入 n 个不超过 30000 的整数（n≤10 ）。然后求出每个数的数字和，再按每个数的数字和由小到大排列输出。

在这里插入图片描述

1.分析问题

  1. 已知：n个不超过30000的整数的数组
  2. 未知：更新后的数组
  3. 关系：从小到大排列的每个数的数位和

2.定义变量

根据分析的已知，未知按需要定义变量。
sum：和。

	//二、数据定义 
	int n,a[20],sum;

3.输入数据

从键盘读入。

每个数字的数位和，因此使用短除法获得各位余数。

//三、数据输入 
	cin>>n;
	for(int i=0;i<n;i++){
   
		cin>>a[i];
		sum=0;
		while(a[i]>0){
   
			sum+=a[i]%10;
			a[i]/=10;
		}
		a[i]=sum;
	}

4.数据计算

选择排序。

//四、数据计算 
	 for (int i = 0; i < n - 1; i++) {
    // 迭代所有元素，除了最后一个（因为最后一个是已排序部分的末尾）
        int minIndex = i; // 假设当前元素为最小值

        // 寻找剩余未排序部分中的最小值索引
        for (int j = i + 1; j < n; j++) {
   
            if (a[j] < a[minIndex]) {
   
                minIndex = j; // 更新找到的最小值索引
            }
        }

        // 将找到的最小值与当前位置的元素交换
        if (minIndex != i) {
   
            swap(a[i], a[minIndex]);
        }
    }

5.输出结果

#include<iostream>
using namespace std;
int main(){
   
	//一、分析问题
	//已知：n个不超过30000的整数的数组 
	//未知：更新后的数组 
	//关系：从小到大排列的每个数的数位和

	
	//二、数据定义 
	int n,a[20],sum; 
	

	//三、数据输入 
	cin>>n;
	for(int i=0;i<n;i++){
   
		cin>>a[i];
		sum=0;
		while(a[i]>0){
   
			sum+=a[i]%10;
			a[i]/=10;
		}
		a[i]=sum;
	}
	//四、数据计算 
	 for (int i = 0; i < n - 1; i++) {
    // 迭代所有元素，除了最后一个（因为最后一个是已排序部分的末尾）
        int minIndex = i; // 假设当前元素为最小值

        // 寻找剩余未排序部分中的最小值索引
        for (int j = i + 1; j < n; j++) {
   
            if (a[j] < a[minIndex]) {
   
                minIndex = j; // 更新找到的最小值索引
            }
        }

        // 将找到的最小值与当前位置的元素交换
        if (minIndex != i) {
   
            swap(a[i], a[minIndex]);
        }
    }

	//五、输出结果 
	for(int i=0;i<n;i++){
   
		cout<<a[i]<<" ";
	} 
	return 0;	
}

问题三：1175 - 语文成绩

给出 N (5≤N≤150 )个人的语文成绩，求 N 个人的语文总分和平均分，并按成绩高低排序后输出。

在这里插入图片描述

1.分析问题

  1. 已知：N个人的语文成绩
  2. 未知：总分sum 平均分avg 排名顺序
  3. 关系：顺序从高到低

2.定义变量

根据分析的已知，未知按需要定义变量。

	//二、数据定义
	int n,a[200],sum=0;
	double avg=0;

3.输入数据

从键盘读入。

	//三、数据输入 
	cin>>n;
	for(int i=0;i<n;i++){
   
		cin>>a[i];
		sum+=a[i];
	}

4.数据计算

选择排序，注意是从高到低排列。

//四、数据计算 
	avg=sum*1.0/n;
	for (int i = 0; i < n - 1; i++) {
    // 迭代所有元素，除了最后一个（因为最后一个是已排序部分的末尾）
        int maxIndex = i; // 假设当前元素为最小值

        // 寻找剩余未排序部分中的最小值索引
        for (int j = i + 1; j < n; j++) {
   
            if (a[j] > a[maxIndex]) {
   
                maxIndex = j; // 更新找到的最小值索引
            }
        }

        // 将找到的最小值与当前位置的元素交换
        if (maxIndex != i) {
   
            swap(a[i], a[maxIndex]);
        }
    }

5.输出结果

#include<iostream>
using namespace std;
int main(){
   
	//一、分析问题
	//已知：N个人的语文成绩
	//未知：总分sum 平均分avg 排名顺序 
	//关系：顺序从高到低

	
	//二、数据定义
	int n,a[200],sum=0;
	double avg=0; 
	

	//三、数据输入 
	cin>>n;
	for(int i=0;i<n;i++){
   
		cin>>a[i];
		sum+=a[i];
	}
	//四、数据计算 
	avg=sum*1.0/n;
	for (int i = 0; i < n - 1; i++) {
    // 迭代所有元素，除了最后一个（因为最后一个是已排序部分的末尾）
        int maxIndex = i; // 假设当前元素为最小值

        // 寻找剩余未排序部分中的最小值索引
        for (int j = i + 1; j < n; j++) {
   
            if (a[j] > a[maxIndex]) {
   
                maxIndex = j; // 更新找到的最小值索引
            }
        }

        // 将找到的最小值与当前位置的元素交换
        if (maxIndex != i) {
   
            swap(a[i], a[maxIndex]);
        }
    }

	//五、输出结果 
	cout<<sum<<endl;
	printf("%.2f\n",avg);
	for(int i=0;i<n;i++){
   
		cout<<a[i]<<" ";
	}
	return 0;	
}

问题四：1233 - 求中位数

中位数指的是一组数，如果按照大小排序排好后最中间的那个数的值，如果有偶数个元素，那么就是最中间两个数的平均数！
比如：2 5 8 1 6 ，排序后的结果为 1 2 5 6 8 ，那么这组数的中位数就是 5 ！
再比如： 8 9 1 2 3 0 ，排序后的结果为0 1 2 3 8 9 ，那么这组数的中位数就是 (2+3)/2=2.5 。

在这里插入图片描述

1.分析问题

  1. 已知：一组数
  2. 未知：中位数 median
  3. 关系：最中间的那个数的值，有偶数个元素，那么就是最中间两个数的平均数

2.定义变量

根据分析的已知，未知按需要定义变量。

	//二、数据定义 
	int n,a[100]; 
	double median;

3.输入数据

从键盘读入。

	//三、数据输入 
	cin>>n;
	for(int i=0;i<n;i++){
   
		cin>>a[i];
	}

4.数据计算

想要求出一堆数中的中位数，必然先对它们进行排序。

选择排序。

//四、数据计算 
	for(int i=0;i<n-1;i++){
   
		int minIndex=i;
		for(int j=i+1;j<n;j++){
   
			if(a[j]<a[minIndex]){
   
				minIndex=j;
			}
		} 
		if(i!=minIndex){
   
			swap(a[i], a[minIndex]);
		}
	}
	if(n%2==0){
   
		median=(a[n/2]+a[n/2-1])*1.0/2;
	}else{
   
		median=a[n/2]*1.0;
	}

5.输出结果

#include<iostream>
using namespace std;
int main(){
   
	//一、分析问题
	//已知：一组数
	//未知：中位数 median
	//关系：最中间的那个数的值，有偶数个元素，那么就是最中间两个数的平均数 

	
	//二、数据定义 
	int n,a[100]; 
	double median;

	//三、数据输入 
	cin>>n;
	for(int i=0;i<n;i++){
   
		cin>>a[i];
	}
	
	//四、数据计算 
	for(int i=0;i<n-1;i++){
   
		int minIndex=i;
		for(int j=i+1;j<n;j++){
   
			if(a[j]<a[minIndex]){
   
				minIndex=j;
			}
		} 
		if(i!=minIndex){
   
			swap(a[i], a[minIndex]);
		}
	}
	if(n%2==0){
   
		median=(a[n/2]+a[n/2-1])*1.0/2;
	}else{
   
		median=a[n/2]*1.0;
	}
	

	//五、输出结果 
	printf("%.1f",median);
	return 0;	
}

三、练习

请用选择排序。

问题一：1172 - 寻找第K大数

在这里插入图片描述

问题二：1221 - 优秀成绩的平均分

在这里插入图片描述

问题三：1242 - 第K大与第K小数

在这里插入图片描述

问题四：1399 - 学员的名次？

在这里插入图片描述

四、总结

以上就是本节关于选择排序的全部内容。

觉得本文还阔以滴，还请点赞、关注、收藏。

在这里插入图片描述

阅读全部

相关推荐

  5. 算法之选择排序

    2024-01-30 19:12:01       49 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-01-30 19:12:01       94 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-01-30 19:12:01       100 阅读

  9. 在Django里面运行非项目文件

    2024-01-30 19:12:01       82 阅读

  19. Python语言-面向对象

    2024-01-30 19:12:01       91 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-01-30 19:12:01       85 阅读

热门阅读

  4. LeetCode 2808. 使循环数组所有元素相等的最少秒数，简单哈希

    2024-01-30 19:12:01       67 阅读

  9. chatgpt搭建

    2024-01-30 19:12:01       48 阅读

  11. fMRI数据处理（随时更新）

    2024-01-30 19:12:01       47 阅读

  15. Golang并发控制方式有几种？

    2024-01-30 19:12:01       58 阅读

  17. Redis有哪些适合的场景

    2024-01-30 19:12:01       51 阅读

  18. 阿里云云上微服务 EDAS接入使用以及注意事项

    2024-01-30 19:12:01       49 阅读

  21. mysql8.0-cnf文件

    2024-01-30 19:12:01       44 阅读

  23. uni-app vite+ts+vue3模式 集成微信云开发

    2024-01-30 19:12:01       63 阅读

  26. OpenCV解释

    2024-01-30 19:12:01       57 阅读