冒泡排序（交换排序的一种）

思想：（升序）相邻两个比较大小，如果前者大于后者，则互换；第一趟下来，最大的数就到正确位置上了。依此类推……

冒泡排序是交换排序的一种。

代码：

 1 // BubbleSort.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 #include <string.h>
 6 #define MAX_ARRAY_NUM 10
 7 void BubbleSort(int* i_Num)
 8 {
 9     int temp = 0;
10     for (int i = 0; i < MAX_ARRAY_NUM - 1; i++)
11     {
12         for (int j = 0; j < MAX_ARRAY_NUM - i - 1; j++)
13         {
14             if (i_Num[j] > i_Num[j+1])
15             {
16                 temp = i_Num[j];
17                 i_Num[j] = i_Num[j+1];
18                 i_Num[j+1] = temp;
19             }
20         }
21 
22     }
23     for (int i = 0; i < 10; i++)
24     {
25         printf("%d	", i_Num[i]);
26     }
27 }
28 
29 int _tmain(int argc, _TCHAR* argv[])
30 {
31     int aNum[10] = {9, 56, 45, 28, 78, 4, 8, 2, 0, 58};
32 
33     BubbleSort(aNum);
34     return 0;
35 }

时间复杂度：

第一趟排序需要比较n-1次，第二趟需要比较n-2次，……，最后一趟只需比较1次，因此复杂度为：（n-1）+（n-2）+……+2+1 = 1/2*n^2-1/2*n，去掉低阶项，去掉常数系数，即复杂度为O(n^2)。

稳定性：

稳定性指原来待排序的原序中间有相同的元素，在没有排序之前它们之间有先后顺序，在排完之后它们的先后顺序不变，就称为这个算法是稳定的。因此，冒泡是一个稳定的排序，因为如果两个元素值相同，则位置不进行交换。