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

插入排序的三种算法C/C++

程序员文章站 2022-03-26 09:32:01
插入排序的三种算法c/c++:一、直接插入排序:1、平均时间复杂度为o(n^2)2、最好情况为o(n)3、最坏情况下为o(n^2)4、空间复杂度为o(1)。 算法实现为: /* *直接插入排...

插入排序的三种算法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)

算法实现为:

/*
 *希尔排序
 */

#include

#define maxsize 100

/*
 *进行希尔排序
 *a为待排序数组,lengh为数组长度,delta为增量数组,length1为增量数组的长度
 */
void shellsort(int a[] , int lengh , int delta[] , int length1) ;

/*
 *进行一趟希尔排序
 */
void shellinsert(int a[] , int length , int delta) ;

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

void main()
{
    int a[maxsize] , length , i ;
    int delta[maxsize] , length1 ;

    printf("please input the length of the array : ") ;
    scanf("%d" , &length) ;

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

    //进行增量数组的接收
    printf("please input the delta's length : ") ;
    scanf("%d" , &length1) ;

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

    printf("before sort... \n") ;
    displayarray(a , length) ;

    shellsort(a , length , delta , length1) ;

    printf("after sort... \n") ;
    displayarray(a , length) ;
}

void shellsort(int a[] , int length , int delta[] , int length1)
{
    int i ;
    for(i = length1 - 1 ; i >= 0 ; i--)
    {
        shellinsert(a , length , delta[i]) ;
    }
}

void shellinsert(int a[] , int length , int delta)
{
    int i , j , temp ;
    for(i = delta ; i < length ; i++)
    {
        temp = a[i] ;
        j = i - delta ;
        while(temp < a[j] && j >= 0)
        {
            a[j + delta] = a[j] ;
            j -= delta ;
        }
        a[j + delta] = temp ;
    }
}   

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