在这里插入图片描述

本期介绍
主要介绍:排序中的选择排序。



1. 前言

  相信只要接触过C语言的同学都或多或少了解排序问题,其中最基本,且最为人所熟知的排序是:选择排序。下面我会带着大家重新把这种排序方法走一遍,使你能够透彻的理解这两种算法的原理,能把它们清晰的区分开,并且分别实现这两种排序的算法优化。


2. 选择排序

在这里插入图片描述

  选择排序的原理:每趟都从剩余待排序的数组元素种选出最小(或最大)的一个元素,交换存放在这一趟序列的起始位置。选择排序的趟数是由元素个数来决定的,若现在有n个元素要对其进行排序,那只需要进行n-1趟就好了。实现代码如下所示:

//实现选择排序:每次遍历找出数组中最大或最小的值

#include<stdio.h>

void print(int arr[], int num)
{
	int i = 0;
	for (i = 0; i < num; i++)
	{
		printf("%d ", arr[i]);
	}
}

void select_sort(int arr[], int num)
{
	//趟数
	int i = 0;
	for (i = 0; i < num - 1; i++)
	{
		//每趟找到最大值的下标
		int j = 0;
		int Max = i;
		int tmp = 0;
		for (j = i + 1; j < num; j++)
		{
			if (arr[Max] < arr[j])
			{
				Max = j;
			}
		}
		//将最大值放入最前面
		tmp = arr[i];
		arr[i] = arr[Max];
		arr[Max] = tmp;
	}
}

int main()
{
	int arr[] = { 0,1,2,3,4,5,6,7,8,9 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	select_sort(arr, sz);
	print(arr, sz);
	return 0;
}

在这里插入图片描述


3. 优化选择排序

  选择排序的优化思路一般是在一趟遍历中,同时找出最大值与最小值,放到数组两端,这样就能将遍历的趟数减少一半。过程如下:
在这里插入图片描述

   这样每次找出最大值与最小值放到数组两端后,left和right会靠的越来越近。如果还像上边那样执行(n-1)趟的话left和right必然会交错,但这里完全没有必要执行(n-1)趟,因为把left<right的所有情况走完数组就已经有序排列了,完全没有必要把后面left>=right的情况再走一遍。程序如下:

#include<stdio.h>

void Swap(int* arr, int x, int y)
{
	int tmp = arr[x];
	arr[x] = arr[y];
	arr[y] = tmp;
}

void sel_sort(int* arr, int num)
{
	
	int left = 0;
	int right = num - 1;
	while (left < right)
	{
		//先假设最左侧元素的下标未为最小元素的下标,最右侧元素的下标为最大元素的下标。
		int min = left;
		int max = right;
		int i = 0;
		for (i = left; i <= right; i++)
		{
			if (arr[i] < arr[min])
			{
				min = i;
			}
			if (arr[i] > arr[max])
			{
				max = i;
			}
		}
		//最大值放在最右端
		Swap(arr, max, right);
		//由于上一步把下标(right)和(max)上的数据进行了交换
		//所以得考虑最小值(arr[min])在位置(right)的情况,即:此时的 min = right;
		if (min == right)
		{
			min = max;
		}
		//最小值放在最左端
		Swap(arr, min, left);
		//每趟遍历,元素总个数减少2,左右端各减少1,left和right索引分别向内移动1
		left++;
		right--;
	}
}

int main()
{
	int i = 0;
	int arr[] = { 3,5,9,2,4,7 };
	int sz = sizeof(arr) / sizeof(arr[0]);//计算数组元素个数
	sel_sort(arr, sz);//选择排序
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

在这里插入图片描述


在这里插入图片描述

这份博客如果对你有帮助,给博主一个免费的点赞以示鼓励欢迎各位点赞评论收藏⭐️,谢谢!!!
如果有什么疑问或不同的见解,欢迎评论区留言欧。

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部