经典排序：冒泡排序法与选择排序法

冒泡排序 (Bubble sort)

原理是取相邻两个数进行大小比较，判断是否交换。

以从小到大排序为例，冒泡排序就像气泡一样，最小的数慢慢浮上来，最大的数慢慢沉下去。那么完整从头到尾做一次之后最后一位就是原序列中最大的数字了。然后只需要对1~(n-1)个数字进行排序，完成后倒数第二个数字也为原序列的1~n-1元素中最大的值。如此重复，进行n-1次一定能完成排序。参考代码：

 1 #include <stdio.h>
 2 void BubbleSort(int *, int);
 3 int main()
 4 {
 5     int a[] = {9, 5, 3, 6, 7, 2, 5, 4, 3, 9}, i;
 6     int s = sizeof(a) / sizeof(int);
 7     puts("Before sort:");
 8     for(i = 0; i < s; i++)
 9         printf("%d ", a[i]);
10     BubbleSort(a, s);
11     puts("\nAfter sort:");
12     for(i = 0; i < s; i++)
13         printf("%d ", a[i]);
14     return 0;
15 }
16 void BubbleSort(int *a, int s) // a为待排序数组 s为数组中需排序长度
17 {
18     int i, j, tmp;
19     for(i = 0; i < s - 1; i++)
20     {
21         for(j = 1; j < s - i; j++)
22         {
23             if(a[j - 1] > a[j])
24             {
25                 tmp = a[j - 1];
26                 a[j - 1] = a[j];
27                 a[j] = tmp;
28             }
29         }
30     }
31 }

优化：如果一整趟下来都没有一次交换，那么确定该序列已经满足单调，直接跳出循环可以省时。

 1 void BubbleSort(int *a, int s) // a为待排序数组 s为数组中需排序长度
 2 {
 3     int i, j, tmp;
 4     int swap_flag; // 标记一趟内是否有交换过
 5     for(i = 0; i < s - 1; i++)
 6     {
 7         swap_flag = 0;
 8         for(j = 1; j < s - i; j++)
 9         {
10             if(a[j - 1] > a[j])
11             {
12                 swap_flag = 1;
13                 tmp = a[j - 1];
14                 a[j - 1] = a[j];
15                 a[j] = tmp;
16             }
17         }
18         if(swap_flag == 0) break;
19     }
20 }

选择排序 (Select sort)

以从小到大排序为例。原理是在序列中挑一个最小的值，然后与序列中的第一个交换。那么，第一个就是整个序列中最小的数字。再对从第二个数字开始的序列做这个操作，得到剩余序列中最小的数字所在位置，与原序列第二个数交换，以此类推做n-1完成排序。参考代码：

void SelectSort(int *a, int s) // a为待排序数组 s为数组中需排序长度
{
    int i, j, tmp, min_num_index;
    for(i = 0; i < s - 1; i++)
    {
        min_num_index = i;
        for(j = i + 1; j < s; j++)
        {
            if(a[j] < a[min_num_index])
                min_num_index = j;
        }
        if(min_num_index != i)
        {
            tmp = a[i];
            a[i] = a[min_num_index];
            a[min_num_index] = tmp;
        }
    }
}