排序算法（二）——冒泡排序（bubble sort）

bubble sort

基本思想：冒泡排序也是一种简单直观的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列顶端。一般重复次即可完成排序。

算法分析：

冒泡排序是一种简单直接暴力的排序算法。因为每一轮比较可能多个元素移动位置，而元素位置的互换是需要消耗资源的，所以这是一种偏慢的排序算法，仅适用于含有较少元素的数列进行排序。
稳定性：因为只有前一个元素大于后一个元素才可能交换位置，所以相同元素的相对顺序不可能改变，所以是稳定排序。
比较性：因为排序时元素之间需要比较，所以是比较排序。

时间复杂度	空间复杂度
因为需要双层循环 $O(n(n-1))$ ,因此平均时间复杂度为 $O(n^2)$	只需要常数个辅助单元，所以空间复杂度为 $O(1)$ （该空间复杂度的排序又称为原地排序（in-place））

def BubbleSort(arr):
    n = len(arr)
    
    #停止条件，因为冒泡排序最多n-1次就可以完成
    for i in range(n):
        #每次比较完的最后那个元素一定是最大的
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

BubbleSort(arr)
 
print ("排序后的数组:")
for i in range(len(arr)):
    print ("%d" %arr[i])