插入排序的三种算法C/C++：一、直接插入排序：1、平均时间复杂度为O(n^2)2、最好情况为O(n)3、最坏情况下为O(n^2)4、空间复杂度为O(1)。

算法实现为：

/*
 *直接插入排序
 */

#include
  
   

#define MaxSize 100

/*
 *a为待排序的数组，length为数组长度
 */
void inSort(int a[] , int length) ;

/*
 *进行数组元素的输出
 */
void displayArray(int a[] , int length) ;

void main()
{
    int a[MaxSize] , length , i ;
    printf("Please input the length of the array : \n") ;
    scanf("%d" , &length) ;

    //进行数组元素的接收
    for(i = 0 ; i < length ; i++)
    {
        scanf("%d" , &a[i]) ;
    }

    printf("Before sort... \n") ;
    displayArray(a , length) ;

    inSort(a , length) ;

    printf("After sort... \n") ;
    displayArray(a , length) ;
}

void inSort(int a[] , int length)
{
    //临时储存元素
    int temp ;
    int i , j ;             
    for(i = 1 ; i < length ; i++)
    {
        temp = a[i] ;
        j = i - 1 ;
        while(temp < a[j] && j >= 0)
        {
            a[j + 1] = a[j] ;           
            j-- ;
        }
        a[j + 1] = temp ;
    }
}

void displayArray(int a[] , int length)
{   
    int i ;
    for(i = 0 ; i < length ; i++)
    {
        printf("%4d ", a[i]);
    }
    printf("\n") ;
}
  

二、折半插入排序
1、平均时间复杂度为O(n^2)
2、最好情况为O(nlogn)
3、最坏情况下为O(n^2)
4、空间复杂度为O(1)

算法实现为：

/*
 *折半插入排序
 */

#include
  
   

#define MaxSize 100

/*
 *a为待排序的数组，length为数组长度
 */
void binSort(int a[] , int length) ;

/*
 *进行数组元素的输出
 */
void displayArray(int a[] , int length) ;

void main()
{
    int a[MaxSize] , length , i ;
    printf("Please input the length of the array : \n") ;
    scanf("%d" , &length) ;

    //进行数组元素的接收
    for(i = 0 ; i < length ; i++)
    {
        scanf("%d" , &a[i]) ;
    }

    printf("Before sort... \n") ;
    displayArray(a , length) ;

    binSort(a , length) ;

    printf("After sort... \n") ;
    displayArray(a , length) ;
}

void binSort(int a[] , int length)
{
    int i , j , mid , low , high , temp ;
    for(i = 1 ; i < length ; i ++)
    {
        low = 0 ;
        high = i - 1 ;
        temp = a[i];
        while(low <= high)
        {
            mid = (low + high) / 2 ;
            if(temp < a[mid])
            {
                high = mid - 1 ;
            }else{
                low = mid + 1 ;
            }
        }
        for(j = i - 1 ; j >= low ; j--)
        {
            a[j + 1] = a[j] ;
        }
        a[low] = temp ;
    }   
}

void displayArray(int a[] , int length)
{   
    int i ;
    for(i = 0 ; i < length ; i++)
    {
        printf("%4d ", a[i]);
    }
    printf("\n") ;
}
  

三、希尔排序
1、平均时间复杂度为O(n^1.5)
4、空间复杂度为O(1)

算法实现为：