排序算法(2)-冒泡排序

原理:

冒泡排序的思想，是让最大的数浮动到数组最后的位置，其次大的数浮动到数组倒数第二个位置……

当然，你也可以从大到小排序，也可以从后向前冒泡。其特征操作是相邻元素的比较和交换。

---

排序过程

举例说明：要排序数组：{10,3,7,4,9,2};   

第一趟排序：

第一次排序：10和3比较，10大于3，交换位置：  3   10  7  4   9  2

第二次排序：10和7比较，10大于7，交换位置：3   7  10  4   9   2

第三次排序：10和4比较，10大于4，交换位置：  3  7  4  10  9  2

第四次排序：10和9比较，10大于9，交换位置：3  7  4  9  10  2

第五次排序：10和2比较：10大于2，交换位置：  3  7  4  9  2  10

第一趟总共进行了5次比较， 排序结果：      3  7  4  9  2  10

---------------------------------------------------------------------

第二趟排序：

第一次排序：3和7比较，3小于7，不交换位置：3  7  4  9  2  10

第二次排序：7和4比较，7大于4，交换位置：  3  4  7  9  2  10

第三次排序：7和9比较，7小于9，不交换位置：3  4  7  9  2  10

第四次排序：9和2比较，9大于2，交换位置：  3  4  7  2  9  10

第二趟总共进行了4次比较， 排序结果：      3  4  7  2  9  10

---------------------------------------------------------------------

第三趟排序：

第一次排序：3和4比较，3小于4，不交换位置：  3  4  7  2  9  10

第二次排序：4和7比较，4小于7，不交换位置：3  4  7  2  9  10

第三次排序：7和2比较，7大于9，交换位置：  3  4  2  7  9  10

第二趟总共进行了3次比较，排序结果：         3  4  2  7  9   10

---------------------------------------------------------------------

第四趟排序：

第一次排序：3和4比较，3小于4，不交换位置：3  4  2  7  9   10

第二次排序：4和2比较，4大于2，交换位置：  3  2  4  7  9  10

第二趟总共进行了2次比较，排序结果：       3  2  4  7  9  10

---------------------------------------------------------------------

第五趟排序：

第一次排序：3和2比较，3大于2，交换位置：  2  3  4  7  9  10

第二趟总共进行了1次比较，排序结果：  2  3  4  7  9  10

---------------------------------------------------------------------

---

代码实现：

---

时间复杂度:其外层循环执行 N - 1次。内层循环最多的时候执行N次，最少的时候执行1次，平均执行(N+1)/2次。

所以循环体内的比较交换约执行(N - 1)(N + 1) / 2 = (N^2 - 1)/2（其中N^2是仿照Latex中的记法，表示N的平方）。按照计算复杂度的原则，去掉常数，去掉最高项系数，其复杂度为O(N^2)。