『Bubble Sort』详解「冒泡排序」的Python实现| Algorithms | Chihokyo BLOG

冒泡排序

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

冒泡排序是最简单的排序算法，它可以通过重复交换相邻元素来进行排序。

什么是冒泡排序，定义自己网上找，就是不断的跟冒泡似的向上去而已。
都说什么比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
但一写代码就不对，单纯这样两句话Code写是写不出来的。

比如一般人可能就这样写了。
写完之后还觉得没毛病。→ 我自己 ✌('ω'✌ )

def error_bubble_sort(arr):  
    for i in range(len(arr) - 1):  
        if arr[i] > arr[i+1]:  
            arr[i], arr[i+1] = arr[i+1], arr[i]  
    return arr  

arr = [8, 7, 6, 4, 1]   
print(error_bubble_sort(arr))  

# result  
# [7, 6, 4, 1, 8]

这样的结果就是只排序了1个，就是最后1个。
所以下面几个问题要搞清楚。

Q: 要loop什么，loop几次，start是什么，end是什么？
第一层loop是要执行的次数。第二层loop才是对比交换的次数。
第一层:起始点就是从第1个，结束就是总长度。
第二层:起始点就是从第1个，结束就是未排序好的总长度。

Q: 跟旁边交换，旁边是什么？
左边，旁边是i-1。右边，就是i+1。

Q: 为什么第二个loop要到 n-i-1 这里？
list : [5,6,90,2,89]
index : 0 1 2 3 4
index为0的时候没有任何数字排序好了。所以进行了4次对比。
5跟6比 6跟90比 90跟2比 2跟89比这时候对比了4次也就是n-0-1 = 5-0-1 = 4
以此类推
index为1的时候最后1个数已排序。对比3次。
index为2的时候最后2个数已排序。对比2次。
index为3的时候最后3个数已排序。对比1次。
index为4的时候最后4个数已排序。对比0次。

思路1

传统经典做法

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

arr = [64, 34, 25, 12, 22, 11, 90]  
print(bubble_sort(arr))  

# result  
# [11, 12, 22, 25, 34, 64, 90]

思路2

本质差不多的转换思路，想一想也能想通的做法。
其实就是搞清楚loop的到底是什么。

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

arr = [64, 34, 25, 12, 22, 11, 90]  
print(bubble_sort(arr))  

# result  
# [11, 12, 22, 25, 34, 64, 90]

小小优化

现在写一个小小的优化的思路。（冒泡本来效率就低，所以优化与否意义不太大？
现在我们都知道冒泡是拿着1个数字然后左右循环对比直到最后1次然后进行排列。
如果我们在第一次进行和左右对比的时候这全程都没有交换的话，那么还要继续下去吗？
比如
[1,2,3,4,5]
我们拿出来1，和后面的对比的时候发现从来没有交换过，那么2还要看吗？
肯定是不要的。那么怎么知道有没有交换呢，用一个count来计数就可以完成。

# 不知道有没有新手跟我一样这样书写了  
# 这样写法是错误的  

def error_bubble_sort(arr):  
    count = 0  
    for i in range(len(arr)):  
        for j in range(len(arr)-i-1):  
            if arr[j] > arr[j+1]:  
                arr[j],arr[j+1] = arr[j+1],arr[j]  
                count += 1  
        if count == 0:  
            break  
    return arr  

# count这个变量应该在下面定义  

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

『Bubble Sort』详解「冒泡排序」的Python实现

冒泡排序

思路1

思路2

小小优化

『Selection Sort』详解「选择排序」的Python实现

共有评论(0)

Chihokyo 旺财