python算法與數(shù)據(jù)結(jié)構(gòu)之冒泡排序?qū)嵗斀?/h1>
更新時(shí)間:2019年06月22日 09:26:25 作者:Se7eN_HOU
冒泡排序(英語(yǔ):Bubble Sort)是一種簡(jiǎn)單的排序算法。它重復(fù)地遍歷要排序的數(shù)列,一次比較兩個(gè)元素,如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。這篇文章主要介紹了python算法與數(shù)據(jù)結(jié)構(gòu)-冒泡排序(32)的相關(guān)資料,需要的朋友可以參考下
一、冒泡排序介紹
冒泡排序(英語(yǔ):Bubble Sort)是一種簡(jiǎn)單的排序算法。它重復(fù)地遍歷要排序的數(shù)列,一次比較兩個(gè)元素,如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。遍歷數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換,也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
二、冒泡排序原理
- 比較相鄰的元素。如果第一個(gè)比第二個(gè)大,就交換他們兩個(gè)。
- 對(duì)每一對(duì)相鄰元素做同樣的工作,從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這一步做完,最后的元素應(yīng)該會(huì)是最大的數(shù)。
- 針對(duì)所有的元素重復(fù)以上的步驟,除了最后一個(gè)。
- 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟,直到?jīng)]有任何一對(duì)數(shù)字需要比較。
三、冒泡排序圖解






四、冒泡排序總結(jié)
有N個(gè)數(shù)據(jù)需要比較N-1趟
每趟比較N-i次,i表示第幾趟,例如7個(gè)數(shù)據(jù),第四趟需要比較 7-4 = 3次
五、冒泡排序python代碼實(shí)現(xiàn)
def bubble_sort(numlist):
# 需要排列的數(shù)據(jù)個(gè)數(shù)
N = len(numlist)
# i 控制一共需要多少趟 N-1
for i in range(N-1):
# j 控制每趟需要比較多少次(因?yàn)閕是從0開(kāi)始,所以N-i-1)
for j in range(N-i-1):
# 判斷j和j+1兩個(gè)位置的數(shù)據(jù)大小
if numlist[j]>numlist[j+1]:
# 交換(交換的代碼有很多種寫(xiě)法)
temp = numlist[j]
numlist[j] = numlist[j+1]
numlist[j+1] = temp
list = [19,2,13,8,34,25,7]
print("排序前l(fā)ist = %s"%list)
bubble_sort(list)
print("排序后list = %s"%list)
運(yùn)行結(jié)果為:
排序前l(fā)ist = [19, 2, 13, 8, 34, 25, 7]
排序后list = [2, 7, 8, 13, 19, 25, 34]
六、冒泡排序C語(yǔ)言代碼實(shí)現(xiàn)
#include <stdio.h>
// 創(chuàng)建一個(gè)冒泡函數(shù),需要傳遞一個(gè)數(shù)組,和數(shù)組的長(zhǎng)度
void bubble_sort(int array[],int arrayLength)
{
// i 控制一共需要循環(huán)多少趟,
for (int i=0; i<arrayLength-1; i++)
{
// j 控制每趟循環(huán)多少次
for (int j=0; j<arrayLength-i-1; j++)
{
//判斷j和j+1位置上數(shù)的大小
if (array[j]>array[j+1])
{
//交換
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
int main(int argc, const char * argv[])
{
// 函數(shù)的聲明
void bubble_sort(int array[],int arrayLength);
// 創(chuàng)建一個(gè)數(shù)組
int numArray[] = {19,2,13,8,34,25,7};
//進(jìn)行排序
bubble_sort(numArray,7);
printf("打印排序后的數(shù)組是:\n");
for (int i=0; i<7; i++)
{
printf("%d ",numArray[i]);
}
return 0;
}
運(yùn)算結(jié)果為:
打印排序后的數(shù)組是:
2 7 8 13 19 25 34
七、冒泡排序的優(yōu)化
通過(guò)上面的案例我們已經(jīng)知道冒泡排序的原理和實(shí)現(xiàn)過(guò)程,但是在處理一些特殊數(shù)據(jù)上的時(shí)候,我們還可以對(duì)冒泡排序優(yōu)化,例如:一個(gè)數(shù)組本來(lái)就是有序,1,2,3,4,5,6,7,這樣的一個(gè)數(shù)組已經(jīng)是正確的順序的,我們只需要比較一趟后,發(fā)現(xiàn)這一趟所有的數(shù)據(jù)都沒(méi)有發(fā)生改變,就說(shuō)明這已經(jīng)是一個(gè)正確的順序的,后面的循環(huán)就沒(méi)必要循環(huán)下去了,這樣便能提高程序的效率,而我們只需要在冒泡排序的代碼中,判斷是否這一樣都沒(méi)發(fā)生交換即可。
python代碼實(shí)現(xiàn)如下:
def bubble_sort(numlist):
# 需要排列的數(shù)據(jù)個(gè)數(shù)
N = len(numlist)
# i 控制一共需要多少趟 N-1
for i in range(N-1):
# 定義一個(gè)變量,用于記錄是否在本趟中發(fā)生了交換
isChange = 0
# j 控制每趟需要比較多少次(因?yàn)閕是從0開(kāi)始,所以N-i-1)
for j in range(N-i-1):
# 判斷j和j+1兩個(gè)位置的數(shù)據(jù)大小
if numlist[j]>numlist[j+1]:
# 交換(交換的代碼有很多種寫(xiě)法)
temp = numlist[j]
numlist[j] = numlist[j+1]
numlist[j+1] = temp
# 只要發(fā)生了交換,我們就改變isChange的值為1
isChange = 1
# 只要isChange =0說(shuō)明已經(jīng)是正確順序了,直接break即可
if isChange == 0:
break
list = [19,2,13,8,34,25,7]
print("排序前l(fā)ist = %s"%list)
bubble_sort(list)
print("排序后list = %s"%list)
運(yùn)行結(jié)果為:
排序前l(fā)ist = [19, 2, 13, 8, 34, 25, 7]
排序后list = [2, 7, 8, 13, 19, 25, 34]
C語(yǔ)言代碼實(shí)現(xiàn)如下:
#include <stdio.h>
// 創(chuàng)建一個(gè)冒泡函數(shù),需要傳遞一個(gè)數(shù)組,和數(shù)組的長(zhǎng)度
void bubble_sort(int array[],int arrayLength)
{
// i 控制一共需要循環(huán)多少趟,
for (int i=0; i<arrayLength-1; i++)
{
//定義一個(gè)變量,用于記錄是否在本趟中發(fā)生了改變
int isChange = 0;
// j 控制每趟循環(huán)多少次
for (int j=0; j<arrayLength-i-1; j++)
{
//判斷j和j+1位置上d數(shù)的大小
if (array[j]>array[j+1])
{
//交換
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
// 只要發(fā)生了交換,我們就改變isChange的值為1
isChange = 1;
}
}
// 只要isChange =0說(shuō)明已經(jīng)是正確順序了,直接break即可
if (isChange == 0)
{
break;
}
}
}
int main(int argc, const char * argv[])
{
// 函數(shù)的聲明
void bubble_sort(int array[],int arrayLength);
// 創(chuàng)建一個(gè)數(shù)組
int numArray[] = {19,2,13,8,34,25,7};
//進(jìn)行排序
bubble_sort(numArray,7);
printf("打印排序后的數(shù)組是:\n");
for (int i=0; i<7; i++)
{
printf("%d ",numArray[i]);
}
return 0;
}
運(yùn)行結(jié)果為:
打印排序后的數(shù)組是:
2 7 8 13 19 25 34
八、冒泡排序的時(shí)間復(fù)雜度
最優(yōu)時(shí)間復(fù)雜度:O(n) (表示遍歷一次發(fā)現(xiàn)沒(méi)有任何可以交換的元素,排序結(jié)束。)
最壞時(shí)間復(fù)雜度:O(n2)
九、冒泡排序算法的穩(wěn)定性
冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較,交換也發(fā)生在這兩個(gè)元素之間。所以,如果兩個(gè)元素相等,是不會(huì)再交換的;如果兩個(gè)相等的元素沒(méi)有相鄰,那么即使通過(guò)前面的兩兩交換把兩個(gè)相鄰起來(lái),這時(shí)候也不會(huì)交換,所以相同元素的前后順序并沒(méi)有改變,所以冒泡排序是一種穩(wěn)定排序算法。
侯哥語(yǔ)錄:我曾經(jīng)是一個(gè)職業(yè)教育者,現(xiàn)在是一個(gè)自由開(kāi)發(fā)者。我希望我的分享可以和更多人一起進(jìn)步。分享一段我喜歡的話(huà)給大家:"我所理解的自由不是想干什么就干什么,而是想不干什么就不干什么。當(dāng)你還沒(méi)有能力說(shuō)不得時(shí)候,就努力讓自己變得強(qiáng)大,擁有說(shuō)不得權(quán)利。"
總結(jié)
以上所述是小編給大家介紹的python算法與數(shù)據(jù)結(jié)構(gòu)之冒泡排序?qū)嵗斀?,希望?duì)大家有所幫助,如果大家有任何疑問(wèn)歡迎給我留言,小編會(huì)及時(shí)回復(fù)大家的!
相關(guān)文章
-
python爬蟲(chóng)之請(qǐng)求模塊urllib的基本使用
urllib是python內(nèi)置的HTTP請(qǐng)求庫(kù),是一個(gè)用來(lái)處理網(wǎng)絡(luò)請(qǐng)求的python標(biāo)準(zhǔn)庫(kù),下面這篇文章主要給大家介紹了關(guān)于python爬蟲(chóng)之請(qǐng)求模塊urllib的基本使用,需要的朋友可以參考下 2022-04-04
-
pyqt6實(shí)現(xiàn)關(guān)閉窗口前彈出確認(rèn)框的示例代碼
本文主要介紹了pyqt6實(shí)現(xiàn)關(guān)閉窗口前彈出確認(rèn)框的示例代碼,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧 2024-02-02
-
一文向您詳細(xì)介紹指令 python -m pip install的用法和功能
通過(guò)本文的介紹,我們?cè)敿?xì)了解了python -m pip install命令的用法和功能,從基本用法到安裝特定版本的包、從其他源安裝包、升級(jí)和卸載包,再到使用requirements.txt管理依賴(lài),我們逐步深入了解了pip的強(qiáng)大功能,感興趣的朋友跟隨小編一起看看吧 2024-07-07
-
pip 錯(cuò)誤unused-command-line-argument-hard-error-in-future解決辦法
這篇文章主要介紹了Python包管理器pip安裝軟件時(shí)出現(xiàn)unused-command-line-argument-hard-error-in-future錯(cuò)誤的解決辦法,需要的朋友可以參考下 2014-06-06
-
Python中print函數(shù)語(yǔ)法格式以及各參數(shù)舉例詳解
這篇文章主要給大家介紹了關(guān)于Python中print函數(shù)語(yǔ)法格式以及各參數(shù)舉例詳解的相關(guān)資料,print()函數(shù)用于將指定的字符串或?qū)ο?通常是字符串)輸出到屏幕或文件中,需要的朋友可以參考下 2023-10-10
-
把大數(shù)據(jù)數(shù)字口語(yǔ)化(python與js)兩種實(shí)現(xiàn)
當(dāng)出現(xiàn)萬(wàn)以上的整型數(shù)字時(shí),經(jīng)常要把它們口語(yǔ)化比較直觀(guān)。下面分享兩段代碼,python與js的 2013-02-02
-
Python實(shí)現(xiàn)微信消息防撤回功能的實(shí)例代碼
這篇文章主要介紹了Python實(shí)現(xiàn)微信消息防撤回 ,需要的朋友可以參考下 2019-04-04
最新評(píng)論
一、冒泡排序介紹
冒泡排序(英語(yǔ):Bubble Sort)是一種簡(jiǎn)單的排序算法。它重復(fù)地遍歷要排序的數(shù)列,一次比較兩個(gè)元素,如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。遍歷數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換,也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
二、冒泡排序原理
- 比較相鄰的元素。如果第一個(gè)比第二個(gè)大,就交換他們兩個(gè)。
- 對(duì)每一對(duì)相鄰元素做同樣的工作,從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這一步做完,最后的元素應(yīng)該會(huì)是最大的數(shù)。
- 針對(duì)所有的元素重復(fù)以上的步驟,除了最后一個(gè)。
- 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟,直到?jīng)]有任何一對(duì)數(shù)字需要比較。
三、冒泡排序圖解






四、冒泡排序總結(jié)
有N個(gè)數(shù)據(jù)需要比較N-1趟
每趟比較N-i次,i表示第幾趟,例如7個(gè)數(shù)據(jù),第四趟需要比較 7-4 = 3次
五、冒泡排序python代碼實(shí)現(xiàn)
def bubble_sort(numlist):
# 需要排列的數(shù)據(jù)個(gè)數(shù)
N = len(numlist)
# i 控制一共需要多少趟 N-1
for i in range(N-1):
# j 控制每趟需要比較多少次(因?yàn)閕是從0開(kāi)始,所以N-i-1)
for j in range(N-i-1):
# 判斷j和j+1兩個(gè)位置的數(shù)據(jù)大小
if numlist[j]>numlist[j+1]:
# 交換(交換的代碼有很多種寫(xiě)法)
temp = numlist[j]
numlist[j] = numlist[j+1]
numlist[j+1] = temp
list = [19,2,13,8,34,25,7]
print("排序前l(fā)ist = %s"%list)
bubble_sort(list)
print("排序后list = %s"%list)
運(yùn)行結(jié)果為:
排序前l(fā)ist = [19, 2, 13, 8, 34, 25, 7]
排序后list = [2, 7, 8, 13, 19, 25, 34]
六、冒泡排序C語(yǔ)言代碼實(shí)現(xiàn)
#include <stdio.h>
// 創(chuàng)建一個(gè)冒泡函數(shù),需要傳遞一個(gè)數(shù)組,和數(shù)組的長(zhǎng)度
void bubble_sort(int array[],int arrayLength)
{
// i 控制一共需要循環(huán)多少趟,
for (int i=0; i<arrayLength-1; i++)
{
// j 控制每趟循環(huán)多少次
for (int j=0; j<arrayLength-i-1; j++)
{
//判斷j和j+1位置上數(shù)的大小
if (array[j]>array[j+1])
{
//交換
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
int main(int argc, const char * argv[])
{
// 函數(shù)的聲明
void bubble_sort(int array[],int arrayLength);
// 創(chuàng)建一個(gè)數(shù)組
int numArray[] = {19,2,13,8,34,25,7};
//進(jìn)行排序
bubble_sort(numArray,7);
printf("打印排序后的數(shù)組是:\n");
for (int i=0; i<7; i++)
{
printf("%d ",numArray[i]);
}
return 0;
}
運(yùn)算結(jié)果為:
打印排序后的數(shù)組是:
2 7 8 13 19 25 34
七、冒泡排序的優(yōu)化
通過(guò)上面的案例我們已經(jīng)知道冒泡排序的原理和實(shí)現(xiàn)過(guò)程,但是在處理一些特殊數(shù)據(jù)上的時(shí)候,我們還可以對(duì)冒泡排序優(yōu)化,例如:一個(gè)數(shù)組本來(lái)就是有序,1,2,3,4,5,6,7,這樣的一個(gè)數(shù)組已經(jīng)是正確的順序的,我們只需要比較一趟后,發(fā)現(xiàn)這一趟所有的數(shù)據(jù)都沒(méi)有發(fā)生改變,就說(shuō)明這已經(jīng)是一個(gè)正確的順序的,后面的循環(huán)就沒(méi)必要循環(huán)下去了,這樣便能提高程序的效率,而我們只需要在冒泡排序的代碼中,判斷是否這一樣都沒(méi)發(fā)生交換即可。
python代碼實(shí)現(xiàn)如下:
def bubble_sort(numlist):
# 需要排列的數(shù)據(jù)個(gè)數(shù)
N = len(numlist)
# i 控制一共需要多少趟 N-1
for i in range(N-1):
# 定義一個(gè)變量,用于記錄是否在本趟中發(fā)生了交換
isChange = 0
# j 控制每趟需要比較多少次(因?yàn)閕是從0開(kāi)始,所以N-i-1)
for j in range(N-i-1):
# 判斷j和j+1兩個(gè)位置的數(shù)據(jù)大小
if numlist[j]>numlist[j+1]:
# 交換(交換的代碼有很多種寫(xiě)法)
temp = numlist[j]
numlist[j] = numlist[j+1]
numlist[j+1] = temp
# 只要發(fā)生了交換,我們就改變isChange的值為1
isChange = 1
# 只要isChange =0說(shuō)明已經(jīng)是正確順序了,直接break即可
if isChange == 0:
break
list = [19,2,13,8,34,25,7]
print("排序前l(fā)ist = %s"%list)
bubble_sort(list)
print("排序后list = %s"%list)
運(yùn)行結(jié)果為:
排序前l(fā)ist = [19, 2, 13, 8, 34, 25, 7]
排序后list = [2, 7, 8, 13, 19, 25, 34]
C語(yǔ)言代碼實(shí)現(xiàn)如下:
#include <stdio.h>
// 創(chuàng)建一個(gè)冒泡函數(shù),需要傳遞一個(gè)數(shù)組,和數(shù)組的長(zhǎng)度
void bubble_sort(int array[],int arrayLength)
{
// i 控制一共需要循環(huán)多少趟,
for (int i=0; i<arrayLength-1; i++)
{
//定義一個(gè)變量,用于記錄是否在本趟中發(fā)生了改變
int isChange = 0;
// j 控制每趟循環(huán)多少次
for (int j=0; j<arrayLength-i-1; j++)
{
//判斷j和j+1位置上d數(shù)的大小
if (array[j]>array[j+1])
{
//交換
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
// 只要發(fā)生了交換,我們就改變isChange的值為1
isChange = 1;
}
}
// 只要isChange =0說(shuō)明已經(jīng)是正確順序了,直接break即可
if (isChange == 0)
{
break;
}
}
}
int main(int argc, const char * argv[])
{
// 函數(shù)的聲明
void bubble_sort(int array[],int arrayLength);
// 創(chuàng)建一個(gè)數(shù)組
int numArray[] = {19,2,13,8,34,25,7};
//進(jìn)行排序
bubble_sort(numArray,7);
printf("打印排序后的數(shù)組是:\n");
for (int i=0; i<7; i++)
{
printf("%d ",numArray[i]);
}
return 0;
}
運(yùn)行結(jié)果為:
打印排序后的數(shù)組是:
2 7 8 13 19 25 34
八、冒泡排序的時(shí)間復(fù)雜度
最優(yōu)時(shí)間復(fù)雜度:O(n) (表示遍歷一次發(fā)現(xiàn)沒(méi)有任何可以交換的元素,排序結(jié)束。)
最壞時(shí)間復(fù)雜度:O(n2)
九、冒泡排序算法的穩(wěn)定性
冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較,交換也發(fā)生在這兩個(gè)元素之間。所以,如果兩個(gè)元素相等,是不會(huì)再交換的;如果兩個(gè)相等的元素沒(méi)有相鄰,那么即使通過(guò)前面的兩兩交換把兩個(gè)相鄰起來(lái),這時(shí)候也不會(huì)交換,所以相同元素的前后順序并沒(méi)有改變,所以冒泡排序是一種穩(wěn)定排序算法。
侯哥語(yǔ)錄:我曾經(jīng)是一個(gè)職業(yè)教育者,現(xiàn)在是一個(gè)自由開(kāi)發(fā)者。我希望我的分享可以和更多人一起進(jìn)步。分享一段我喜歡的話(huà)給大家:"我所理解的自由不是想干什么就干什么,而是想不干什么就不干什么。當(dāng)你還沒(méi)有能力說(shuō)不得時(shí)候,就努力讓自己變得強(qiáng)大,擁有說(shuō)不得權(quán)利。"
總結(jié)
以上所述是小編給大家介紹的python算法與數(shù)據(jù)結(jié)構(gòu)之冒泡排序?qū)嵗斀?,希望?duì)大家有所幫助,如果大家有任何疑問(wèn)歡迎給我留言,小編會(huì)及時(shí)回復(fù)大家的!
相關(guān)文章
python爬蟲(chóng)之請(qǐng)求模塊urllib的基本使用
urllib是python內(nèi)置的HTTP請(qǐng)求庫(kù),是一個(gè)用來(lái)處理網(wǎng)絡(luò)請(qǐng)求的python標(biāo)準(zhǔn)庫(kù),下面這篇文章主要給大家介紹了關(guān)于python爬蟲(chóng)之請(qǐng)求模塊urllib的基本使用,需要的朋友可以參考下2022-04-04
pyqt6實(shí)現(xiàn)關(guān)閉窗口前彈出確認(rèn)框的示例代碼
本文主要介紹了pyqt6實(shí)現(xiàn)關(guān)閉窗口前彈出確認(rèn)框的示例代碼,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2024-02-02
一文向您詳細(xì)介紹指令 python -m pip install的用法和功能
通過(guò)本文的介紹,我們?cè)敿?xì)了解了python -m pip install命令的用法和功能,從基本用法到安裝特定版本的包、從其他源安裝包、升級(jí)和卸載包,再到使用requirements.txt管理依賴(lài),我們逐步深入了解了pip的強(qiáng)大功能,感興趣的朋友跟隨小編一起看看吧2024-07-07
pip 錯(cuò)誤unused-command-line-argument-hard-error-in-future解決辦法
這篇文章主要介紹了Python包管理器pip安裝軟件時(shí)出現(xiàn)unused-command-line-argument-hard-error-in-future錯(cuò)誤的解決辦法,需要的朋友可以參考下2014-06-06
Python中print函數(shù)語(yǔ)法格式以及各參數(shù)舉例詳解
這篇文章主要給大家介紹了關(guān)于Python中print函數(shù)語(yǔ)法格式以及各參數(shù)舉例詳解的相關(guān)資料,print()函數(shù)用于將指定的字符串或?qū)ο?通常是字符串)輸出到屏幕或文件中,需要的朋友可以參考下2023-10-10
把大數(shù)據(jù)數(shù)字口語(yǔ)化(python與js)兩種實(shí)現(xiàn)
當(dāng)出現(xiàn)萬(wàn)以上的整型數(shù)字時(shí),經(jīng)常要把它們口語(yǔ)化比較直觀(guān)。下面分享兩段代碼,python與js的2013-02-02
Python實(shí)現(xiàn)微信消息防撤回功能的實(shí)例代碼
這篇文章主要介紹了Python實(shí)現(xiàn)微信消息防撤回 ,需要的朋友可以參考下2019-04-04

