国产在线观看高潮免费播放一级二级三级,色色五月丁香婷婷,成人五月天激情视频

當前位置：首頁 > 公眾號精選 > strongerHuang

[導(dǎo)讀]關(guān)注星標公眾號，不錯過精彩內(nèi)容來源|CSDN編排?|strongerHuang軟件排序算法中，冒泡排序是最經(jīng)典的一個，很多大學教程也都是用它作為案例。你知道冒泡排序的時間與空間復(fù)雜度嗎？概述冒泡排序（BubbleSort）：是一種計算機科學領(lǐng)域的較簡單的排序算法。它重復(fù)地走訪過要...

來源 | CSDN

編排 | strongerHuang

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

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

概述

冒泡排序（Bubble Sort）：是一種計算機科學領(lǐng)域的較簡單的排序算法。
它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。
這個算法的名字由來是因為越大的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端，故名算法分析。

冒泡排序算法是所有排序算法中最簡單的，在生活中應(yīng)該也會看到氣泡從水里面出來時，越到水面上氣泡就會變的越大。在物理上學氣壓的時候好像也看到過這種現(xiàn)象；
其實理解冒泡排序就可以根據(jù)這種現(xiàn)象來理解：每一次遍歷，都把大的往后面排（當然也可以把小的往后面排），所以每一次都可以把無序中最大的（最小）的元素放到無序的最后面（或者說有序元素的最開始）；
基本步驟

1.外循環(huán)是遍歷每個元素，每次都放置好一個元素；

2.內(nèi)循環(huán)是比較相鄰的兩個元素，把大的元素交換到后面；3.等到第一步中循環(huán)好了以后也就說明全部元素排序好了；
代碼實現(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)每個元素 for (j = 0; j < i; j ){ // 內(nèi)循環(huán)， if (array[j] > array[j 1]){// 交換相鄰的兩個元素 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; }
時間復(fù)雜度

1.這個時間復(fù)雜度還是很好計算的：外循環(huán)和內(nèi)循環(huán)以及判斷和交換元素的時間開銷；

2.最優(yōu)的情況也就是開始就已經(jīng)排序好序了，那么就可以不用交換元素了，則時間花銷為：[ n(n-1) ] / 2；所以最優(yōu)的情況時間復(fù)雜度為：O( n^2 )；
3.最差的情況也就是開始的時候元素是逆序的，那么每一次排序都要交換兩個元素，則時間花銷為：[ 3n(n-1) ] / 2；（其中比上面最優(yōu)的情況所花的時間就是在于交換元素的三個步驟）；所以最差的情況下時間復(fù)雜度為：O( n^2 )；
綜上所述：

最優(yōu)的時間復(fù)雜度為：O( n^2 ) ；有的說 O(n)，下面會分析這種情況；
最差的時間復(fù)雜度為：O( n^2 )；
平均的時間復(fù)雜度為：O( n^2 )；

空間復(fù)雜度

空間復(fù)雜度就是在交換元素時那個臨時變量所占的內(nèi)存空間；
最優(yōu)的空間復(fù)雜度就是開始元素順序已經(jīng)排好了，則空間復(fù)雜度為：0；
最差的空間復(fù)雜度就是開始元素逆序排序了，則空間復(fù)雜度為：O(n)；
平均的空間復(fù)雜度為：O(1)；
最優(yōu)時間復(fù)雜度 n

有很多人說冒泡排序的最優(yōu)的時間復(fù)雜度為：O(n)；
其實這是在代碼中使用一個標志位來判斷是否已經(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元素開始就已經(jīng)大概有序了，那么這種方法就可以很好減少排序的次數(shù)；
其實我感覺這種方法也有弊端，比如要額外的判斷下，以及賦值操作；
空間復(fù)雜度為 0？
有人會說這個空間復(fù)雜度能降到0，因為空間復(fù)雜度主要是看使用的輔助內(nèi)存，如果沒有輔助內(nèi)存變量，那么可以說空間復(fù)雜度為0；所以該算法中空間復(fù)雜度一般是看交換元素時所使用的輔助空間；

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；

上面幾種方法都可以不使用臨時空間來交換兩個元素，但是都有些潛在的問題，比如越界；
所以個人覺得還是老老實實的用個臨時變量吧，這樣算法意圖就比較清晰了。

參考來源：

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

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

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