【python】实现冒泡排序及其优化

比眉伴天荒 2024-03-25 17:44 79阅读 0赞

#### python 实现冒泡排序 ####

冒泡排序是一种常见的排序算法，相对来说比较简单。它的基本思想是比较相邻的元素，如果顺序不对就交换它们的位置，这样一轮下来可以确保最大（或最小）的元素被交换到了最后的位置。接下来再对剩余的元素进行同样的操作，直到所有元素都排好序为止。以下是python实现冒泡排序的几种方法：

1.  最基本的冒泡排序方法是通过两个嵌套的循环来实现，外层循环控制循环的次数，内层循环控制相邻元素的比较和交换。具体实现如下：

def bubbleSort(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]
        return arr

1.  可以在基本冒泡排序的基础上加入一个参数order，用于控制排序的顺序，当order>0时为升序，当order<0时为降序。具体实现如下：

def bubbleSort(arr,order):
        max = len(arr)
        for i in range(0, max):
            j = 1
            while(j<max-i):
                if((arr[j-1]>arr[j]) and (int(order)>0)) or ((arr[j-1]<arr[j]) and (int(order)<0)):
                    arr[j-1], arr[j] = arr[j], arr[j - 1]
                j += 1
            i += 1
        return arr

1.  可以对冒泡排序进行优化，当一轮下来没有发生任何交换时，说明已经排好序，可以直接退出循环。具体实现如下：

def bubbleSort(arr):
        n = len(arr)
        for i in range(n):
            flag = True
            for j in range(0, n-i-1):
                if arr[j] > arr[j+1] :
                    arr[j], arr[j+1] = arr[j+1], arr[j]
                    flag = False
            if flag:
                break
        return arr

1.  可以使用双向冒泡排序（也称鸡尾酒排序），在每一轮中不仅从左到右比较和交换相邻元素，还从右到左比较和交换相邻元素。具体实现如下：

def cocktailSort(arr):
        n = len(arr)
        start = 0
        end = n-1
        while (start <= end):
            flag = True
            for i in range(start, end):
                if arr[i] > arr[i+1]:
                    arr[i], arr[i+1] = arr[i+1], arr[i]
                    flag = False
            end -= 1
            for i in range(end, start,