您的位置:

Python实现冒泡排序

一、冒泡排序简介

冒泡排序(Bubble Sort)是一种简单的排序算法,它重复地遍历要排序的列表,每次比较相邻的两项,如果它们的顺序错误就交换它们,直到没有要交换的项为止。冒泡排序算法的时间复杂度为 O(n²)。

二、冒泡排序实现思路

冒泡排序算法的实现思路可以用以下的步骤来描述:

1、比较相邻的元素,如果第一个比第二个大,就交换它们的位置;

2、对每一对相邻的元素都进行步骤1的工作,从开始第一对到结尾最后一对,这样在最后的元素应该会是最大的数;

3、针对所有的元素重复以上的步骤,除了最后一个;

4、持续每次对越来越少的元素重复上述步骤,直到没有任何一对数字需要比较为止。

三、Python实现代码

def bubble_sort(arr):
    n = len(arr)
    # 遍历所有数组元素
    for i in range(n):
        # Last i elements are already in place
        for j in range(0, n-i-1):
            # traverse the array from 0 to n-i-1
            # Swap if the element found is greater
            # than the next element
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]

四、代码解析

1、定义bubble_sort函数,传入一个参数arr,表示待排序的数组;

2、定义变量n,表示数组的长度;

3、通过两个for循环遍历数组,外层循环遍历数组的所有元素,内层循环则遍历数组中前n-i-1个元素,因为最后的n-i-1个元素已经排好序了;

4、当发现arr[j]比arr[j+1]大时,交换这两个元素的位置;

5、最终,得到一个有序的数组。

五、算法优化

冒泡排序算法虽然简单,但是时间复杂度比较高,因此需要对算法进行优化。

1、设置标志位

如果在某次遍历中,没有任何元素被交换,说明数组已经有序,可以停止遍历。

def bubble_sort(arr):
    n = len(arr)
    # 遍历所有数组元素
    for i in range(n):
        # Last i elements are already in place
        flag = True
        for j in range(0, n-i-1):
            # traverse the array from 0 to n-i-1
            # Swap if the element found is greater
            # than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                flag = False
        # 如果遍历中没有任何元素被交换,说明数组已经有序,可以停止遍历。
        if flag:
            break

2、优化搜索范围

对于传统的冒泡排序,在每一轮遍历时都要比较整个数组,这样即使数组已经有序,仍然要进行n次遍历。而如果每次遍历时记录最后一次交换的位置,那么后面的元素就已经有序了,可以减少比较次数。

def bubble_sort(arr):
    n = len(arr)
    # 遍历所有数组元素
    for i in range(n):
        # Last i elements are already in place
        flag = True
        # 记录最后一次元素交换的位置
        k = n - 1
        for j in range(0, k):
            # traverse the array from 0 to n-i-1
            # Swap if the element found is greater
            # than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                # 更新最后一次元素交换的位置
                k = j
                flag = False
        # 如果遍历中没有任何元素被交换,说明数组已经有序,可以停止遍历。
        if flag:
            break

六、总结

冒泡排序是一种简单有效的排序算法,但是时间复杂度比较高,需要使用优化手段来提高效率。Python实现冒泡排序的代码也比较简单,可以方便地进行调试和优化。