算法1.2--选择排序(SelectSort)

方法:从M个数中找出最小的一个数,放在无序数列的最前面.算法的正确性是明显的.

如果有N个数,那么需要N-1轮的搜索.第i次搜索要比较,要比较N-i次比较,则比较次数为:

(N-1) + (N-2) + (N-3) + ... + 1 = N(N-1)/2 

O(N^2)

#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 select_sort(int * list, int length)
{
        int i, j, min;
        int temp;
        for(i = 0; i < length-1; i ++)
        {
                min = i;
                for(j = i +1; j < length; j ++)
                {
                        if(list[j] < list[min])
                                min = j;
                }

                /*Swap the two elements*/
                temp = list[min];
                list[min] = list[i];
                list[i] = temp;

                show_list(list, length);
        }
}

int main(int argc, char * argv[])
{
        int length;
        int * list = NULL;

        /*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
        {
                show_list(list, length);
                select_sort(list, length);
        }
        free(list);
        return 1;
}