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

更新時間：2025年10月13日 09:37:02 作者：無限進步_

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

引言

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

算法基礎

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

時間復雜度：

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

空間復雜度：O(1)

方法一：基礎冒泡排序

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ù)組
計算數(shù)組長度：int n = sizeof(a) / sizeof(a[0]); 通過總字節(jié)數(shù)除以單個元素字節(jié)數(shù)得到元素個數(shù)
雙重循環(huán)結構：
- 外層循環(huán)控制排序輪數(shù)：for (int i = 0; i < n-1; i++)
- 內(nèi)層循環(huán)進行相鄰元素比較：for (int j = 0; j < n - 1 - i; j++)
元素交換：使用臨時變量temp完成兩個元素的交換

特點分析

優(yōu)點：

代碼簡潔明了，易于理解
邏輯清晰，是學習排序算法的入門首選

缺點：

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

方法二：優(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; // 假設這趟已經(jīng)有序了
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (a[j] > a[j + 1])
            {
                flag = 0; // 發(fā)生交換就說明，無序
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
        if (flag == 1) // 這一趟沒交換就說明已經(jīng)有序了，后續(xù)無需排序了
        {
            break;
        }
    }
 
    for (int k = 0; k < n; k++)
    {
        printf("%d ", a[k]);
    }
    printf("\n");
    return 0;
}

代碼解析

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

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

特點分析

優(yōu)化效果：

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

實際應用價值：

這種優(yōu)化在實際應用中非常有價值，因為很多場景下數(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ù)組開頭
        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;
}

代碼解析

這個版本使用指針操作代替數(shù)組下標，展示了C語言指針的強大功能。

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

特點分析

技術特點：

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

學習價值：

對于理解C語言指針和內(nèi)存管理很有幫助，是進階學習的良好示例。

補充(指針版冒泡排序)

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

三種方法對比

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