這篇文章給大家分享的內容是兩種實用的js排序演算法分析,有著一定的參考價值,有需要的朋友可以參考一下
零:資料準備,給定數組arr=[2,5,4,1,7,3,8,6,9,0];
一:冒牌排序
1思想:冒泡排序想法:每一次比較相鄰兩個資料的大小,小的排在前面,如果前面的資料比後面的大就交換這兩個數的位置
要實現上述規則需要用到兩層for循環,外層從第一個數到倒數第二個數,內層從外層的後面一個數到最後一個數
2特點:排序演算法的基礎。簡單實用易於理解,缺點是比較次數多,效率較低。
3實作:
var times=0; var bubbleSort=function(arr){ for(var i=0;i<arr.length-1;i++){ for(var j=i+1;j<arr.length;j++){ if(arr[i]>arr[j]){//如果前面的数据比后面的大就交换 var temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } console.log("第"+(++times)+"次排序后:"+arr); } } return arr; } console.log("The result is:"+bubbleSort(arr));
4效率:陣列長度10,排序次數45次。
二:快速排序
1想法:快速排序思想:先找到一個基準點(一般指數組的中部),然後數組被該基準點分為兩部分,依次與該基準點資料比較,如果比它小,放左邊;反之,放右邊。
左右分別以空數組去儲存比較後的資料。最後遞歸執行上述操作,直到陣列長度<=1;
2特點:快速,常用。缺點是需要另外聲明兩個數組,浪費了記憶體空間資源。
3實作:
var times=0; var quickSort=function(arr){ //如果数组长度小于等于1无需判断直接返回即可 if(arr.length<=1){ return arr; } var midIndex=Math.floor(arr.length/2);//取基准点 var midIndexVal=arr.splice(midIndex,1);//取基准点的值,splice(index,1)函数可以返回数组中被删除的那个数arr[index+1] var left=[];//存放比基准点小的数组 var right=[];//存放比基准点大的数组 //遍历数组,进行判断分配 for(var i=0;i<arr.length;i++){ if(arr[i]<midIndexVal){ left.push(arr[i]);//比基准点小的放在左边数组 } else{ right.push(arr[i]);//比基准点大的放在右边数组 } console.log("第"+(++times)+"次排序后:"+arr); } //递归执行以上操作,对左右两个数组进行操作,直到数组长度为<=1; return quickSort(left).concat(midIndexVal,quickSort(right)); }; console.log(quickSort(arr));
4效率:陣列長度10,排序次數22次。
三:總結
兩種方法各有優缺點,但是這兩種方法作為程式設計師必須掌握,因為一種是最基礎的,另一種是最常用的,面試或日常都會碰到。
相關推薦:
js實作排序演算法(冒泡、選擇、插入、二分插入、快速、希.. .
以上是兩種實用的js排序演算法分析的詳細內容。更多資訊請關注PHP中文網其他相關文章!