当前位置：首页 > article >正文

冒泡排序原理及python代码

article 2024/11/13 15:14:05

引言

在计算机科学中，排序算法是一种将一系列数据元素按照特定顺序排列的算法。排序算法广泛应用于各种领域，如数据库管理、搜索引擎优化、数据压缩、加密解密等。冒泡排序（Bubble Sort）是排序算法中最简单直观的一种，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小（或越大）的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法原理

冒泡排序的基本思想是：通过对待排序序列从前向后（或从后向前），依次比较相邻元素的值，若发现逆序则交换，使值较大（或较小）的元素逐渐从前移向后（或从后移向前），就像水底的气泡一样逐渐向上冒。

第一轮排序：从第一个元素开始，比较相邻的两个元素，如果第一个比第二个大（升序排序），则交换它们两个；对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
第二轮排序：对所有的元素（除了最后一个）重复以上的步骤，除了最后一个。
持续每轮次的操作：每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序的特点

简单性：冒泡排序算法逻辑简单，易于实现。
稳定性：冒泡排序是稳定的排序算法，即相等的元素在排序后仍然保持原有的顺序。
低效性：冒泡排序的时间复杂度较高，平均和最坏情况都是O(n^2)，其中n是数组的长度。这使得它不适合大数据量的排序。
空间复杂度：冒泡排序是原地排序，不需要额外的存储空间，空间复杂度为O(1)。

冒泡排序的Python实现

下面是一个简单的冒泡排序算法的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):  
            # 遍历数组从0到n-i-1  
            # 交换如果元素找到的元素比下一个大  
            if arr[j] > arr[j+1]:  
                arr[j], arr[j+1] = arr[j+1], arr[j]  
  
# 测试冒泡排序  
if __name__ == "__main__":  
    arr = [64, 34, 25, 12, 22, 11, 90]  
    bubble_sort(arr)  
    print("Sorted array is:", arr)

冒泡排序的优化

虽然冒泡排序算法简单，但其在最坏情况下的性能较差。不过，有几种方法可以优化冒泡排序：

提前结束：如果在某一轮遍历中没有发生任何交换，那么可以判断数组已经有序，因此可以提前结束排序。

def bubble_sort_optimized(arr):  
    n = len(arr)  
    for i in range(n):  
        swapped = False  
        for j in range(0, n-i-1):  
            if arr[j] > arr[j+1]:  
                arr[j], arr[j+1] = arr[j+1], arr[j]  
                swapped = True  
        # 如果这一轮没有发生交换，说明数组已经有序  
        if not swapped:  
            break

鸡尾酒排序（双向冒泡排序）：同时从数组的两端开始进行比较，一端向前移动，另一端向后移动，这样可以减少一些不必要的比较，特别是在数据部分有序时。

def cocktail_sort(arr):  
    n = len(arr)  
    swapped = True  
    start = 0  
    end = n-1  
    while swapped:  
        swapped = False  
        # 正向冒泡  
        for i in range(start, end):  
            if arr[i] > arr[i+1]:  
                arr[i], arr[i+1] = arr[i+1], arr[i]  
                swapped = True  
        if not swapped:  
            break  
        swapped = False  
        end -= 1  
  
        # 反向冒泡  
        for i in range(end-1, start-1, -1):  
            if arr[i] > arr[i+1]:  
                arr[i], arr[i+1] = arr[i+1], arr[i]  
                swapped = True  
        start += 1

冒泡排序的应用场景

尽管冒泡排序在效率上不如许多其他排序算法，但在某些特定场景下仍然有其用武之地：