算法2.1--算法2.4 基于相邻元比较的排序算法

这几个排序算法都是基于相邻元素的比较的，而且都是O(N^2)阶的算法。

在最坏情况下，基于相邻元素的比较及交换的算法，至少需要N(N-1)/2次比较，平均情况下至少需要N(N-1)/4次比较。

 

算法2.1 SelectSort,参见

http://blog.chinaunix.net/u/12325/showart.php?id=316152

 

算法2.2 InsertSort,参见

http://blog.chinaunix.net/u/12325/showart.php?id=316175

 

算法2.3-2.4 起泡排序(BubbleSort)

基本的想法是不断地交换相邻的两个逆序的元素，bubble_sort2()比bubble_sort()好一点就是设置了一个flag来记录本次扫描是否有交换，如果没有的话，证明已经是有序的了，便可中止。

这样的算法是稳定的、原址排序算法。

 

#include
#include
#include
#include

#define MAX_LENGTH 100

/*Show usage*/
void usage(char * prog)
{
        printf("%s Usage:\n", prog);
        printf("%s \n", prog);
}

/*Generate and initialize the list*/
int * generate_list(int count)
{

        int i;
        int * list;
        list = (int *)malloc(count*sizeof(int));
        if(list == NULL)
        {
                perror("malloc");
                return NULL;
        }

        /*Initialize the list with integers less than 100*/
        srandom((unsigned int)time(NULL));
        for (i  = 0; i < count ; i ++)
                list[i] = random()%100;

        return list;
}

/*Show the list*/
void show_list(int * list, int length)
{
        int i;
        for(i = 0; i < length; i ++)
                printf("%d      ", list[i]);

        printf("\n");
}

/*algorithm*/
void bubble_sort(int * list, int length)
{
        int i,j, temp;
        for(i = 0; i < length -1; i ++)
        {
                for(j = length -1; j > i; j --)
                {
                        if(list[j] < list[j-1])
                        {
                                temp = list[j];
                                list[j] = list[j-1];
                                list[j-1] = temp;
                        }
                }
        }
        printf("Ordered list:\n");
        show_list(list, length);
        return;
}

/*algorithm*/
void bubble_sort2(int *list, int length)
{
        int flag = 1;
        int i, j, temp;
        for(i = 0; (i < length -1)&&flag; i ++)
        {
                flag = 0;
                for(j = length -1; j > i; j -- )
                        if(list[j] < list[j-1])
                        {
                                flag = 1;
                                temp = list[j];
                                list[j] = list[j-1];
                                list[j-1] = temp;
                        }
        }
        printf("Ordered list 2:\n");
        show_list(list, length);
        return;
}

int main(int argc, char * argv[])
{
        int length;
        int * list = NULL;
        struct timeval tpstart,tpend;
        float timeuse;

        /*Deal with the arguments*/
        if(argc != 2)
        {
                usage(argv[0]);
                exit(127);
        }

        length = atoi(argv[1]);
        if(!length || length > MAX_LENGTH)
        {
                usage(argv[0]);
                exit(129);
        }

        list = generate_list(length);
        if(list == NULL)
                exit(128);
        else
        {
                printf("Soruce list:\n");
                show_list(list, length);

                gettimeofday(&tpstart,NULL);
                bubble_sort(list, length);
                gettimeofday(&tpend,NULL);
                timeuse=1000000*(tpend.tv_sec-tpstart.tv_sec)+ tpend.tv_usec-tpstart.tv_usec;
                timeuse/=1000;
                printf("time used: %f msec\n", timeuse);

                gettimeofday(&tpstart,NULL);
                bubble_sort2(list, length);
                gettimeofday(&tpend,NULL);
                timeuse=1000000*(tpend.tv_sec-tpstart.tv_sec)+ tpend.tv_usec-tpstart.tv_usec;
                timeuse/=1000;
                printf("time used: %f msec\n", timeuse);
        }

        free(list);
        return 1;

}