112.【C语言】数据结构之排序(详解插入排序)
目录
1.排序定义
使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作
2.插入排序
"插入"的含义
例如对于一个升序数列:3,4,5,11;现在要求插入7使得数列还能满足升序
显然改动后的数列应该是3,4,5,7,11
算法:设要插入的数字为k,从数列的最后一个元素开始,依次向前比较,直到满足
时,向原数列插入k
代码
小提示:写排序代码时,先写单趟排序,之后将其嵌入循环内,能较容易写出
函数框架
void InsertSort(int* a, int n)
{
}函数设计思路
设tmp为要插入的数字,end为有序数组的最后一个元素的下标,n为无序数组元素的个数,a为数组指针,将tmp插入到[0,end]的区间中,构成有序数列
以升序为例,分析插入的三种可能
①tmp大于所有已经排序的数
②tmp大小介于已经排序的数之间
③tmp小于所有已经排序的数
①tmp大于所有已经排序的数
例如有序数列int arr[]={1,3,5,8,10,21,37,40},此时arr[end]==40;现插入tmp==50,
第一次循环:tmp>arr[end],直接arr[end+1]=tmp,循环结束
②tmp大小介于已经排序的数之间
例如有序数列int arr[]={1,3,5,8,10,21,37,40},此时arr[end]==40;现插入tmp==22
第一次循环:arr[end]==40,tmp<a[end],于是arr[end+1]=arr[end],end--,准备下一次循环
第二次循环:arr[end]==37,tmp<arr[end],于是arr[end+1]=arr[end],end--,准备下一次循环
第三次循环:arr[end]==21,tmp>arr[end],满足条件,arr[end+1]=tmp,循环结束
③tmp小于所有已经排序的数
例如有序数列int arr[]={1,3,5,8,10,21,37,40},此时arr[end]==40;现插入tmp==0
省略前几次循环,第?循环,arr[end]==1,tmp<arr[end],于是arr[end+1]=arr[end],end--,准备下一次循环
如果进行了下次循环,end==-1,会造成越界访问,此时应该立即退出循环!执行arr[end+1]=tmp
显然退出循环有两种情况:1.end<0,即end==-1时 2.tmp>arr[end]
因此将所有可能的情况讨论全,循环退出的条件才能写全
单趟排序代码
int end;
int tmp;
while (end >= 0)
{
if (tmp > arr[end])
{
arr[end + 1] = arr[end];
end--;
}
else
{
arr[end + 1] = tmp;
break;
}
}
if (end == -1)
{
arr[end + 1] = tmp;
}上面这样写略显麻烦,无论满足什么条件退出循环,最后都执行arr[end + 1] = tmp;
优化后
while (end >= 0)
{
if (tmp > arr[end])
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;将单趟排序代码嵌入到循环中
main.c写入
int main()
{
int arr[] = { 1,6,2,4,7,3,9,0,-1,5 };
printf("排序前:");
PrintSort(arr, sizeof(arr) / sizeof(arr[0]));
InsertSort(arr,sizeof(arr)/sizeof(arr[0]));
printf("排序后:");
PrintSort(arr, sizeof(arr) / sizeof(arr[0]));
return 0;
错误代码
void InsertSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
int end = i;
int tmp = arr[i + 1];
while (end >= 0)
{
if (tmp < arr[end])
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}
问题出在越界访问,当i==n-1时,执行int tmp = arr[i + 1];就越界了(arr的最后一个元素是arr[n-1])!!
两种改法
改法1:改for的循环条件
for (int i = 0; i < n-1; i++)改法2:改tmp和end赋的初始值
for (int i = 0; i < n; i++)
{
int end = i-1;
int tmp = arr[i];
//省略......
}备注:循环的一开始,无序数组的首元素可构成一个有序数组,后面的数依次插入有序数组
运行结果
时间复杂度
最坏情况,每次内循环结束条件都为end==-1,时间复杂度
最好情况:提供的数组恰好是有序的,时间复杂度
结论:从时间复杂度来看,数组越接近有序,插入排序的时间复杂度越低,而希尔排序就是基于这个结论设计的,有关希尔排序的内容参见下篇文章
原文地址：https://blog.csdn.net/2401_85828611/article/details/144441139
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！