冒泡排序(BUBBLE SORT)

如果一个队列只有两个元素且为逆序，只要将这两个元素交换即可。冒泡排序就是一种基于“交换”思想的排序方法，每次比较两个元素，如果为逆序，就将其交换。而这两个元素的选取，就是遍历整个队列来得到。

冒泡排序一般步骤：

• 第一趟冒泡。遍历整个队列，将当前元素和身后的元素进行比较，逆序的进行交换。这样会进行(n-1)次；
• 然后再进行遍历冒泡，直到该趟遍历过程中没有发生交换操作为止，此时队列已为正序。

冒泡排序特性：

• 冒泡的过程中，每一次交换都是大元素向下移动，小元素向上移动，所以整个一趟排序的趋势就是大元素向下移动，小元素想上移动。因为在每一次交换的过程中，大元素都会被交换到下方，所以，一趟排序结束之后，都会有一个当前队列中最大的元素被交换到了队列最后，到达最终位置。
• 如果该队列为逆序，那就需要遍历(n-1)趟，一共sum_{i=n}^{2}(i-1)比较；如果为正序，那么只需要遍历一趟，进行(n-1)比较即可。平均时间复杂度是O(n^{2})；
• 该排序方法是就地排序，只是在交换的过程中需要申请一个临时变量，一个变量来记录当前遍历是否发生过交换操作，所以空间复杂度是O(1)；
• 冒泡排序基于交换的思想，所以可以保证两个相同的元素不会被交换，该算法是稳定的。

冒牌排序实例：

• 初始序列：{49, 38, 65, 97, 76, 13, 27, 49}
• {38, 49, 65, 97, 76, 13, 27, 49} 元素49和38进行比较，逆序，交换；
• {38, 49, 65, 76, 97, 13, 27, 49} 元素49行业64进行比较，正序，不交换；
• {38, 49, 65, 76, 13, 27, 97, 49} 元素65和76进行比较，正序；
• {38, 49, 65, 76, 13, 27, 49, 97} 元素76和13进行比较，逆序，交换；
• {38, 49, 65, 13, 76, 27, 49, 97} 元素76和27进行比较，逆序，交换；
• {38, 49, 65, 13, 27, 76, 49, 97} 元素76和49进行比较，逆序，交换；
• {38, 49, 65, 13, 27, 49, 76}, 97 元素76和97进行比较，正序，不交换。一趟遍历结束，97到达最终位置；
• {38, 49, 13, 27, 49, 65}, 76, 97 第二趟排序，76到达最终位置；
• {38, 13, 27, 49, 49}, 65, 76, 97 第三趟排序结束，选出了65；
• {13, 27, 38, 49}, 49, 65, 76, 97 第四趟排序
• {13, 27, 38}, 49, 49, 65, 76, 97 第五趟排序
• {13, 27}, 38, 49, 49, 65, 76, 97 第六趟排序
• 13, 27, 38, 49, 49, 65, 76, 97 最终结果

原文链接：冒泡排序(BUBBLE SORT)，转载请注明来源！