建站
咨詢
售后
建站咨詢
新聞中心
雞湯給大家備好了：
創(chuàng)新互聯(lián)公司從2013年開始，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目網(wǎng)站制作、成都做網(wǎng)站網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元紅河做網(wǎng)站,已為上家服務(wù),為紅河各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18982081108
歲月流逝是多么殘酷啊，對(duì)我們也是如此，不要把時(shí)間浪費(fèi)在不重要的人和事情上!
在計(jì)算機(jī)科學(xué)中，排序是一個(gè)經(jīng)典的主題。學(xué)習(xí)排序算法的好處有三：
1.創(chuàng)造性解決問題
2.練習(xí)和鞏固程序設(shè)計(jì)技能
3.演示算法性能的極好例子
冒泡排序?qū)儆诒容^簡單的一種排序方法。但是，很多同學(xué)到現(xiàn)在也不能手寫一個(gè)冒泡排序。甚至經(jīng)過和一些剛畢業(yè)甚至工作一兩年的朋友交流后，發(fā)現(xiàn)他們內(nèi)心對(duì)算法，抱著深深的恐懼和盲目崇拜，覺得算法好像高不可攀，只適合那些高學(xué)歷、高智商的人來學(xué)習(xí)和研究!今天，我想把這篇獻(xiàn)給他們，希望他們能樹立起學(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;
- }
- }
- }
- }
本文轉(zhuǎn)載自微信公眾號(hào)「鍋外的大佬」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系鍋外的大佬公眾號(hào)。
網(wǎng)站欄目：看完了這篇，面試的時(shí)候人人都能單手?jǐn)]冒泡排序！
當(dāng)前URL：http://www.5511xx.com/article/cdjphgh.html
