C++實現(xiàn)冒泡排序的多種方式詳解
更新時間：2025年10月13日 09:37:02 作者：無限進步_
冒泡排序是最基礎(chǔ)的排序算法之一,它的核心思想是通過相鄰元素的比較和交換,將較大的元素逐步冒泡到數(shù)組的末尾,今天我們來分析三種不同的冒泡排序?qū)崿F(xiàn)方式,每種都有其獨特之處,需要的朋友可以參考下
引言
冒泡排序是最基礎(chǔ)的排序算法之一，它的核心思想是通過相鄰元素的比較和交換，將較大的元素逐步"冒泡"到數(shù)組的末尾。今天我們來分析三種不同的冒泡排序?qū)崿F(xiàn)方式，每種都有其獨特之處。
算法基礎(chǔ)
冒泡排序的基本原理很簡單：重復(fù)遍歷待排序的數(shù)列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。遍歷數(shù)列的工作重復(fù)進行，直到?jīng)]有再需要交換的元素，這意味著該數(shù)列已經(jīng)排序完成。
時間復(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ù)組 - 計算數(shù)組長度：
int n = sizeof(a) / sizeof(a[0]);通過總字節(jié)數(shù)除以單個元素字節(jié)數(shù)得到元素個數(shù) - 雙重循環(huán)結(jié)構(gòu)：
- 外層循環(huán)控制排序輪數(shù)：
for (int i = 0; i < n-1; i++) - 內(nèi)層循環(huán)進行相鄰元素比較：
for (int j = 0; j < n - 1 - i; j++)
- 外層循環(huán)控制排序輪數(shù)：
- 元素交換：使用臨時變量temp完成兩個元素的交換
特點分析
優(yōu)點：
- 代碼簡潔明了，易于理解
- 邏輯清晰，是學(xué)習(xí)排序算法的入門首選
缺點：
- 沒有優(yōu)化，即使數(shù)組已經(jīng)有序也會繼續(xù)執(zhí)行完整排序過程
- 效率較低，無法提前結(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ā)生交換就說明，無序
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;
}代碼解析
這個版本在基礎(chǔ)版本上增加了一個重要的優(yōu)化：提前終止機制。
- 標(biāo)志變量：
int flag = 1;在每輪排序開始前假設(shè)數(shù)組已經(jīng)有序 - 交換檢測：當(dāng)發(fā)生元素交換時，
flag = 0;標(biāo)記數(shù)組仍無序 - 提前終止：如果一輪排序后flag仍為1，說明沒有發(fā)生交換，數(shù)組已有序，直接退出循環(huán)
特點分析
優(yōu)化效果：
- 對于已經(jīng)有序或接近有序的數(shù)組，效率大幅提升
- 最好情況下時間復(fù)雜度從O(n²)降低到O(n)
實際應(yīng)用價值：
這種優(yōu)化在實際應(yī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ù)組開頭
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ù)組下標(biāo)，展示了C語言指針的強大功能。
- 指針初始化：
int* p = a;指針p指向數(shù)組首地址 - 指針比較：
if (*p > *(p+1))使用指針解引用比較元素值 - 指針交換：通過指針直接操作內(nèi)存完成元素交換
- 指針移動：
p++使指針指向下一個元素
特點分析
技術(shù)特點：
- 展示了指針在數(shù)組操作中的應(yīng)用
- 代碼執(zhí)行效率可能略有提升（依賴編譯器優(yōu)化）
- 更接近底層內(nèi)存操作
學(xué)習(xí)價值：
對于理解C語言指針和內(nèi)存管理很有幫助，是進階學(xué)習(xí)的良好示例。
補充(指針版冒泡排序)
int main()
{
int a[] = { 2,1,5,7,3,9,0,4,6,8 };
int* p = a;
int temp = 0, falg = 0; // 注意：這里有個拼寫錯誤，應(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)記為無序
temp = *p;
*p = *(p + 1);
*(p + 1) = temp;
}
p++; // 指針移動到下一個元素
}
if (flag == 1) // 如果本輪沒有發(fā)生交換
{
break; // 提前結(jié)束排序
}
}
for (int k = 0; k < n; k++)
{
printf("%d ", a[k]);
}
printf("\n");
return 0;
}三種方法對比
| 特性 | 方法一 | 方法二 | 方法三 |
|---|---|---|---|
| 代碼復(fù)雜度 | 簡單 | 中等 | 中等 |
| 執(zhí)行效率 | 穩(wěn)定O(n²) | 最好O(n) | 穩(wěn)定O(n²) |
| 內(nèi)存使用 | 低 | 低 | 低 |
| 適用場景 | 教學(xué)演示 | 實際應(yīng)用 | 指針學(xué)習(xí) |
| 優(yōu)化程度 | 無優(yōu)化 | 提前終止 | 無優(yōu)化 |
總結(jié)
三種冒泡排序?qū)崿F(xiàn)各有特色：
- 方法一最適合算法初學(xué)者，代碼清晰易懂
- 方法二在實際開發(fā)中最實用，具備智能優(yōu)化能力
- 方法三適合想要深入理解指針和內(nèi)存操作的開發(fā)者
雖然冒泡排序在實際應(yīng)用中效率不高，但作為算法學(xué)習(xí)的入門課程，它幫助我們理解排序的基本概念和算法優(yōu)化的重要性。掌握這三種實現(xiàn)方式，能夠為學(xué)習(xí)更復(fù)雜的排序算法打下堅實基礎(chǔ)。
無論選擇哪種實現(xiàn)方式，理解算法背后的思想才是最重要的！
以上就是C++實現(xiàn)冒泡排序的多種方式詳解的詳細內(nèi)容，更多關(guān)于C++冒泡排序?qū)崿F(xiàn)的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要介紹了C++算法與泛型算法（algorithm、numeric）,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-02-02
本文介紹簡體中文Windows操作系統(tǒng)中,C++讀取文本文件中的漢字亂碼情況原因及解決,文中通過代碼和圖文給大家介紹的非常詳細,具有一定的參考價值,需要的朋友可以參考下2024-01-01
C++ Custom Control控件向父窗體發(fā)送對應(yīng)的消息
這篇文章主要介紹了C++ Custom Control控件向父窗體發(fā)送對應(yīng)的消息的相關(guān)資料,需要的朋友可以參考下2015-06-06
本篇文章是對卡特蘭數(shù)及其應(yīng)用進行了詳細的分析介紹，需要的朋友參考下2013-05-05
以下是對c++中冒號和雙冒號的用法進行了介紹，需要的朋友可以過來參考下2013-07-07
這篇文章主要介紹了c++中static的用法詳解,C 語言的 static 關(guān)鍵字有三種用途，具體內(nèi)容詳情大家跟隨腳本之家小編一起學(xué)習(xí)吧2018-05-05
這篇文章主要為大家詳細介紹了C語言分裝實現(xiàn)三子棋游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-05-05
這篇文章主要介紹了C語言的空類型指針,空指針,野指針的詳解及用法示例，介紹了其相關(guān)概念，然后分享了幾種用法，具有一定參考價值。需要的朋友可以了解下。2021-09-09
下面小編就為大家?guī)硪黄獜腃++單例模式到線程安全詳解。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12
這篇文章主要介紹了C++ 中 socket編程實例詳解的相關(guān)資料,需要的朋友可以參考下2017-06-06