如何掌握并使用冒泡排序

這篇文章主要講解了“如何掌握并使用冒泡排序”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“如何掌握并使用冒泡排序”吧！

1.什么是冒泡排序

冒泡排序算法需要遍歷幾次數(shù)組，在每次遍歷中，比較連續(xù)相鄰的元素。如果一對(duì)元素是降序排列，則互換他們的位置，否則保持不變。這樣一來，使得較小的值像“氣泡”一樣，逐漸浮向頂部，而較大的值沉入底部，因此稱這種排序方法為冒泡排序(bubble  sort )或下沉排序(sinking sort)。

第一次遍歷之后，最后一個(gè)元素將成為最大的元素。第二次遍歷之后，倒數(shù)第二個(gè)元素，將成為倒數(shù)第二大的元素。整個(gè)過程持續(xù)到所有的元素全部都已排好序。

2.圖解冒泡排序

經(jīng)過第一次遍歷后，最大的數(shù)已經(jīng)在數(shù)組末尾。因?yàn)樽詈笠粋€(gè)數(shù)已經(jīng)是最大數(shù)，因此不需要再考慮最后一對(duì)元素。

經(jīng)過第二次遍歷，后兩個(gè)數(shù)已經(jīng)排好序，所以只需要對(duì)除它們之外的元素進(jìn)行排序。

因此，在進(jìn)行第n次遍歷時(shí)，不需要考慮倒數(shù)第n-1個(gè)元素，因?yàn)樗鼈円呀?jīng)排好序了!

冒泡排序偽代碼：

for(int k = 1; k < list.length; k++){     for(int j = 0; j < list.length-k; j++) {         if(list[j] > list[j + 1]) {             swap(list[i], list[i + 1]);         }     } }

3.改進(jìn)后的冒泡排序

注意到，上面的排序?qū)嶋H上有很多次沒有發(fā)生交換，因此，我們可以對(duì)冒泡排序稍微改進(jìn)下：

boolean nextPass = true; for(int k = 1; k < list.length && nextPass; k++){     nextPass = false;     for(int j = 0; j < list.length-k; j++) {         if(list[j] > list[j + 1]) {             swap(list[i], list[i + 1]);             nextPass = true;         }     } }

4. 冒泡排序時(shí)間復(fù)雜度

最佳情況下，冒泡排序只需要一次遍歷就能確定數(shù)組已排好序，不需要再進(jìn)行下一次遍歷。因此，最佳情況下，冒泡排序時(shí)間復(fù)雜度為O(n)。

最壞情況下，冒泡排序需要 次。因此比較總次數(shù)為: $$ (n-1) + (n-2) + (n-3) + ...+ 3 + 2 + 1 = ({\frac  n2^2} - {\frac n2}) = O(n^2) $$ 所以，最壞情況下，冒泡排序的時(shí)間復(fù)雜度為:O(n^2)。

5. 附上函數(shù)

public static void bubbleSort(int[] list) {     boolean nextPass = true;     for(int k = 1; k < list.length && nextPass; k++){         nextPass = false;         for(int j = 0; j < list.length-k; j++) {             if(list[j] > list[j + 1]) {                 int tmp = list[j];                 list[j] = list[j+1];                 list[j+1] = tmp;                 nextPass = true;             }         }     } }

感謝各位的閱讀，以上就是“如何掌握并使用冒泡排序”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)如何掌握并使用冒泡排序這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！