思路方法:从M个数中找出最小个数,放在无序数列最前面.算法正确性是明显.
如果有N个数,那么需要N-1轮搜索.第i次搜索要比较,要比较N-i次比较,则比较次数为:
(N-1) + (N-2) + (N-3) + ... + 1 = N(N-1)/2
O(N^2)
# <stdlib.h>
# <stdio.h>
# <errno.h>
# <time.h>
# MAX_LENGTH 100
/*Show usage*/
void usage(char * prog)
{
prf(\"%s Usage:\\n\", prog);
prf(\"%s <the count of numbers to sort (should be less than 100)>\\n\", prog);
}
/*Generate and initialize the list*/
* generate_list( count)
{
i;
* list;
list = ( *)malloc(count*());
(list NULL)
{
perror(\"malloc\");
NULL;
}
/*Initialize the list with egers less than 100*/
srandom((unsigned )time(NULL));
for (i = 0; i < count ; i )
list[i] = random%100;
list;
}
/*Show the list*/
void show_list( * list, length)
{
i;
for(i = 0; i < length; i )
prf(\"%d \", list[i]);
prf(\"\\n\");
}
/*algorithm*/
void select_sort( * list, length)
{
i, j, min;
temp;
for(i = 0; i < length-1; i )
{
min = i;
for(j = i +1; j < length; j )
{
(list[j] < list[min])
min = j;
}
/*Swap the two elements*/
temp = list[min];
list[min] = list[i];
list[i] = temp;
show_list(list, length);
}
}
( argc, char * argv)
{
length;
* list = NULL;
/*Deal with the arguments*/
(argc != 2)
{
usage(argv[0]);
exit(127);
}
length = atoi(argv[1]);
(!length || length > MAX_LENGTH)
{
usage(argv[0]);
exit(129);
}
list = generate_list(length);
(list NULL)
exit(128);
{
show_list(list, length);
select_sort(list, length);
}
free(list);
1;
}
最新评论