免费网站制作器,微信小店,国内最厉害的公关团队,客户网站 备案前言 插入排序是一种简单直观的排序算法#xff0c;在小规模数据排序或部分有序的情况下插入排序的表现十分良好#xff0c;今天我将带大家学习插入排序的使用。let’s go ! ! !
插入排序
插入排序的基本思想是将待排序的序列分为已排序和未排序两部分。初始时#xff0c…前言 插入排序是一种简单直观的排序算法在小规模数据排序或部分有序的情况下插入排序的表现十分良好今天我将带大家学习插入排序的使用。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也是同理插入完即可得到目标序列。 下面我们来用代码实现
#includestdio.h
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插入空处。 代码如下
#includestdio.h
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;}elseleft 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;
}结尾
看到这里的小伙伴们想必都已经掌握了插入排序的使用方法如果觉得博主讲的不错的话能不能给博主一个免费的关注点赞收藏支持一下呢博主将持续分享更多知识关注博主不迷路哦~我们下期再见 对了今天是圣诞节小伙伴们圣诞节快乐
