插入排序与希尔排序--C语言实现

/* insert sort and shell sort
 * [e-mail]
 */

#include
#include

#include "fatal.h"

typedef int element_type;

/* 插入排序
 * 进行第N趟排序时，第N-1趟已经排好序了
 */
static void
insert_sort( element_type a[], int n )
{
    int j, p;
    element_type tmp;
    
    for ( p = 1; p < n; p++ ){
        tmp = a[p];
        for ( j = p; (j > 0) && (a[j - 1] > tmp); j-- ){
            a[j] = a[j - 1];
        } 
        a[j] = tmp;
    }
}

/* 希尔排序 */
static void
shell_sort( element_type a[], int n )
{
    int p, j, increment;
    element_type tmp;

    /* 使用shell增量 */
    for ( increment = n / 2; increment > 0; increment /= 2 ){
        /* 对每个增量使用插入排序 */
        for ( p = increment; p < n; p++ ){
            tmp = a[ p ];
            /*for ( j = p; (j >= increment) && ( a[ j - increment] > tmp );
                j -= increment ){
                a[ j ] = a[j - increment];
            }*/
            for ( j = p; j >= increment; j -= increment )
                if ( a[ j - increment] > tmp )
                    a[ j ] = a[j - increment];
                else
                    break;
            a[ j ] = tmp;
        }
    }
}

/************    The next is test functions    ***************/
//#define get_array_size(array)    ( sizeof(array) / sizeof(array[0]) )

#define D_COUNT    (0x10000)

/* equal return 1, else return 0 */
static int
my_memcmp( element_type *mem1, element_type *mem2, int count )
{

    int i;

    for ( i = 0; i < count; i++ )
        if ( *mem1++ != *mem2++ )
            return 0;

    return 1;
}

void
test_sort( void )
{
    int i;
    element_type *data4insert,*data4shell;

    data4insert = malloc( D_COUNT * sizeof(element_type) );
    data4shell = malloc( D_COUNT * sizeof(element_type) );
    if ( !data4insert || !data4shell )
        Error("Out of space!");

    for ( i = 0; i < D_COUNT; i++ ){
        /* rand()是个“伪”随机数函数*/
        data4shell[i] = data4insert[i] = rand();
        //data4shell[i] = rand();
    }

    /* 通过观测执行时间可以明显看出这两个排序算法时间性能相差甚远 */
    insert_sort( data4insert, D_COUNT );
    shell_sort( data4shell, D_COUNT );

    i = my_memcmp( data4insert, data4shell, D_COUNT );
    if ( i )
        printf("\t------ sort result equal. ------\n");
    else
        printf("\t------ sort result not equal. ------\n");
    free( data4insert );
    free( data4shell );
   
    return;
}