快捷導(dǎo)航

C++實(shí)現(xiàn)冒泡排序的多種方式詳解

更新時(shí)間：2025年10月13日 09:37:02 作者：無(wú)限進(jìn)步_

冒泡排序是最基礎(chǔ)的排序算法之一,它的核心思想是通過相鄰元素的比較和交換,將較大的元素逐步冒泡到數(shù)組的末尾,今天我們來(lái)分析三種不同的冒泡排序?qū)崿F(xiàn)方式,每種都有其獨(dú)特之處,需要的朋友可以參考下

引言

冒泡排序是最基礎(chǔ)的排序算法之一，它的核心思想是通過相鄰元素的比較和交換，將較大的元素逐步"冒泡"到數(shù)組的末尾。今天我們來(lái)分析三種不同的冒泡排序?qū)崿F(xiàn)方式，每種都有其獨(dú)特之處。

算法基礎(chǔ)

冒泡排序的基本原理很簡(jiǎn)單：重復(fù)遍歷待排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過來(lái)。遍歷數(shù)列的工作重復(fù)進(jìn)行，直到?jīng)]有再需要交換的元素，這意味著該數(shù)列已經(jīng)排序完成。

時(shí)間復(fù)雜度：

最壞情況：O(n²)
最好情況：O(n) - 優(yōu)化后
平均情況：O(n²)

空間復(fù)雜度：O(1)

方法一：基礎(chǔ)冒泡排序

int main()
{
    int a[] = { 2,1,5,7,3,9,0,4,6,8 };
    int temp = 0;
    int n = sizeof(a) / sizeof(a[0]);
    printf("%d\n",n);
    
    for (int i = 0; i < n-1; i++)
    {
        for (int j = 0; j < n - 1 - i; j++)
        {
            if ( a[j] > a[j+1] )
            {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
 
    for (int k = 0; k < n; k++)
    {
        printf("%d ", a[k]);
    }
    printf("\n");
    return 0;
}

代碼解析

數(shù)組初始化：int a[] = { 2,1,5,7,3,9,0,4,6,8 }; 創(chuàng)建待排序數(shù)組
計(jì)算數(shù)組長(zhǎng)度：int n = sizeof(a) / sizeof(a[0]); 通過總字節(jié)數(shù)除以單個(gè)元素字節(jié)數(shù)得到元素個(gè)數(shù)
雙重循環(huán)結(jié)構(gòu)：
- 外層循環(huán)控制排序輪數(shù)：for (int i = 0; i < n-1; i++)
- 內(nèi)層循環(huán)進(jìn)行相鄰元素比較：for (int j = 0; j < n - 1 - i; j++)
元素交換：使用臨時(shí)變量temp完成兩個(gè)元素的交換

特點(diǎn)分析

優(yōu)點(diǎn)：

代碼簡(jiǎn)潔明了，易于理解
邏輯清晰，是學(xué)習(xí)排序算法的入門首選

缺點(diǎn)：

沒有優(yōu)化，即使數(shù)組已經(jīng)有序也會(huì)繼續(xù)執(zhí)行完整排序過程
效率較低，無(wú)法提前結(jié)束

方法二：優(yōu)化版冒泡排序

int main()
{
    int a[] = { 2,1,5,7,3,9,0,4,6,8 };
    int temp = 0, falg = 0;
    int n = sizeof(a) / sizeof(a[0]);
    printf("%d\n", n);
    
    for (int i = 0; i < n - 1; i++)
    {
        int flag = 1; // 假設(shè)這趟已經(jīng)有序了
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (a[j] > a[j + 1])
            {
                flag = 0; // 發(fā)生交換就說(shuō)明，無(wú)序
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
        if (flag == 1) // 這一趟沒交換就說(shuō)明已經(jīng)有序了，后續(xù)無(wú)需排序了
        {
            break;
        }
    }
 
    for (int k = 0; k < n; k++)
    {
        printf("%d ", a[k]);
    }
    printf("\n");
    return 0;
}

代碼解析

這個(gè)版本在基礎(chǔ)版本上增加了一個(gè)重要的優(yōu)化：提前終止機(jī)制。

標(biāo)志變量：int flag = 1; 在每輪排序開始前假設(shè)數(shù)組已經(jīng)有序
交換檢測(cè)：當(dāng)發(fā)生元素交換時(shí)，flag = 0; 標(biāo)記數(shù)組仍無(wú)序
提前終止：如果一輪排序后flag仍為1，說(shuō)明沒有發(fā)生交換，數(shù)組已有序，直接退出循環(huán)

特點(diǎn)分析

優(yōu)化效果：

對(duì)于已經(jīng)有序或接近有序的數(shù)組，效率大幅提升
最好情況下時(shí)間復(fù)雜度從O(n²)降低到O(n)

實(shí)際應(yīng)用價(jià)值：

這種優(yōu)化在實(shí)際應(yīng)用中非常有價(jià)值，因?yàn)楹芏鄨?chǎng)景下數(shù)據(jù)可能已經(jīng)部分有序。

方法三：指針版冒泡排序

int main()
{
    int a[] = { 2,1,5,7,3,9,0,4,6,8 };
    int* p = a;
    int temp = 0, falg = 0;
    int n = sizeof(a) / sizeof(a[0]);
    printf("%d\n", n);
    
    for (int i = 0; i < n - 1; i++)
    {
        p = a; // 每趟開始時(shí)重置指針到數(shù)組開頭
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (*p > *(p+1))
            {
                temp = *p;
                *p = *(p + 1);
                *(p + 1) = temp;
            }
            p++; // 指針后移
        }
    }
 
    for (int k = 0; k < n; k++)
    {
        printf("%d ", a[k]);
    }
    printf("\n");
    return 0;
}

代碼解析

這個(gè)版本使用指針操作代替數(shù)組下標(biāo)，展示了C語(yǔ)言指針的強(qiáng)大功能。

指針初始化：int* p = a; 指針p指向數(shù)組首地址
指針比較：if (*p > *(p+1)) 使用指針解引用比較元素值
指針交換：通過指針直接操作內(nèi)存完成元素交換
指針移動(dòng)：p++ 使指針指向下一個(gè)元素

特點(diǎn)分析

技術(shù)特點(diǎn)：

展示了指針在數(shù)組操作中的應(yīng)用
代碼執(zhí)行效率可能略有提升（依賴編譯器優(yōu)化）
更接近底層內(nèi)存操作

學(xué)習(xí)價(jià)值：

對(duì)于理解C語(yǔ)言指針和內(nèi)存管理很有幫助，是進(jìn)階學(xué)習(xí)的良好示例。

補(bǔ)充(指針版冒泡排序)

int main()
{
    int a[] = { 2,1,5,7,3,9,0,4,6,8 };
    int* p = a;
    int temp = 0, falg = 0;  // 注意：這里有個(gè)拼寫錯(cuò)誤，應(yīng)該是flag
    int n = sizeof(a) / sizeof(a[0]);
    printf("%d\n", n);
    
    for (int i = 0; i < n - 1; i++)
    {
        int flag = 1;  // 每輪開始前假設(shè)數(shù)組已有序
        p = a;  // 重置指針到數(shù)組開頭
        
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (*p > *(p+1))  // 使用指針比較相鄰元素
            {
                flag = 0;  // 發(fā)生交換，標(biāo)記為無(wú)序
                temp = *p;
                *p = *(p + 1);
                *(p + 1) = temp;
            }
            p++;  // 指針移動(dòng)到下一個(gè)元素
        }
        
        if (flag == 1)  // 如果本輪沒有發(fā)生交換
        {
            break;  // 提前結(jié)束排序
        }
    }
 
    for (int k = 0; k < n; k++)
    {
        printf("%d ", a[k]);
    }
    printf("\n");
    return 0;
}

三種方法對(duì)比

特性	方法一	方法二	方法三
代碼復(fù)雜度	簡(jiǎn)單	中等	中等
執(zhí)行效率	穩(wěn)定O(n²)	最好O(n)	穩(wěn)定O(n²)
內(nèi)存使用	低	低	低
適用場(chǎng)景	教學(xué)演示	實(shí)際應(yīng)用	指針學(xué)習(xí)
優(yōu)化程度	無(wú)優(yōu)化	提前終止	無(wú)優(yōu)化

總結(jié)

三種冒泡排序?qū)崿F(xiàn)各有特色：

方法一最適合算法初學(xué)者，代碼清晰易懂
方法二在實(shí)際開發(fā)中最實(shí)用，具備智能優(yōu)化能力
方法三適合想要深入理解指針和內(nèi)存操作的開發(fā)者

雖然冒泡排序在實(shí)際應(yīng)用中效率不高，但作為算法學(xué)習(xí)的入門課程，它幫助我們理解排序的基本概念和算法優(yōu)化的重要性。掌握這三種實(shí)現(xiàn)方式，能夠?yàn)閷W(xué)習(xí)更復(fù)雜的排序算法打下堅(jiān)實(shí)基礎(chǔ)。

無(wú)論選擇哪種實(shí)現(xiàn)方式，理解算法背后的思想才是最重要的！

以上就是C++實(shí)現(xiàn)冒泡排序的多種方式詳解的詳細(xì)內(nèi)容，更多關(guān)于C++冒泡排序?qū)崿F(xiàn)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: