1.插入排序—直接插入排序(Straight Insertion Sort)
基本思想:
将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序列有序为止。
要点:设立哨兵,作为临时存储和判断数组边界之用。
直接插入排序示例:
![456a32b5b6345e1aef59ecba02138d15.png](https://img-blog.csdnimg.cn/img_convert/456a32b5b6345e1aef59ecba02138d15.png)
如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。
代码如下:
#include<stdio.h>
void print(int data[],int n) //打印结果的函数
{
int i;
for(i=0;i<n;i++)
{
printf("%d ",data[i]);
}
printf("\n");
}
void insertSort( int data[] ,int n ) //排序函数
{
/*----begin------*/
int i,j;
int t;
for(i=1;i<n;i++)
{
t = data[i];
j = i -1;
while(j>=0 && data[j]>t)
{
data[j+1]=data[j];
j--;
}
data[j+1] = t;
print(data,n); //显示排序的过程
}
/*-----end------*/
}
int main()
{
int data[8]={49,38,65,97,76,13,27,49};
insertSort(data ,8);
return 0;
}
运行结果:
38 49 65 97 76 13 27 49
38 49 65 97 76 13 27 49
38 49 65 97 76 13 27 49
38 49 65 76 97 13 27 49
13 38 49 65 76 97 27 49
13 27 38 49 65 76 97 49
13 27 38 49 49 65 76 97
--------------------------------
Process exited after 0.02938 seconds with return value 0
请按任意键继续. . .
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)