關於排序,其實不管是哪種語言,都有它內置的排序函數,我們要用的時候調用就行了,既然如此,我們為什麼還要講這個東西呢?我想,其實,我們講排序更多是在於排序中包含的思想演算法,因為,演算法對於電腦來說相當重要,一個好的演算法能夠讓電腦的效率達到事半功倍的效果,所以,演算法是電腦語言中一門相當熱門的課程,它 ...
關於排序,其實不管是哪種語言,都有它內置的排序函數,我們要用的時候調用就行了,既然如此,我們為什麼還要講這個東西呢?我想,其實,我們講排序更多是在於排序中包含的思想演算法,因為,演算法對於電腦來說相當重要,一個好的演算法能夠讓電腦的效率達到事半功倍的效果,所以,演算法是電腦語言中一門相當熱門的課程,它所代表的電腦思維也是很值得我們去深入研究的。
我也知道,關於我標題中的排序,博客園中的很多作者都寫過詳細解釋的文章,可能,筆者本人認為自己的理解更能體現出這個排序的工作原理吧,所以,筆者也就大慚不愧的在這裡再次寫下關於冒泡排序的文章,有需要的讀者可以看一下。
再進入正題之前,我給大家介紹一下谷歌瀏覽器一個很有用的調試程式代碼的功能,如果你已經知道,請略過。
首先,打開谷歌瀏覽器,輸入我們的代碼腳本:
右鍵,點擊檢查,
按順序點擊,獲取腳本的運行代碼:
我的腳本是bubble.html,存儲在www.test.com功能變數名稱下麵的js/f目錄下麵,每個人的腳本不一樣,存儲的目錄也不一樣,請根據自己的情況來。
調出腳本的內容後,下麵就是調試代碼了。
選擇好了斷點之後,接下來在谷歌瀏覽器中再次運行腳本,就是對下麵的www.test.com/js/f/bubble.html再回車運行
再次運行之後,你會看到這樣的東西:
看到上面的那個藍色矩形框了嗎?這個藍色矩形框就是腳本正在運行的代碼位置,那我們怎麼讓腳本的代碼一步步的運行呢?
這裡之所以對這個腳本的for迴圈代碼進行斷點監控,其實,我是為了查看冒泡排序到底是怎麼迴圈操作的,對於新手來說,這樣子直觀的查看冒泡排序代碼的運行情況會更好的瞭解演算法的執行過程。
對於這個調試小功能就介紹到這裡了,下麵進入正題,沒辦法直接想象出冒泡排序的執行情況的話,你可以按我上面的步驟調出谷歌的調試功能,直觀的查看冒泡排序的整個過程。
介紹一下兩個變數互相調換的思維,我們藉助中間變數來調換:
//交互元素,這裡的代碼是從腳本中截取出來的,這麼簡單,應該不影響理解 if(arr[j] > arr[j+1]){ mark = false; var temp = arr[j];//temp是中間變數,把要交換的第一個元素arr[j]賦值給中間變數,也是把第一個元素存儲起來 arr[j] = arr[j+1];//第二個元素賦值給第一個元素,因為第一個元素我們已經存儲在中間變數中了,所以我們不用擔心它的值會被覆蓋掉 arr[j+1] = temp;//temp存儲了第一個元素的值,把它賦值給第二個元素,就是把第一個元素賦值給第二個元素了,到這一步,兩個元素已經交換位置了 }
再介紹一下,冒泡排序的演算法過程:
冒泡排序:通過對相鄰元素的對比,並交換位置,一步一步的把一個元素給挑選出來。
舉個例子,對下麵的數組進行排序:
這是一個無序的數組:2,9,4,8,5,1,0,7,3,6
比較規則:大於>
第一輪:
第一次比較:我們把2和9作比較:2>9嗎 ?2和9比較是假,那麼我們不管它,繼續向前。
第二次比較:9和4做比較,9>4嗎 ? 是真,那麼我們讓它們交換值,交換了值,它們的位置不就變了嗎,是吧?怎麼交換值上面已經講過,這裡不再重覆了。
經過這次交換值,原來的數組已經變成:2,4,9,8,5,1,0,7,3,6
第三次比較:9和8做比較,9>8嗎 ? 是真,那麼它們兩個繼續交換值,此時,數組已經變成:2,4,8,9,5,1,0,7,3,6
......................
看到這裡9的位置了嗎?它是不是一步一步往後移?第一次比較因為9本來就是大的,所以,它不應該和2交換位置,因此,9沒有被放到前面去,第二次比較,因為9比4大,所以,根據比較規則,它們應該互換位置,也就是9向後移了一位,第三次比較,依然符合比較規則,所以9和8互換位置了,9又向後移了一步,接下來的比較和上面的比較是一樣的過程,你自己比較想象一下吧,這裡就不再重覆了。
比較到最後一次:原數組的情況應該是:2,4,8,5,1,0,7,3,6,9
經過第一輪的比較,我們已經把最大的元素給放到最後面去了,對吧?
接下來,第二輪:
首先說一下,第二輪的時候,原來的數組2,9,4,8,5,1,0,7,3,6,已經變成了2,4,8,5,1,0,7,3,6,9,我們是在已經冒泡過一次的數組的基礎上進行比較的,先確認這一點,要是你還認為是最初的數組,那麼,接下來的比較你會被搞糊塗的。呵呵。
此刻的數組:2,4,8,5,1,0,7,3,6,9
根據比較規則:2>4 嗎?是假,不管它,繼續向前比較。
4>8嗎?是假,不管它,繼續向前比較。
8>5嗎?是真,兩者交換值,也就是互換位置,此刻數組:2,4,5,8,1,0,7,3,6,9
繼續向前,8>1嗎?是真,兩者交換位置,此刻數組:2,4,5,1,8,0,7,3,6,9
.......
比較到最後,原數組又發生了改變,已經變成:2,4,5,1,0,7,3,6,8,9
經過兩輪的比較,原數組是否已經變得有序一點了?呵呵,沒有錯,兩輪之後,最後面的兩位數已經是有序的了。
既然兩輪之後,最後面的兩位已經是有序的了,那麼,十輪之後呢?你自己想象一下。
十輪之後,這個數組肯定已經排序好了。這就是冒泡排序的工作過程,相鄰元素比較,每一輪冒泡出一個有序的值。
那麼,我們怎麼用代碼的方式實現冒泡排序呢?
寫到這裡,我想大家應該知道怎麼做了吧?
我們用兩層嵌套的for迴圈來實現這個過程,也就是實現冒泡排序:
//外層控制輪數 for(var i=0;i<len;i++){ //內層對數組元素進行冒泡選擇 for(var j=0;j<len-1-i;j++){ //交互元素 if(arr[j] > arr[j+1]){ var temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } }
上面那兩個嵌套的for迴圈看到了嗎?外層的for迴圈,我們就是用來控制比較········輪數········的,
內層的for迴圈,我們用來控制···················每一輪的比較次數··················的,同時,在這個for迴圈裡面,我們還要做什麼呢?上面的文字敘述,你看懂了嗎?上面的文字敘述中,我們是不是在···每一次比較···的時候,都要根據比較規則來交換數組元素的位置,是吧?那麼,程式的工作過程也是一樣的,我們也要在這裡根據比較規則對數組的元素進行交換位置,為的是冒泡出我們需要的元素。
下麵是冒泡排序的完整代碼,我對他進行了優化,當然,如果還可以優化,你也可以繼續優化的。
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="zh-cn"> <head> <meta http-equiv="Content-Type" content="text/html;charset=UTF-8" /> <title>冒泡排序</title> <meta name="keywords" content="關鍵字列表" /> <meta name="description" content="網頁描述" /> <link rel="stylesheet" type="text/css" href="" /> <style type="text/css"></style> <script type="text/javascript"> //參數數字數組 function bubble(arr){ //檢查參數 if(toString.call(arr) !== '[object Array]'){ return false; } //獲取數組長度 var len = arr.length; if(len <= 1){//小於1不用排序 return arr; } //外層控制輪數 for(var i=0;i<len;i++){ //標記是否有排序的元素 var mark = true; //內層對數組元素進行冒泡選擇 for(var j=0;j<len-1-i;j++){ //交互元素 if(arr[j] > arr[j+1]){ mark = false; var temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } if(mark){ //當沒有進行冒泡選擇時,證明已經排序好了 return arr; } } } //測試 var ar = [9,3,7,4,8,2,5,1,6,0]; alert(bubble(ar)); </script> </head> <body> </body> </html>
這裡只是簡單的介紹冒泡排序的工作原理,假如有時間,我再詳細講解一下另外三個排序,快速排序、選擇排序、插入排序。
其實這三個排序的工作原理都和冒泡排序很相似,網上也有很多文章介紹,大家可以自己研究一下。