【排序算法】C语言实现选择排序与冒泡排序

文章目录

• 🚀前言
• 🚀冒泡排序
• • ✈️冒泡排序的逻辑
  • ✈️冒泡排序coding
• 🚀选择排序
• • ✈️选择排序的逻辑
  • ✈️选择排序coding

🚀前言

这里是阿辉算法与数据结构专栏的第一篇文章，咱们就从排序算法开始讲起，排序算法有很多大致分为两类：基于比较的排序和非比较的排序

• 基于比较的排序：冒泡、选择、插入、希尔、堆、归并、随机快排
• 非比较的排序：桶排序

以上的排序算法阿辉都会讲到，今天阿辉主要讲一下选择排序和冒泡排序。
铁子们，进入咱们今天的学习吧！！!

🚀冒泡排序

铁子们对于冒泡排序一定是有很多理解了，这里阿辉就简单讲一下😆

✈️冒泡排序的逻辑

逻辑很简单，就是前一个数据与后一个数据进行比较，前一个数据更大就交换，相等或小于不进行任何操作，然后重复操作，一趟下来就能把最大的数据放到末尾位置然后重复上述操作如下图👇

可以看出，对于上面具有5个元素的无序数组，我们通过4趟的冒泡后就将其变为有序数组，每一趟冒泡后都可以使剩下的数据中最大的数据沉底

我们看一下动图演示：

✈️冒泡排序coding

其实很多情况下我们对于逻辑掌握的很快，关键是把逻辑抽象成代码的过程很麻烦，各种边界要考虑到位，对于一个算法首先要把具体例子搞明白再去写，否则很容易脑子一摊浆糊

关于冒泡排序，其实我们就关注两件事
1.需要几趟冒泡
对于一个有n个元素的数组，我们需要 n-1 趟冒泡
很好理解，比如：3 2 1这三个数
一趟冒泡会把3移到末尾变成 2 1 3
第二趟就会把2移到3的前一位变成 1 2 3这时数组已经有序了
2.一趟冒泡进行几次比较
对于有n个元素的数组来说：
第一次冒泡，范围是下标0 ~ n-1，就比较n-1次
第二次冒泡，范围是下标0 ~ n-2，就比较n-2次
第三次冒泡，范围是下标0 ~ n-3，就比较n-3次
 … … … …

有了上面的分析，我们很容易想到可以用一个循环控制趟数，再用一个循环控制比较的次数就可以写出下面经典的冒泡排序

//交换方法
void swap(int a[], int x, int y)
{
	int tmp = a[x];
	a[x] = a[y];
	a[y] = tmp;
}
//经典冒泡排序
void BubbleSort(int a[], int sz)//sz表示传入数组的大小
{
	//end表示需要进行几趟冒泡
	for (int end = sz - 1; end > 0;end--)
	{
		//同时end从sz-1开始，作为比较次数限定第二个for循环的范围
		//每一趟冒泡都是从下标 0和1  1和2  2和3 ……比较
		//second代表每次比较的第二个数，也就是0和1的1,1和2的2
		//所以second从1开始
		for (int second = 1; second <= end; second++)
		{
			//当第一个数大于第二个数就交换
			if (a[second - 1] > a[second])
			{
				//交换函数，传入数组名和需要交换的两个数的下标
				swap(a, second, second - 1);
			}
		}
	}
}

为什么说上述是经典的冒泡排序，因为他有一个缺陷对于长度一样的数组不管其是否有序都会进行固定次数的比较，这样的话效率很差，所以就有冒泡排序的改良版

void BubbleSort(int a[], int sz)
{
	for (int end = sz - 1; end > 0;end--)
	{
		int flag = 0;//增加一个flag变量，判断是否数组已有序
		for (int second = 1; second <= end; second++)
		{
			if (a[second - 1] > a[second])
			{
				swap(a, second, second - 1);
				flag = 1;
			}
		}
		//flag为0说明没进行交换，没交换就说明每个数的前一个数不大于它
		//说明数组已有序跳出循环
		if (flag == 0)
			break;
	}
}

🚀选择排序

选择排序也不难，阿辉来给铁子们稍微讲一下😆

✈️选择排序的逻辑

逻辑就是：对于一个有n个元素的数组，首先在下标为0 ~ n-1的范围内找到最小的数与下标为0的数交换，染后在下标1 ~ n-1范围找到最小的数与下标为1的数字交换，然后按照上述依次进行，直到排好序
选择过程：

我们来看一下动图展示：

✈️选择排序coding

同样选择排序我们也只关心两件事
1.进行几次找最小值
这与冒泡类似，一个有n个元素的数组进行，n-1次选择
2.每次寻找最小值的范围
对于有n个元素的数组来说：
对于有n个元素的数组来说：
第一次选择，范围是下标0 ~ n-1
第二次选择，范围是下标1 ~ n-1
第三次选择，范围是下标2 ~ n-1
…………

有了上面的分析，我们很容易想到可以用一个循环控制找最小值的次数，再用一个循环遍历要找的最小值的范围

//交换方法
void swap(int a[], int x, int y)
{
	int tmp = a[x];
	a[x] = a[y];
	a[y] = tmp;
}
//选择排序
void SelectSort(int a[],int sz)//sz数组元素个数
{
	int first = 0;//控制找最小值，并且是每一次要找最小值的范围的第一个元素的下标
	for (first = 0; first < sz - 1; first++)
	{
		int end = sz - 1;//控制遍历最小值的范围，并且从后遍历数组
		int min = first;//min记录最小值的下标
		while(end > first)
		{
			//如果以end为下标的元素比以min为下标的元素小，min就记录该数的下标
			min = a[min] > a[end] ? end : min;
			end--;
		}
		swap(a, first, min);//每次找到的最小数与开始位置交换
	}
}

以上GIF动图均出自这篇文章
如果觉得文章对你有帮助的话，还请点赞，关注，收藏支持博主，如有不足还请指点，博主及时改正，感谢大家支持！！！