【C语言篇】简单选择排序法

勤奋不是嘴上说说而已,而是实际的行动,在勤奋的苦度中持之以恒,永不退却。业精于勤,荒于嬉;行成于思,毁于随。在人生的仕途上,我们毫不迟疑地选择勤奋,她是几乎于世界上一切成就的催产婆。只要我们拥着勤奋去思考,拥着勤奋的手去耕耘,用抱勤奋的心去对待工作,浪迹红尘而坚韧不拔,那么,我们的生命就会绽放火花,让人生的时光更加的闪亮而精彩。

导读:本篇文章讲解 【C语言篇】简单选择排序法,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

🎐上篇文章,我们详细讲解了冒泡排序法,这篇文章,我们会对冒泡排序法进行深一步的分析、反思,引出一种比冒泡排序法更优的解法——简单排序法。🌠


💧引入–(冒泡排序再思考)

其实通过我们最先分析冒泡排序法的时候,也就是优化之前,会发现,这个代码的效率是很低的。这里再次引用一下:

#include<stdio.h>
#define N 10
int main()
{
	int arr[N] = {0};//创建一个整形数组
	int temp = 0;//创建一个变量,作用是在交换元素的过程中起到“空瓶”作用
	int i = 0;
	for (i = 0; i < N; i++)//for循环输入10个数字
	{
		scanf("%d", &arr[i]);
	}

	//循环控制变量i、j
	int j = 0;
	for (i = 0; i < N-1; i++)//外层循环:控制趟数
	{
		for (j = 0; j < N - 1 - i; j++)//这里j的作用有2个,第二个是充当元素下标(所以从0开始的好处)
		{
			if (arr[j] > arr[j + 1])//交换
			{
				temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
			}
		}
	}
	
	for ( i = 0; i < N ; i++)//输出
	{
		printf("%d\n", arr[i]);
	}


	return 0;

}

为什么这么说呢:原因有1,如果数组中元素在趟数执行完之前已经有序,但是剩余的趟数还是会照例执行,其实这是没有必要的(虽然后面我们优化了,但是这里我们仅对上面这个代码讨论),我们看,一次完整的大循环走下来,总共交换的次数最多会执行(N-1)+(N-2)+(N-3)+…1.这是一个等差数列,结果为N(N-1)/2,当N很大时,这个结果也会很大:
在这里插入图片描述

而每一次交换需要执行三行代码,所以时间效率无疑很低。
所以关键点就是:如何通过减少交换的次数,来提高代码的效率呢?
这就引出了第二种排序方法:简单选择排序法

🎄简单排序法–思路

根据上文,我们发现冒泡排序法交换次数太多。接下来,我们会逐步分析,如何实现选择排序:
step1思考: 冒泡排序中,每一趟都要比较,并且一旦if成立,则实现交换,这种不断比较、交换的目的是什么?是为了最大的那个数落在合适的位置对吧?当然,比较肯定是少不了的,因为只有通过比较,才能找出此趟中的最大数。那么交换次数能否减少呢?
step2如何减少:其实,每一趟,我们只希望此趟的最大数落在正确位置,那么能不能通过比较,找到这个最大数(假设不在正确位置),然后让这个最大数直接和正确位置(此趟中最大数被排好后的那个位置,该位置也放了我们的假设最大值)的那个数进行交换(如果正确位置本来就储放了此趟中最大数,则不交换)。也直接实现了:一趟排好一个数字的目的。并且大大减少了交换次数。因为一趟中最多只交换一次。(先选择,找出最大数,再交换)
step3:如何实现: 思路有了,那么代码如何实现呢。
(这里我们是按照先找最小值,再进行交换,讲解。本质和先找最大值,再交换是一样的)
首先肯定是需要两层循环,外层控制趟数,内层控制比较次数。
step①:第一趟:
假设第一个数(角标:0)就为最小值,角标记为k,将它和它后面的数进行比较,如果后面的数比它还小,那么k此时就与该数角标交换(直接k=角标,赋值即可)当然,这里肯定不是通过交换的数据,而是通过角标来实现,待会具体看。
step②:一趟内循环下来后,该角标代表的就是该组数字中最小数的角标。知道了角标,其实就是找到了这个最小数。
step③:直接将该角标和初始角标0进行交换,那么最小值就排在第一个,也就是正确位置,这样一趟下来,就有一个数字被排好。
第二趟,因为第一个数字已经排好了,所以假设第二个数字最小(k=1)…<步骤同上>
由此,每趟排好1个数,共需要9趟。
具体看如下图解和代码:

🎀图解

在这里插入图片描述

🙇‍♀️代码实现

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#define N 10
int main()
{
	int arr[N] = { 0 };

	int i = 0;
	int j = 0;
	int temp = 0;
	for (i = 0; i < N; i++)
	{
		scanf("%d", &arr[i]);
	}
	for (i = 0; i < N - 1; i++)
	{
		int k = i;
		int Min = arr[k];//假设角标为k的元素为最小
		for (j = k+1; j < N ; j++)//注意,这里j初始化为i,因为按照这个程序进行,每趟中数字是从小到大排列
		{
			if (arr[k] >arr[j])//
			{
				k = j;//设置角标的好处:直接进行赋值,无需进行元素交换
			}
		}//一趟内层循环下来,虽然最小数没有处在正确位置(因为没有元素交换位置呀)
		//但是我们找到了这组数字中最小数的角标,为k
		if (k != i)//说明最小值并不是我们初始设的那个,说明找到了此趟最小值,所以直接把找到的最小值和假设的最小值交换位置即可
		{
			temp = arr[i];
			arr[i] = arr[k];
			arr[k] = temp;
		}
	}
	for (i = 0; i < N ; i++)
	{
		printf("%d\n", arr[i]);
	}

	return 0;

}

在这里插入图片描述


最后,希望此篇文章对你有帮助。可能有不正确、不准确的地方,还请大家多多指出。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/142480.html

(0)

相关推荐

发表回复

登录后才能评论
半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!