C++算法之冒泡排序

一、基本思想

試想一下，如果在上體育課的時候，通常學生都會隨意站成一列，但是體育老師會幫忙調(diào)整學生的站位使得最終順序是按照身高排序的。那么，回憶一下體育老師是如何調(diào)整順序的呢？

假設體育老師想將學生從左到右按照身高從矮到高排序。通常情況下，他會從左到右掃視學生的身高。如果左邊有一個同學，個子比右邊的同學高，他就要將其進行調(diào)整。具體調(diào)整方法是：

如果一個同學比他右邊的同學高，就讓這兩個同學交換位置。
如果交換過后，這個同學仍然比新的右邊的同學高，那么繼續(xù)交換，直到他不在比右邊的同學高。這樣進行了若干次以后，隊列就按照身高排好序了。

那么，如何嚴謹?shù)乇硎觥绑w育老師排序方法”，并對于任意給定的序列，都能將其從小到大排好序呢？

回憶在介紹選擇排序的時候，我們的具體思路如下：

我們發(fā)現(xiàn)，這里我們使用了將原問題轉換為規(guī)模更小的子問題的思路。

所以在選擇排序的過程，相當于每次將當前序列未排序部分的最小元素歸位，將未排序的序列長度縮小一位。同樣，如果我們能夠通過某種方式，把序列中的最大值移動到序列最后面，也可以起到將未排序序列長度縮小一位的效果。

通過“體育老師交換方法”，使得每次我們都能把最大值移動到序列的最后一位。

利用上面的步驟進行問題轉換，將未排序的序列長度縮減一個。

這就是冒泡排序的具體思路，而上面提到的“將最大值移動到最后一位”的操作，就叫做冒泡操作。

二、步驟

冒泡排序

1、冒泡排序分為n-1個階段。
在第1個階段，通過“冒泡”，將前n個元素的最大值移動到序列的最后一位。此時只剩前n-1個元素未排序。
2、在第i個階段，此時序列前n-i+1個元素未排序。通過“冒泡”，我們將前n-i+1個元素中的最大值移動到最后一位。此時只剩前n-i個元素未排好序。
3、最終到第n-1個階段，前2個元素未排序。將其中的較大值移動到后一位，則整個序列排序完畢。
4、在上面的算法過程中，我們提到“冒泡”將序列中的最大值移動到最后一位。下面，我們介紹一下“冒泡”的過程：

冒泡過程

對于長度為n的序列，如何將其中的最大值移動到最后一位？

就像上面說的那樣，如果相鄰兩個元素（如下圖2和3），第一個大，第二個小，那么，將兩個元素交換。

如果我們對一段序列從左到右連續(xù)做如下交換操作：

if (a[i] > a[i + 1]) swap(a[i], a[i + 1])；

它的效果相當于將每一個”極大值“元素，移動到能到達的最遠的位置。

自然，序列中的最大值，也是一個極大值，而它能被移動到的最遠的位置，就是序列的最后一位。

所以，如果對于序列的1~n位，想將其中的最大元素”冒泡“到最后一位，那么就需要從第1位開始，一直到第n-1位，依次進行上面的交換過程。

三、代碼

代碼如下（示例）：

#include <bits/stdc++.h>
#define N 1010
using namespace std;
int n = 6; // 待排序的元素個數(shù)為6
int a[N] = {0, 2, 3, 2, 11, 7, 6}; // 待排序元素 {2,3,2,11,7,6}

int main() {   
    // 連續(xù)交換過程
    // 一共n-1個階段，在第i個階段，未排序序列長度從n-i+1到n-i。
    for (int i = 1; i < n; ++i) {  
        // 將序列從1到n-i+1的最大值，移到n-i+1的位置
        for (int j = 1; j <= n - i; ++j)
            // 其中j枚舉的是前后交換元素的前一個元素序號
            // TODO 請補全代碼完成階段的冒泡過程
            if (a[j] > a[j + 1]) 
                swap(a[j], a[j + 1]);
    }
    
    // 輸出
    for (int i = 1; i <= n; ++i) cout << a[i] << ' ';
    cout << endl;
    return 0;
}

四、復雜度分析

從代碼中，我們可以看到冒泡排序的主干部分有兩層循環(huán)，并且每一層的循環(huán)次數(shù)都在O(n)左右的數(shù)量級。所以完整的冒泡排序時間復雜度是O(n^2)文章來源地址http://www.zghlxwxcb.cn/news/detail-630535.html

到了這里，關于C++算法之冒泡排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！