冒泡排序

首先排序分为四种：

交换排序：包括冒泡排序，快速排序。

选择排序：包括直接选择排序，堆排序。

插入排序：包括直接插入排序，希尔排序。

合并排序：合并排序。

冒泡排序：

首先我们自己来设计一下“冒泡排序”，这种排序很现实的例子就是：

我抓一把沙仍进水里，那么沙子会立马沉入水底，沙子上的灰尘会因为惯性暂时沉入水底，但是又会立马像气泡一样浮出水面，最后也就真相大白咯。

关于冒泡的思想，我不会说那么官方的理论，也不会贴那些文字上来，我的思想就是看图说话。

那么我们就上图.

要达到冒泡的效果，我们就要把一组数字竖起来看，大家想想，如何冒泡？如何来体会重的沉底，轻的上浮？

第一步: 我们拿40跟20比，发现40是老大，不用交换。

第二步: 然后向前推一步，就是拿20跟30比，发现30是老大，就要交换了。

第三步：拿交换后的20跟10比，发现自己是老大，不用交换。

第四步：拿10跟50交换，发现50是老大，进行交换。

最后，我们经过一次遍历，把数组中最小的数字送上去了，看看，我们向目标又迈进了一步。

实现 C++程序：

 1 #include<iostream>
 2 #include <ctime>  //使用了time() 函数 
 3 #include <cstdlib>    //使用了srand()函数 
 4 
 5 const int N=20005;
 6 int a[N];
 7 using namespace std;
 8 //冒泡排序算法
 9         void bubblesort(int *a, int n)
10         {
11             int temp;
12             //第一层循环： 表明要比较的次数，比如n个数，肯定要比较n-1次
13             for (int i = 1; i < n; i++)
14             {
15                 //j>i: 从后往前的的下标一定大于从前往后的下标，否则就超越了。
16                 for (int j = n; j > i; j--)
17                 {
18                     //如果前面一个数大于后面一个数则交换
19                     if (a[j - 1] > a[j])
20                     {
21                         temp = a[j - 1];
22                         a[j - 1] = a[j];
23                         a[j] = temp;
24                     }
25                 }
26             }
27         }
28                  
29 
30 int main()
31 {
32     //随机产生n个数存入数组a中 
33     int n=17000;
34     srand(int(time(0)));      //利用时间函数time()，产生每次不同的随机数种子
35     for(int i=1;i<=n;i++) a[i]=rand();  //随机产生3000个数存于数组a中 （从1开始） 
36     clock_t start = clock();
37     bubblesort(a,n);                   //对数组a进行排序（从1开始） 
38     clock_t end = clock();
39     for(int i=1;i<=20;i++) cout<<a[i]<<' ';    //输出前20个数据（已从小到大排序） 
40     cout<<endl<<"冒泡排序耗时为："<<end-start<<"ms"<<endl; 
41     return 0;
42 }

经我亲测在1秒中之内，可排序的数据为17000个，原因为冒泡的时间复杂度为O(n²),因此只能排17000个数据，要想排序次数超过万级，就必须更换成新的排序方法。