选择排序【详解】

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

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;
}

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