排序的方法有很多,本節介紹如何使用陣列的 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));//遞歸 }這段程式的運作流程是:
splice 把它從原陣列取出。push 把比基準小的放進 left、大的放進 right。concat 把「排好序的左半 + 基準 + 排好序的右半」拼接起來,左右兩半再各自遞迴。透過 push 分區搭配遞迴,就能簡潔地完成快速排序。這種寫法把「比較、分區、合併」三個步驟表達得非常直觀,是理解分治演算法很好的入門範例。