基本排序算法之冒泡排序的Python实现

2 9月 2017
4 分钟阅读
标签:
算法,
排序,
冒泡排序,
Python

最近因为业务需要，开始学习Python，作为C/C++程序员，一开始写Python总是忍不住在每行后面加个‘;’。当然除了语法，还是要把基本的数据结构和算法都简单的复习一遍的，下面开始从几类常见的排序开始实现，虽然python自带的sorted方法很好用，但是可以用自己的方法与它做一下比较。以下的代码均在Python 3.6环境下验证通过，排序对象为整形列表，按照由小到大的方式排序。

冒泡排序的原理非常简单，就是个双层循环的过程，列表元素像水里的一串气泡，第一趟冒泡从第一个气泡开始，与它相邻的气泡做比较，大的气泡交换到上面去，这个冒泡的过程就是内循环，需要n-1次。每经过一趟冒泡的过程，可以使一个最大的元素冒出来，需要排序的元素数目就会减1，如果列表里面有n个元素，则冒n-1次就可以完成全部过程，这就是外循环。

基于这种原理，用Python3的方法实现如下：

def bubble_sort1(lists):
    """冒泡排序"""
    if list_check(lists) is False:
        return lists
    
    for i in range(len(lists) - 1):
        for j in range(len(lists) - i - 1):
            if lists[j] > lists[j + 1]:
                lists[j], lists[j + 1] = lists[j + 1], lists[j]
    return lists

可以看出这个二层循环的过程，在最坏的情况下，时间复杂度为O(n²)，但是换一种思路，如果有一趟冒泡并没有发生交换，我们就可以确定此时列表已经是有序的了，不需要再去执行下一趟的冒泡过程。于是可以设置一个flag用来记录交换是否发生，则可以将算法优化如下：

def bubble_sort2(lists):
    """冒泡排序添加flag版"""
    
    if list_check(lists) is False:
        return lists
    
    for i in range(len(lists) - 1):
        flag = True
        for j in range(len(lists) - i - 1):
            if lists[j] > lists[j + 1]:
                lists[j], lists[j + 1] = lists[j + 1], lists[j]
                flag = False
        if flag:
            return lists
    return lists

为了比较这两种算法，以及与Python自带的sorted方法的效率，下面用一个装饰器来计算函数执行时间。代码如下：

def time_usage(func):
    """时间计算函数"""
    def wrapper(*args, **kwargs):
        """用装饰器和timeit提高计算精度"""
        start_time = timeit.default_timer()
        ret = func(*args, **kwargs)
        use_time = timeit.default_timer() - start_time
        print('{} elapsed time: {} seconds!'.format(func.__name__, use_time))
        return ret
    return wrapper

然后从0~20000之间取10000个随机整数组成列表进行排序并统计时间，完整代码如下：

# -*- coding:utf-8 -*-
"""常见排序算法的Python实现"""
import timeit
import numpy.random as nprnd
    
RAND_LIST = nprnd.randint(20000, size=10000).tolist()
    
def list_check(lists):
    """list类型入参检查函数"""
    if not isinstance(lists, list):
        print('Only support list!')
        return False
    
    if not lists:
        print('The list is empty!')
        return False
        
        
def time_usage(func):
    """时间计算函数"""
    def wrapper(*args, **kwargs):
        """用装饰器和timeit提高计算精度"""
        start_time = timeit.default_timer()
        ret = func(*args, **kwargs)
        use_time = timeit.default_timer() - start_time
        print('{} elapsed time: {} seconds!'.format(func.__name__, use_time))
        return ret
    return wrapper
    
    
@time_usage
def bubble_sort1(lists):
    """冒泡排序"""
    if list_check(lists) is False:
        return lists
    
    for i in range(len(lists) - 1):
        for j in range(len(lists) - i - 1):
            if lists[j] > lists[j + 1]:
                lists[j], lists[j + 1] = lists[j + 1], lists[j]
    return lists
    
    
@time_usage
def bubble_sort2(lists):
    """冒泡排序添加flag版"""
    
    if list_check(lists) is False:
        return lists
    
    for i in range(len(lists) - 1):
        flag = True
        for j in range(len(lists) - i - 1):
            if lists[j] > lists[j + 1]:
                lists[j], lists[j + 1] = lists[j + 1], lists[j]
                flag = False
        if flag:
            return lists
    return lists
    
if __name__ == '__main__':
    time_usage(sorted)(RAND_LIST)
    
    SORT_LIST = copy.deepcopy(RAND_LIST)
    bubble_sort1(SORT_LIST)
    
    SORT_LIST = copy.deepcopy(RAND_LIST)
    bubble_sort2(SORT_LIST)

执行一下比较它们的效率：

可以看出事与愿违，第二种反而比第一种慢了一点点，多次排序比较后依然如此，作为对比我又用C++去实现了一遍，结果是一样的，如下图所示，第二种比第一种慢一点点：

其原因可能是因为flag只有在大部分数都排序好的情况下才用得上，对于这种大规模随机数，每次循环的过程中都要对flag的赋值与判断，占用的时间累积起来却是得不偿失。

但是不管是哪种冒泡排序，同内置的sorted函数的0.003s执行时间相比，效率仍然低了几个数量级。

冒泡排序的实现简单，适合教科书中详解循环的用法，但是它效率低下，在数据规模很小的场景下使用比较方便，对于大规模数据的处理，还是需要考虑使用别的排序方法。