DIV CSS 佈局教程網

JS 陣列排序的兩種經典實作分析
編輯:關於JavaScript     

本文整理兩種不需要呼叫內建 sort 的排序實作,幫助理解排序的核心動作:比較與交換。

方法一:氣泡排序

思路:依序比較相鄰的兩個元素,若前者大於後者就交換位置。所以需要兩個輔助函式:交換函式與比較判斷。比較輪數為陣列長度。

 var arr=[2,58,49,26,34]; function change(f,s){ var temp=arr[f]; arr[f]=arr[s]; arr[s]=temp; } for(var i=0;i<arr.length;i++){ for(var j=0;j<arr.length-1;j++){ if(arr[j]>arr[j+1]){ change(j,j+1); } } } alert(arr); 

外層迴圈控制輪數,內層負責一輪的相鄰比較。每跑完一輪,當前最大值就會被推到尚未排序區間的尾端。

方法二:選擇排序(遞迴版)

從陣列中找出最小值放到第一位,然後對剩下的部分重複同樣的動作。

 var arr=[2,58,49,26,34]; function change(){ if(arr.length==1){ return arr; } var iMin=arr[0]; var index=0; for(var i=0;i<arr.length;i++){ if(arr[i]<iMin){ iMin=arr[i]; index=i; } } var prev=arr.splice(index,1); return prev.concat(change(arr)); } alert(change(arr)); 

這裡用 splice 把最小值從原陣列取出,再把剩下的陣列遞迴交給自己,最後用 concat 拼接。終止條件是陣列只剩一個元素。

兩種演算法的時間複雜度都是 O(n²),資料量大時應改用內建的 sort 或更高效的演算法;但它們的價值在於把「比較 + 交換」這個本質攤開來看。

希望本文所述對你的 JavaScript 開發有所幫助。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved