排序算法——插入排序

一、插入排序算法的思想

     

    插入排序算法的基本思想如下：

    将n个元素的数列分为已有序和无序两个部分，如下所示：

　　{，{a2，a3，a4，…,an}}

　　{{a1(1)，a2(1)}，{a3(1)，a4(1) …,an(1)}}

　　…

　　{{a1(n-1)，a2(n-1) ，…}, {an(n-1)}}

　　每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。

二、插入排序算法的描述

   具体算法描述如下：

　　1、从第一个元素开始，该元素可以认为已经被排序

　　2、取出下一个元素，在已经排序的元素序列中从后向前扫描

　　3、如果该元素（已排序）大于新元素，将该元素移到下一位置

　　4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

　　5、将新元素插入到下一位置中

　　6、重复步骤2

三、C代码实现

#include "stdio.h"
/*
* 函数：swap(int *a,int *b)
* 功能：进行两个数的交换
*/
void swap(int *a,int *b)
{
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}
/*
* 函数：insert_sort(int *array, int n)
* 功能：插入排序
* 参数：n为数组元素的个数
*/
void insert_sort(int array[],int n)
{
    int i,j;
    int temp;
    for(i=1;i<n;i++)
    {
        temp=array[i];
        for(j=i;j>0 && temp<array[j-1];j--)
        {
            array[j]=array[j-1];
        }
        array[j]=temp;
    }
}

int main(int argc,char *argv[])
{
    int array[]={3,8,3,7,1,2,5,6,4,90};
    insert_sort(array,10);
    for(int i=0;i<10;i++)
    {
        printf("%d ",array[i]);
    }
    printf("\n");
    return 0;
}

四、插入排序算法的时间复杂度

   

   插入排序的时间复杂度为O(n^2)，是稳定的排序算法，适用于数量较少的排序。