欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

插入排序

程序员文章站 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:数组中只有几个元素的位置不确定。

相关标签: 插入排序 排序