冒泡排序过程详解

柔光的暖阳◎ 2022-09-11 07:28 277阅读 0赞

## 冒泡排序 ##

### 1，引入 ###

*  一种简单的排序算法

### 2，比较轮数 与 每轮的比较次数 ###

*  比如，我们要对`64 34 25 72 22 11 60`这个序列**升序排序**。
 *  **冒泡排序**的思路是：将序列从左到右，每两个相邻的数都比较一次，如果前者大于后者，就交换这两个相邻数字的位置，**这个过程重复多次**，就可以将序列变成升序的。拿上面例子来说：  
    ![第一轮交换过程][f70c86e0d6974664af79448aac7a9e8e.png_pic_center]
 *  想象一下，你走在回家的路上，沿途有各种价值不一的宝物，每次遇到宝物，你总会把手里的宝物和遇到的宝物比较，然后带走价值较大的那一个，当你回到家时，你带来的肯定是价值最大的那一个。这就是上面不断比较然后适时交换想达到的目的。
 *  所以第一轮后的必然结果是**序列中的最大值被交换到序列最右端**：  
    ![第一轮交换结果][4d910936af0e49ff92880638ef1574cc.png_pic_center]
 *  这表示我们第二轮只需要比较到倒数第二个位置，毕竟序列剩余的任何数都比最大值小，比较的结果也必然是不交换。
 *  也可以这样理解：第一轮过后，最大值已经被安排在了合适的位置，现在相当于是对前`n-1`个数组成的子序列排序。这种理解对以递归实现冒泡排序很有用。
 *  下面继续看第二轮：  
    ![第二轮比较过程][882e63adf5ad4e62a1f8e8010df5cc19.png_pic_center]
 *  第二轮排序后的结果：  
    ![第二轮交换结果][23d5cc59152c49609400a5098ab63920.png_pic_center]
 *  第二轮过后，倒数第二大的数字`64`被交换到了倒数第二个位置上，同样下一轮中我们只比较到倒数第三个位置即可。
 *  所以**每轮比较的次数都比前一轮少1**。
 *  另一个问题是：要使整个序列有序最少需要比较多少轮？
 *  每轮过后都会将一个当前最大值放到序列右端，`n-1`轮后，剩余的最后一个元素相当于自己组成序列的最大值，无需比较，自然有序，所以最少需要的比较轮数是`n-1`（`n`是元素总数）  
    ![剩余几轮比较过程][ba37f93e237345edaf93500c9576bdab.png_pic_center]

### 3，实现 ###

#### 3,1, C++代码 ####

*  C++实现：

// bubble_sort.cc
    void bubble_sort(vector<int>& seq) {
        
    	auto length = seq.size();
    	for (int i = 0; i < length - 1; ++i) {
        	// 进行 n-1 轮
    		bool is_sortted = true;
    		for (int j = 0; j < length - 1 - i; ++j) {
        	// 每轮比较次数比前一轮少1
    			if (seq.at(j) > seq.at(j + 1)) {
        
    				is_sortted = false;
    				
    				// swap
    				auto tmp = seq[j];
    				seq[j] = seq[j + 1];
    				seq[j + 1] = tmp;
    			}
    		}
    		if (is_sortted)
    			break;
    	}
    }

*  C++ 调用：

int main()
    {
        
    	vector<int> ivec = {
         64, 34, 25, 72, 22, 11, 60 };
    	bubble_sort(ivec);
    	for (auto i : ivec) {
        
    		cout << i << ' ';
    	}
    }
    
    // 输出：11 22 25 34 60 64 72

#### 3,2, Python代码 ####

*  Python实现：

def bubble_sort(collection):
        length = len(collection)
        for i in range(length - 1):	# 进行 n-1 轮
            swapped = False
            for j in range(length - 1 - i):		
                if collection[j] > collection[j + 1]:	# 每轮比较次数比前一轮少1
                    swapped = True
                    collection[j], collection[j + 1] = collection[j + 1], collection[j]
            if not swapped:
                break
        return collection

*  Python调用：

coll = [64, 34, 25, 72, 22, 11, 60]
    print(*bubble_sort(coll))
    
    # 输出：11 22 25 34 60 64 72

#### 3,3, 优化标记 ####

*  上面实现中都使用了一个`bool`来标记序列是否提前有序，对于已有序的序列，某轮比较中根本不会发生交换操作（不会进入`if`语句），所以当某轮过后此`bool`标记没有被置位（没有进入`if`语句），表示序列已经有序，可以提前结束。

### 4，参考 ###

*  [Bubble Sort - GeeksforGeeks][]
 *  [All Algorithms implemented in Python][]

[f70c86e0d6974664af79448aac7a9e8e.png_pic_center]: /images/20220828/e29c5c75291641b6b237cf50001db2bb.png
[4d910936af0e49ff92880638ef1574cc.png_pic_center]: /images/20220828/a1bef9e18ef54e38bf8ae2139fd24cdf.png
[882e63adf5ad4e62a1f8e8010df5cc19.png_pic_center]: /images/20220828/2756d69a7407451389704aee6c769382.png
[23d5cc59152c49609400a5098ab63920.png_pic_center]: /images/20220828/59a094c101a54816b069d39bfcbcb935.png
[ba37f93e237345edaf93500c9576bdab.png_pic_center]: /images/20220828/589499a205694db083c35263eb7f7689.png
[Bubble Sort - GeeksforGeeks]: https://www.geeksforgeeks.org/bubble-sort/
[All Algorithms implemented in Python]: https://github.com/TheAlgorithms/Python