排序算法（二）冒泡法

　　冒泡排序的基本思想：

　　从数组的第一个数开始，相邻两数进行比较，经过交换，小的数放在前面，大的数放在后面，一直到最后一个数与倒数第二个数比较完，这样比较一轮后，数组中最大的数“下沉”到了数组的最后，每一趟只能确定将一个数归位；然后，新的一轮的比较又是从第一个数开始......如果数组中有N个元素，则共需要比较N-1轮；形象地描述这种排序方法：每次比较都会使较小的值像气泡一样“上浮”，而较大的值逐渐“下沉”！

　　代码：

 1 #include<iostream>
 2 using namespace std;
 3 void bubbleSort(int data[], int len);
 4 int main()
 5 {
 6     int len;//需要排序的个数
 7     cout << "需要排序的个数为：" << endl;
 8     scanf_s("%d", &len);
 9     int*  data = (int*)malloc((len)*sizeof(int));//动态分配大小为（len）的数组
10     memset(data, 0, (len)*sizeof(int));//初始化数组的值为0，否则会出错
11     cout << "原始数据为：" << endl;
12     for (int i = 0; i < len; i++)//循环读入len个数到数组data中
13         cin >> data[i];
14     cout << endl;
15     cout << "--------------------------------------" << endl;
16     bubbleSort(data, len);
17     cout << "冒泡法排序后输出为：" << endl;
18     for (int i = 0; i < len; i++)
19     {
20         cout << data[i] << ",";
21     }
22     cout << endl;
23     cout << "--------------------------------------" << endl;
24     system("pause");
25     return(0);
26 }
27 
28 /*冒泡实现函数*/
29 void bubbleSort(int data[], int len)
30 {
31     int temp;
32     for (int i = 1; i < len; i++)//n个数排序，只用进行n-1趟
33     {
34         for (int j = 0; j < len - i; j++)//从第一位开始比较直到最后一个尚未归位的数，第1趟时，要比较len个数，所以需要比较len-1次，第2趟时，最后一个数已排好，无需比较，所以只需比较前len-i个数，所以只需比较len-2次
35         {
36             if (data[j]>data[j + 1])//从小到大排序，若为小于号时，则为从大到小
37             {
38                 temp = data[j];
39                 data[j] = data[j + 1];
40                 data[j + 1] = temp;
41             }
42         }
43         cout << "第" << i << "次排序后输出为：" << endl;
44         for (int k = 0; k < len; k++)
45         {
46             cout << data[k] << ",";
47         }
48         cout << endl;
49         cout << "--------------------------------------" << endl;
50     }
51 }

　　程序运行结果：

　　冒泡排序的核心部分是双重嵌套循环。不难看出冒泡排序的时间复杂度是O(N²)。这是一个非常高的时间复杂度。冒泡排序早在1956年就有人开始研究，之后有很多人都尝试过对冒泡排序进行改进，但结果却令人失望。如Knuth（Donald E. Knuth中文名为高德纳，1974年图灵奖获得者）所说：“冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实之外，似乎没有什么值得推荐的。”