当前位置：首页 > news >正文

摄影图片网站百度手机助手app下载安装

news 2025/8/9 5:32:34

摄影图片网站,百度手机助手app下载安装,江西网站开发费用,现在推广平台有哪些前言插入排序是一种简单直观的排序算法，在小规模数据排序或部分有序的情况下插入排序的表现十分良好，今天我将带大家学习插入排序的使用。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也是同理，插入完即可得到目标序列。
下面我们来用代码实现：

#include<stdio.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插入空处。
代码如下：

#include<stdio.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;
}