排序(一)：冒泡排序

冒泡排序(Bubble Sort)是一种比较简单的排序算法，因其越大的元素会经由依次相邻交换慢慢“浮”到数列的顶端，所以叫“冒泡排序”。

原理

冒泡排序其实就是从头开始对整个数列里面的元素进行两两比较，比较大的元素放到后面，接着进行对比，直到最大的一个元素被提取出来放到整个数列的最后。接着再对剩下的元素进行相同的操作，直到整个数列被排序完成。

步骤

1）比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3）针对所有的元素重复以上的步骤，除了最后一个。

4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码

python：

#! /usr/bin/python
#coding:utf-8

def bubbleSort(nums):
    for i in range(len(nums)-1):   # 排序的次数
        for j in range(len(nums)-i-1):  # 列表的下标
            if nums[j+1] < nums[j]:
                #nums[j], nums[j+1] = nums[j+1], nums[j]
                temp = nums[j+1]
                nums[j+1] = nums[j]
                nums[j] = temp
    return nums
nums = [50,10,90,30,70,40,80,60,20]

print(bubbleSort(nums))

运行结果：

1	[10,20,30,40,50,60,70,80,90]

可将数组中数值两两交换改写为一行代码

1	nums[j+1],nums[j] = nums[j],nums[j+1]

算法分析

1）冒泡排序是原地排序算法吗？
冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。

2）冒泡排序是稳定的排序算法吗？

在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

3）冒泡排序的时间复杂度是多少？
最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n^2)。