泡沫算法

泡沫算法

冒泡排序,是指計算機的一種排序方法,它的時間複雜度為O(n^2),雖然不及堆排序、快速排序的O(nlogn,底數為2),但是有兩個優點:1.“編程複雜度”很低,很容易寫出代碼;2.具有穩定性,這裡的穩定性是指原序列中相同元素的相對順序仍然保持到排序後的序列,而堆排序、快速排序均不具有穩定性。不過,一路、二路歸併排序、不平衡二叉樹排序的速度均比冒泡排序快,且具有穩定性,但速度不及堆排序、快速排序。冒泡排序是經過n-1趟子排序完成的,第i趟子排序從第1個數至第n-i個數,若第i個數比後一個數大(則升序,小則降序)則交換兩數

演示

這裡有一個動畫演示,輸入不同大小的數字點start就開始演示了,很形象
http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/maopaopaixu.htm

思想

這種方法的基本思想是,將待排序的看作是豎著排列的“氣泡”,較小的元素比較輕,從而要往上浮。在冒泡排序算法中我們要對這個“氣泡”序列處理若干遍。所謂一遍處理,就是自底向上檢查一遍這個序列,並時刻注意兩個相鄰的元素的順序是否正確。如果發現兩個相鄰元素的順序不對,即“輕”的元素在下面,就交換它們的位置。顯然,處理一遍之後,“最輕”的元素就浮到了最高位置;處理二遍之後,“次輕”的元素就浮到了次高位置。在作第二遍處理時,由於最高位置上的元素已是“最輕”元素,所以不必檢查。一般地,第i遍處理時,不必檢查第i高位置以上的元素,因為經過前面i-1遍的處理,它們已正確地排好序。

相關詞條

相關搜尋

熱門詞條

聯絡我們