首页
 

通知公告

插入排序详解(C语言)

来源:欧亿体育点击:时间:2024-01-12 16:02

前言
插入排序是一种简单直观的排序算法,在小规模数据排序或部分有序的情况下插入排序的表现十分良好,今天我将带大家学习插入排序的使用。let’s go ! ! !

插入排序

插入排序的基本思想是将待排序的序列分为已排序和未排序两部分。初始时,将第一个元素视为已排序序列,剩下的元素视为未排序部分。然后逐个将未排序部分的元素插入到已排序序列的正确位置,直到所有元素都被插入到已排序序列中。
举个例子:
这是一个数组,我们要对其从小到大排序。
1 6 8 9 5 2 3
根据刚才的思路,我们将1认为是已排序部分,其他的为待排序部分,我们要逐个的将待排序部分的元素插入到已排序部分,首先我们把6插在1的后面,因为,6 > 1,现在6就算是以排序部分,之后的8和9也依次加到后面,现在的已排序部分为1689,我们需要把5插入其中,首先5和9对比,5 < 9,再让5和8对比,5 < 8,再让5和6对比,5 < 6,再让5和1对比,5 > 1,所以5需要插在1和6之间,剩下的2和3也是同理,插入完即可得到目标序列。
下面我们来用代码实现:

#include
int main()
{
	int arr[6] = { 1,1,4,5,1,4 };//创建数组
	for (int i = 1; i < 6; i++)
	{
		int end = i;//记录当前位置
		while (end)
		{
			if (arr[end - 1] > arr[end])//交换位置
			{
				int tem = arr[end];
				arr[end] = arr[end - 1];
				arr[end-1] = tem;
				end--;
			}
			else//已经插入退出循环
			{
				break;
			}
		}
	}
	return 0;
}

优化
我们会发现在已排序部分是单调的,那么我们是不是就可以使用二分法呢?使用二分法可以大大加快我们插入的效率。当我们通过二分法找到需要插入的位置后,我们要让这个位置到记录的位置这个区间的元素整体后移一格,然后插入这个数字,例如:
1 6 8 9 5
我们通过二分查找找到5要放在1和6中间,那么我们要让6-9后移一格1 6 8 9然后将5插入空处。
代码如下:

#include
int efcz(int* arr, int right)//二分查找函数
{
	int end = right + 1;//目标数下标
	int left = 0;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (arr[mid] >= arr[end])
		{
			right = mid - 1;
		}
		else
			left = mid + 1;
	}
	return left;
}
int main()
{
	int arr[6] = { 1,3,4,5,6,2 };//创建数组
	for (int i = 1; i < 6; i++)
	{
		int right = i-1;//右边界
		int ret = efcz(arr, right);//二分查找插入位置
		int tem = arr[i];//临时变量
		for (int j = right; j >= ret; j--)//数组从ret到rihgt整体后移一格
		{
			arr[j + 1] = arr[j];
		}
		arr[ret] = tem;//插入
	}
	return 0;
}

结尾

看到这里的小伙伴们想必都已经掌握了插入排序的使用方法,如果觉得博主讲的不错的话,能不能给博主一个免费的关注,点赞,收藏支持一下呢?博主将持续分享更多知识,关注博主不迷路哦~,我们下期再见!
(对了,今天是圣诞节,小伙伴们圣诞节快乐!)