DIV CSS 佈局教程網

用陣列 push 方法實作快速排序
編輯:關於JavaScript     

排序的方法有很多,本節介紹如何使用陣列的 push 方法來完成快速排序(Quick Sort)。相較於其他寫法,這個版本在分區時用 push 把元素分到左右兩邊,讀起來相當清楚。

 function quickSort(arr){ if(arr.length <= 1) return arr;//判斷是否有效數組 var cut = Math.floor(arr.length/2);//取中間下標 var left = [],right = []; var num = arr.splice(cut,1)[0];//取基准值 for(var i = 0;i < arr.length;i ++){ if(arr[i] < num){ left.push(arr[i]);//小的放左邊 }else { right.push(arr[i]);//大的放右邊 } } return quickSort(left).concat(num,quickSort(right));//遞歸 }

這段程式的運作流程是:

  • 先判斷陣列是否有效——長度小於等於 1 時直接回傳(這是遞迴的終止條件)。
  • 取中間位置作為基準值(pivot),並用 splice 把它從原陣列取出。
  • 遍歷剩下的元素,用 push 把比基準小的放進 left、大的放進 right。
  • 最後用 concat 把「排好序的左半 + 基準 + 排好序的右半」拼接起來,左右兩半再各自遞迴。

透過 push 分區搭配遞迴,就能簡潔地完成快速排序。這種寫法把「比較、分區、合併」三個步驟表達得非常直觀,是理解分治演算法很好的入門範例。

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