参考：[http://www.crazycoder.cn/]这几个排序算法都是基于相邻元素的比较的，而且都是O(N^2)阶的算法。

参考：[http://www.crazycoder.cn/]在最坏情况下，基于相邻元素的比较及交换的算法，至少需要N(N-1)/2次比较，平均情况下至少需要N(N-1)/4次比较。

参考：[http://www.crazycoder.cn/]

算法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 <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
#include <time.h>

#define MAX_LENGTH 100

/*Show usage*/
void usage(char * prog)
{
printf(\"%s Usage:\\n\", prog);
printf(\"%s <the count of numbers to sort (should be less than 100)>\\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\");
}