當(dāng)前位置:首頁(yè) > 公眾號(hào)精選 > strongerHuang
[導(dǎo)讀]關(guān)注星標(biāo)公眾號(hào),不錯(cuò)過(guò)精彩內(nèi)容來(lái)源|CSDN編排?|strongerHuang軟件排序算法中,冒泡排序是最經(jīng)典的一個(gè),很多大學(xué)教程也都是用它作為案例。你知道冒泡排序的時(shí)間與空間復(fù)雜度嗎?概述冒泡排序(BubbleSort):是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡(jiǎn)單的排序算法。它重復(fù)地走訪過(guò)要...


來(lái)源 | CSDN


編排 | strongerHuang




軟件排序算法中,冒泡排序是最經(jīng)典的一個(gè),很多大學(xué)教程也都是用它作為案例。




你知道冒泡排序的時(shí)間與空間復(fù)雜度嗎?



概述


冒泡排序(Bubble Sort):是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡(jiǎn)單的排序算法。
它重復(fù)地走訪過(guò)要排序的數(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ù)列的頂端,故名算法分析。



冒泡排序算法是所有排序算法中最簡(jiǎn)單的,在生活中應(yīng)該也會(huì)看到氣泡從水里面出來(lái)時(shí),越到水面上氣泡就會(huì)變的越大。在物理上學(xué)氣壓的時(shí)候好像也看到過(guò)這種現(xiàn)象;
其實(shí)理解冒泡排序就可以根據(jù)這種現(xiàn)象來(lái)理解:每一次遍歷,都把大的往后面排(當(dāng)然也可以把小的往后面排),所以每一次都可以把無(wú)序中最大的(最小)的元素放到無(wú)序的最后面(或者說(shuō)有序元素的最開(kāi)始);
基本步驟


1.外循環(huán)是遍歷每個(gè)元素,每次都放置好一個(gè)元素;


2.內(nèi)循環(huán)是比較相鄰的兩個(gè)元素,把大的元素交換到后面;3.等到第一步中循環(huán)好了以后也就說(shuō)明全部元素排序好了;
代碼實(shí)現(xiàn):
#include//打印數(shù)組元素void print_array(int *array, int length){ int index = 0; printf("array:\n"); for(; index < length; index ){ printf(" %d,", *(array index)); } printf("\n\n"); }
void bubbleSort(int array[], int length){ int i, j, tmp;
if (1 >= length) return;// 判斷參數(shù)條件
for (i = length-1; i > 0; i--){//外循環(huán),循環(huán)每個(gè)元素 for (j = 0; j < i; j ){ // 內(nèi)循環(huán), if (array[j] > array[j 1]){// 交換相鄰的兩個(gè)元素 tmp = array[j]; array[j] = array[j 1]; array[j 1] = tmp; } } } }
int main(void){ int array[12] = {1,11,12,4,2,6,9,0,3,7,8,2}; print_array(array, 12); bubbleSort(array, 12); print_array(array, 12); return 0; }
時(shí)間復(fù)雜度


1.這個(gè)時(shí)間復(fù)雜度還是很好計(jì)算的:外循環(huán)和內(nèi)循環(huán)以及判斷和交換元素的時(shí)間開(kāi)銷;



2.最優(yōu)的情況也就是開(kāi)始就已經(jīng)排序好序了,那么就可以不用交換元素了,則時(shí)間花銷為:[ n(n-1) ] /  2;所以最優(yōu)的情況時(shí)間復(fù)雜度為:O( n^2 );
3.最差的情況也就是開(kāi)始的時(shí)候元素是逆序的,那么每一次排序都要交換兩個(gè)元素,則時(shí)間花銷為:[ 3n(n-1) ] / 2;(其中比上面最優(yōu)的情況所花的時(shí)間就是在于交換元素的三個(gè)步驟);所以最差的情況下時(shí)間復(fù)雜度為:O( n^2 );
綜上所述:
  • 最優(yōu)的時(shí)間復(fù)雜度為:O( n^2 ) ;有的說(shuō) O(n),下面會(huì)分析這種情況;


  • 最差的時(shí)間復(fù)雜度為:O( n^2 );


  • 平均的時(shí)間復(fù)雜度為:O( n^2 );



空間復(fù)雜度


  • 空間復(fù)雜度就是在交換元素時(shí)那個(gè)臨時(shí)變量所占的內(nèi)存空間;


  • 最優(yōu)的空間復(fù)雜度就是開(kāi)始元素順序已經(jīng)排好了,則空間復(fù)雜度為:0;


  • 最差的空間復(fù)雜度就是開(kāi)始元素逆序排序了,則空間復(fù)雜度為:O(n);


  • 平均的空間復(fù)雜度為:O(1);


  • 最優(yōu)時(shí)間復(fù)雜度 n



有很多人說(shuō)冒泡排序的最優(yōu)的時(shí)間復(fù)雜度為:O(n);
其實(shí)這是在代碼中使用一個(gè)標(biāo)志位來(lái)判斷是否已經(jīng)排序好的,修改下上面的排序代碼:
void bubbleSort(int array[], int length){ int i, j, tmp; int flag = 1;
if (1 >= length) return;
for (i = length-1; i > 0; i--, flag = 1){ for (j = 0; j < i; j ){ if (array[j] > array[j 1]){ tmp = array[j]; array[j] = array[j 1]; array[j 1] = tmp; flag = 0; } } if (flag) break; } }


根據(jù)上面的代碼可以看出,如果元素已經(jīng)排序好,那么循環(huán)一次就直接退出?;蛘哒f(shuō)元素開(kāi)始就已經(jīng)大概有序了,那么這種方法就可以很好減少排序的次數(shù);
其實(shí)我感覺(jué)這種方法也有弊端,比如要額外的判斷下,以及賦值操作;
空間復(fù)雜度為 0?
有人會(huì)說(shuō)這個(gè)空間復(fù)雜度能降到0,因?yàn)榭臻g復(fù)雜度主要是看使用的輔助內(nèi)存,如果沒(méi)有輔助內(nèi)存變量,那么可以說(shuō)空間復(fù)雜度為0;所以該算法中空間復(fù)雜度一般是看交換元素時(shí)所使用的輔助空間;
1、 a  = a b;b = a - b;a = a - b;2、 a = a * b;   b =  a / b;a = a / b;3、 a = a ^ b;  b =  a ^ b;a = a ^ b;


上面幾種方法都可以不使用臨時(shí)空間來(lái)交換兩個(gè)元素,但是都有些潛在的問(wèn)題,比如越界;
所以個(gè)人覺(jué)得還是老老實(shí)實(shí)的用個(gè)臨時(shí)變量吧,這樣算法意圖就比較清晰了。
參考來(lái)源:


https://blog.csdn.net/p1279030826/article/details/99072021



聲明:本文素材來(lái)源網(wǎng)絡(luò),版權(quán)歸原作者所有。如涉及作品版權(quán)問(wèn)題,請(qǐng)與我聯(lián)系刪除。------------ END ------------





本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點(diǎn),本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請(qǐng)聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請(qǐng)及時(shí)聯(lián)系本站刪除。

strongerHuang

692 篇文章

關(guān)注

發(fā)布文章

編輯精選

技術(shù)子站

關(guān)閉