强化阶段（第3-4个月）：排序算法 - 冒泡排序优化：鸡尾酒排序（双向冒泡）减少不必要的比较次数

在备考全国青少年机器人技术等级考试的Python编程部分时，排序算法是一个重要的知识点。特别是在强化阶段（第3-4个月），掌握各种排序算法及其优化方法显得尤为重要。本文将详细介绍如何通过鸡尾酒排序（双向冒泡）来优化传统的冒泡排序，从而减少不必要的比较次数。

一、冒泡排序的基本原理

冒泡排序是一种简单的排序算法，其基本思想是通过多次遍历数组，每次比较相邻的两个元素，如果它们的顺序错误就交换它们的位置。经过多次遍历后，整个数组就会变得有序。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

二、冒泡排序的缺点

虽然冒泡排序实现简单，但其效率较低，时间复杂度为O(n^2)。在处理大规模数据时，性能表现不佳。此外，冒泡排序在每一轮遍历中都会进行大量的比较和交换操作，其中很多是比较不必要的。

三、鸡尾酒排序（双向冒泡）优化

为了提高冒泡排序的效率，可以使用鸡尾酒排序（Cocktail Shaker Sort），也称为双向冒泡排序。鸡尾酒排序在每一轮遍历中，先从左到右进行一次冒泡排序，再从右到左进行一次冒泡排序。这样可以减少不必要的比较次数，提高排序效率。

1. 鸡尾酒排序的基本原理

鸡尾酒排序在每一轮遍历中，先从左到右进行一次冒泡排序，将最大的元素移到最右边；然后再从右到左进行一次冒泡排序，将最小的元素移到最左边。通过这种方式，鸡尾酒排序可以更快地将最大和最小的元素放到正确的位置。

def cocktail_shaker_sort(arr):
    n = len(arr)
    start = 0
    end = n - 1
    swapped = True
    
    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