大家好，又见面了，我是全栈君。
插入排序 – 算法
1、将排序部分分成两部分
2、每次从后面部分取最前面的数插入到前面部分的适当位置
该处提供两个插入排序版本号，指定间隔插入与插入排序。后面对指定间隔排序提到Shell排序中的n/2间隔与Sedgewick间隔
比如：
排序前：92 77 67 8 6 84 55 85 43 67
[77 92] 67 8 6 8455 85 43 67 将77插入92前
[67 77 92] 8 6 8455 85 43 67 将67插入77前
[8 67 77 92] 6 8455 85 43 67 将8插入67前
[6 8 67 77 92] 8455 85 43 67 将6插入8前
[6 8 67 77 84 92]55 85 43 67 将84插入92前
[6 8 55 67 77 8492] 85 43 67 将55插入67前
[6 8 55 67 77 84 8592] 43 67 ……
[6 8 43 55 67 77 8485 92] 67 ……
[6 8 43 55 67 67 7784 85 92] ……
// 插入排序
int InsertionSort(int a[],int lens)
{
int k;
int tmp;
for(int i=1;i<lens;i++)
{
int j=i-1;
//取出待插数据
tmp = a[i];
// 遍历前面已排好序的序列。找插入位置
// 在i之前查找需待插入数据a[i]的位置k
for(k=j;k>=0;k--)
{
if(tmp<a[k]) a[k+1]=a[k];// 后移
else break;//找到位置
}
// 找到位置。插入指定值
if(i!=(k+1))a[k+1]=tmp;
}
return 0;
}
// 插入排序 - 使用指定间隔的
int InsertionSortWithGap(int a[],int lens,int gap)
{
int k,tmp;
// 控制插入层
for(int m=0;m<gap;m++)
{
for(int i=gap+m;i<lens;i+=gap)
{
int j=i-gap;
tmp=a[i];
for(k=j;k>=0;k-=gap)
{
if(tmp<a[k]) a[k+gap]=a[k];
else break;
}
if(i!=(k+gap))a[k+gap]=tmp;
}
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115563.html原文链接：https://javaforall.net
