插入排序
程序员文章站
2022-03-21 22:12:58
...
插入排序:
步骤:
1:从第一个元素开始,该元素可以认为已经被排序
2:取出下一个元素,在已经排序的元素序列中从后向前扫描
3:如果该元素(已排序)大于新元素,将该元素移到下一位置(即前面)
4:重复步骤三,直到找到已排序的元素小于或等于新元素的位置
5:将新元素插入到该位置后
6:重复步骤二到五
时间复杂度: O(n*n)
空间复杂度: O(1)
代码:
#include <stdio.h>
int main(void)
{
int a[6]={2,5,3,1,6,4};
int i,j;
for(i=0;i<5;i++) //i<5,循环需要运行五次的原因是第一个元素可以被认为已经被排序
{
for(j=i+1;j>0;j--)
{
if(a[j-1]>a[j]) //他需要一直和前面的元素比较
{
int t;
t=a[j],a[j]=a[j-1],a[j-1]=t;
}
}
}
printf("The sort array is:\n");
for(i=0;i<6;i++)
{
printf("%d ",a[i]);
}
return 0;
}
//代码后面的很多注释不想写,因为和步骤重复,相信你如果不懂代码可以反复阅读算法的步骤,很详细,直到你可以读懂code
特点:
极适用于部分有序数组。
部分有序数组定义:
1:数组中每个元素距离他的最终位置都不远;
2:一个有序的大数组接一个小数组;
3:数组中只有几个元素的位置不确定。