频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
插入排序的三种算法C/C++
2017-03-13 09:29:00         来源:g15827636417的博客  
收藏   我要投稿

插入排序的三种算法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") ;
}
点击复制链接 与好友分享!回本站首页
上一篇:C++地址传递
下一篇:C++建模实战之高考录取系统(1)
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站