【八大排序(一)】排序还只会用冒泡?进来给我学!网站首页 技术教程

【八大排序(一)】排序还只会用冒泡?进来给我学!

杭电码农-NEO 2024-09-08 00:01:03

简介【八大排序(一)】排序还只会用冒泡?进来给我学!

?博主CSDN主页:杭电码农-NEO?

⏩专栏分类:八大排序专栏⏪

?代码仓库:NEO的学习日记?

?关注我?带你学习排序知识
??

在这里插入图片描述

插入,希尔排序

1. 前言?
2. 插入排序?
3. 选择排序?
4. 算法效率分析?
5. 总结与网站分享?

1. 前言?

博主前段时间接到了专业课老师的任务:
让我设计个排序算法用来给学生成绩排名.
我心里一惊!
这不是为难我这个只会冒泡的大学生嘛
在这里插入图片描述

于是我删掉了王者荣耀,删掉了吃鸡
我奋不顾身,我披星戴月的肝八大排序
终于!我现在学成归来
下面就给大家分享八大排序中的前两个:

插入排序
选择排序

2. 插入排序?

2.1 基本思路?

基本思想:

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

玩斗地主抓牌实际上就是一种插入排序:

在这里插入图片描述

2.2 画图理解?

单趟插入:
比如我们先定义一个有序数组:

int a[100]={2,4,5,10};

我们再把数据3插入到这个数组中:

插入排序

2.3 代码实现?

在我们实际生活中
最常见的就是把一个无序数组变成有序
所以还不能是单纯的插入到有序数组中

这里我们将一个无序数组变为有序
直接在原数组中操作
这里我们定义一个无序数组:

int a[9]={2,9,5,7,4,1,3,8,6}

要想直接在原数组中操作,相当于要进行元素个数这么多次单趟插入,我们定义两个变量,end和x,一个指向第一个元素,一个指向第二个元素,end<x就不移动,end>x就开始往后走

画图:

原数组插入

// 插入排序
void InsertSort(int* a, int n)
{
	assert(a);
	for (int i = 0; i < n - 1; i++)//将一个数组中所有元素升序
	{                              //,这里必须是n-1,不然后面数组会越界
		int end=i;
		int x=a[end+1];//x始终指向end下一个位置的值
		while (end >= 0)//每趟插入最多挪动end-1个数据
		{
			if (a[end] > x)//x前一个数大于x,就将数据往后移一格
			{
				a[end + 1] = a[end];//这里数组的值会往后覆盖
				                    //但是没关系,我们已经将a[end+1]的值保存在x当中了
				end--;
			}
			else
			{
				break;//跳出里面的while循环
			}
		}
		a[end + 1] = x;
	}
}

3. 选择排序?

3.1 基本思想?

基本思想:

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完

不知道你们有没有经历过这种痛:
小学排队的时候老师对我说:
你,最矮!到最前面来排着.

在这里插入图片描述

当然大家可能之前接触过选择排序
但是我分享的选择排序是做了优化的
以前我们是每一趟选一个最大或最小
优化后:一趟选两个,最大的和最小的
分别放在数组的左右端

3.2 画图理解?

我们先定义一个1~9的无序数组:

int a[9]={6,2,5,3,9,4,8,5,1,7}

这里的视频理解中,一趟只选出了一个
我们只要理解这个优化的思路就好了

选择排序

3.3 代码实现?

因为选择排序会用到交换
所以我们直接写一个交换函数

//交换函数
void swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

然后下面是我们的代码版本一:

void SelectSort(int* a, int n)
{
	int begain = 0;
	int end = n - 1;
	while (begain < end)
	{
		int maxi = begain;//初始化最值
		int mini = begain;
		for (int i = begain; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;//记录下标,否则会有数据被覆盖的问题
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		swap(&a[begain], &a[mini]);//将最大最小值交换
		swap(&a[end], &a[maxi]);
		begain++;//数组范围往中间缩小
		end--;
	}
}

3.4 代码优化?

但是这个代码会出现一个问题:当数组中的最大值位于数组的第一个位置时,我们把begin和mini交换后,maxi指向的位置还是第一个元素,也就是最小值mini.再将maxi与end交换,就把最小值换到最后了!我们画图理解一下:

在这里插入图片描述

修改后的版本二

// 选择排序
void SelectSort(int* a, int n)
{
	int begain = 0;
	int end = n - 1;
	while (begain < end)
	{
		int maxi = begain;
		int mini = begain;
		for (int i = begain; i <=end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;//记录下标,否则会有数据被覆盖的问题
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		swap(&a[begain], &a[mini]);
		if (maxi == begain)//当最大值为begain时,交换最小值和开头元素后,maxi指向的值不再是最大值了.
		{
			maxi = mini;
		}
		swap(&a[end], &a[maxi]);
		begain++;
		end--;
	}
}