您好,登錄后才能下訂單哦!
小編給大家分享一下python算法與數(shù)據(jù)結(jié)構(gòu)之冒泡排序的示例分析,希望大家閱讀完這篇文章之后都有所收獲,下面讓我們一起去探討吧!
冒泡排序(英語:Bubble Sort)是一種簡單的排序算法。它重復地遍歷要排序的數(shù)列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。遍歷數(shù)列的工作是重復地進行直到?jīng)]有再需要交換,也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。
對每一對相鄰元素做同樣的工作,從開始第一對到結(jié)尾的最后一對。這一步做完,最后的元素應該會是最大的數(shù)。
針對所有的元素重復以上的步驟,除了最后一個。
持續(xù)每次對越來越少的元素重復上面的步驟,直到?jīng)]有任何一對數(shù)字需要比較。
有N個數(shù)據(jù)需要比較N-1趟
每趟比較N-i次,i表示第幾趟,例如7個數(shù)據(jù),第四趟需要比較 7-4 = 3次
def bubble_sort(numlist): # 需要排列的數(shù)據(jù)個數(shù) N = len(numlist) # i 控制一共需要多少趟 N-1 for i in range(N-1): # j 控制每趟需要比較多少次(因為i是從0開始,所以N-i-1) for j in range(N-i-1): # 判斷j和j+1兩個位置的數(shù)據(jù)大小 if numlist[j]>numlist[j+1]: # 交換(交換的代碼有很多種寫法) 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)
運行結(jié)果為:
排序前l(fā)ist = [19, 2, 13, 8, 34, 25, 7]
排序后list = [2, 7, 8, 13, 19, 25, 34]
#include <stdio.h> // 創(chuàng)建一個冒泡函數(shù),需要傳遞一個數(shù)組,和數(shù)組的長度 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)建一個數(shù)組 int numArray[] = {19,2,13,8,34,25,7}; //進行排序 bubble_sort(numArray,7); printf("打印排序后的數(shù)組是:\n"); for (int i=0; i<7; i++) { printf("%d ",numArray[i]); } return 0; }
運算結(jié)果為:
打印排序后的數(shù)組是:
2 7 8 13 19 25 34
通過上面的案例我們已經(jīng)知道冒泡排序的原理和實現(xiàn)過程,但是在處理一些特殊數(shù)據(jù)上的時候,我們還可以對冒泡排序優(yōu)化,例如:一個數(shù)組本來就是有序,1,2,3,4,5,6,7,這樣的一個數(shù)組已經(jīng)是正確的順序的,我們只需要比較一趟后,發(fā)現(xiàn)這一趟所有的數(shù)據(jù)都沒有發(fā)生改變,就說明這已經(jīng)是一個正確的順序的,后面的循環(huán)就沒必要循環(huán)下去了,這樣便能提高程序的效率,而我們只需要在冒泡排序的代碼中,判斷是否這一樣都沒發(fā)生交換即可。
python代碼實現(xiàn)如下:
def bubble_sort(numlist): # 需要排列的數(shù)據(jù)個數(shù) N = len(numlist) # i 控制一共需要多少趟 N-1 for i in range(N-1): # 定義一個變量,用于記錄是否在本趟中發(fā)生了交換 isChange = 0 # j 控制每趟需要比較多少次(因為i是從0開始,所以N-i-1) for j in range(N-i-1): # 判斷j和j+1兩個位置的數(shù)據(jù)大小 if numlist[j]>numlist[j+1]: # 交換(交換的代碼有很多種寫法) temp = numlist[j] numlist[j] = numlist[j+1] numlist[j+1] = temp # 只要發(fā)生了交換,我們就改變isChange的值為1 isChange = 1 # 只要isChange =0說明已經(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)
運行結(jié)果為:
排序前l(fā)ist = [19, 2, 13, 8, 34, 25, 7]
排序后list = [2, 7, 8, 13, 19, 25, 34]
C語言代碼實現(xiàn)如下:
#include <stdio.h> // 創(chuàng)建一個冒泡函數(shù),需要傳遞一個數(shù)組,和數(shù)組的長度 void bubble_sort(int array[],int arrayLength) { // i 控制一共需要循環(huán)多少趟, for (int i=0; i<arrayLength-1; i++) { //定義一個變量,用于記錄是否在本趟中發(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說明已經(jīng)是正確順序了,直接break即可 if (isChange == 0) { break; } } } int main(int argc, const char * argv[]) { // 函數(shù)的聲明 void bubble_sort(int array[],int arrayLength); // 創(chuàng)建一個數(shù)組 int numArray[] = {19,2,13,8,34,25,7}; //進行排序 bubble_sort(numArray,7); printf("打印排序后的數(shù)組是:\n"); for (int i=0; i<7; i++) { printf("%d ",numArray[i]); } return 0; }
運行結(jié)果為:
打印排序后的數(shù)組是:
2 7 8 13 19 25 34
最優(yōu)時間復雜度:O(n) (表示遍歷一次發(fā)現(xiàn)沒有任何可以交換的元素,排序結(jié)束。)
最壞時間復雜度:O(n2)
冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個元素比較,交換也發(fā)生在這兩個元素之間。所以,如果兩個元素相等,是不會再交換的;如果兩個相等的元素沒有相鄰,那么即使通過前面的兩兩交換把兩個相鄰起來,這時候也不會交換,所以相同元素的前后順序并沒有改變,所以冒泡排序是一種穩(wěn)定排序算法。
侯哥語錄:我曾經(jīng)是一個職業(yè)教育者,現(xiàn)在是一個自由開發(fā)者。我希望我的分享可以和更多人一起進步。分享一段我喜歡的話給大家:"我所理解的自由不是想干什么就干什么,而是想不干什么就不干什么。當你還沒有能力說不得時候,就努力讓自己變得強大,擁有說不得權利。"
看完了這篇文章,相信你對“python算法與數(shù)據(jù)結(jié)構(gòu)之冒泡排序的示例分析”有了一定的了解,如果想了解更多相關知識,歡迎關注億速云行業(yè)資訊頻道,感謝各位的閱讀!
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權內(nèi)容。