web開發(fā)中冒泡排序是什么意思

這篇文章將為大家詳細講解有關web開發(fā)中冒泡排序是什么意思，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

創(chuàng)新互聯(lián)公司主要從事做網站、網站設計、網頁設計、企業(yè)做網站、公司建網站等業(yè)務。立足成都服務湯陰,十載網站建設經驗,價格優(yōu)惠、服務專業(yè),歡迎來電咨詢建站服務:13518219792

冒泡排序介紹    

冒泡排序一種簡單的排序算法。它會遍歷若干次要排序的數(shù)列，每次遍歷時，它都會從前往后依次的比較相鄰兩個數(shù)的大?。蝗绻罢弑群笳叽?，則交換它們的位置。這樣，一次遍歷之后，最大的元素就在數(shù)列的末尾！ 采用相同的方法再次遍歷時，第二大的元素就被排列在最大元素之前。重復此操作，直到整個數(shù)列都有序為止！

冒泡排序圖解    

下面以數(shù)列{20,40,30,10,60,50}為例，演示它的冒泡排序過程(如下圖)。

我們首先分析第一趟排序：

• 當i=5,j=0時，a[0]<a[1]。此時，不做任何處理！

• 當i=5,j=1時，a[1]>a[2]。此時，交換a[1]和a[2]的值；交換之后，a[1]=30，a[2]=40。

• 當i=5,j=2時，a[2]>a[3]。此時，交換a[2]和a[3]的值；交換之后，a[2]=10，a[3]=40。

• 當i=5,j=3時，a[3]<a[4]。此時，不做任何處理！

• 當i=5,j=4時，a[4]>a[5]。此時，交換a[4]和a[5]的值；交換之后，a[4]=50，a[3]=60。

第一趟排完之后，最大元素60移到數(shù)組最后了，也就是a[5]此時為數(shù)組中最大的元素，再進行第二趟排序的時候，只需按照上面的方法排前面5個元素就可以了。這樣：

第2趟排序完之后，數(shù)列中a[4]、a[5]是有序的。
第3趟排序完之后，數(shù)列中a[3]、a[4]、a[5]是有序的。
第4趟排序完之后，數(shù)列中a[2]、[3]、a[4]、a[5]是有序的。
第5趟排序完之后，數(shù)列中a[1]、a[2]、[3]、a[4]、a[5]是有序的。

第5趟排序之后，整個數(shù)列也就是有序的了。

冒泡排序算法實現(xiàn)    

根據上面流程，不難寫出冒泡排序的代碼實現(xiàn)，此處是按升序排列。

void bubble_sort(int a[], int n)
{int i,j;for (i=n-1; i>0; i--){// 將a[0...i]中最大的數(shù)據放在末尾for (j=0; j<i; j++){if (a[j] > a[j+1])swap(a[j], a[j+1]);}}
}

其實觀察上面例子冒泡排序的流程圖，第3趟排序之后，數(shù)據已經是有序的了；第4趟和第5趟并沒有進行數(shù)據交換。因此可以對冒泡排序進行優(yōu)化，使它效率更高一些：添加一個標記，如果一趟遍歷中發(fā)生了交換，則標記為true，否則為false。如果某一趟沒有發(fā)生交換，說明排序已經完成，退出。優(yōu)化后的代碼如下：

void bubble_sort2(int a[], int n)
{int i,j;int flag;     // 標記一趟是否發(fā)生交換for (i=n-1; i>0; i--){flag = 0;     // 初始化標記為0// 將a[0...i]中最大的數(shù)據放在末尾for (j=0; j<i; j++){if (a[j] > a[j+1]){swap(a[j], a[j+1]);flag = 1; //發(fā)生交換，設flag為1}}if (flag==0)break; // 若無交換，說明數(shù)列已有序}
}

冒泡排序時間空間復雜度    

冒泡排序的時間復雜度是O(N²)：假設被排序的數(shù)列中有N個數(shù)。遍歷一趟的時間復雜度是O(N)，需要遍歷多少次呢？N-1次！因此，冒泡排序的時間復雜度O(N²)。

冒泡排序是穩(wěn)定的算法：它滿足穩(wěn)定算法的定義；所謂算法穩(wěn)定性指的是對于一個數(shù)列中的兩個相等的數(shù)a[i]=a[j]，在排序前,a[i]在a[j]前面，經過排序后a[i]仍然在a[j]前，那么這個排序算法是穩(wěn)定的。

關于“web開發(fā)中冒泡排序是什么意思”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。

網站題目：web開發(fā)中冒泡排序是什么意思
鏈接URL：http://muchs.cn/article28/ihccjp.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供網站策劃、網站設計公司、軟件開發(fā)、外貿網站建設、品牌網站建設、網站建設

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)