實作原理
通過一趟排序將要排序的資料分割成獨立的兩部分：
- 分割點
base默認取一開始陣列最左邊的值 - 經過左右指標的磁區判斷，令所有比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊），在這個磁區退出之后，該基準就處于數列的中間位置，
- 之后把小于基準值元素的子數列和大于基準值元素的子數列排序，
寫法一：遞回+自建函式
function division(array,left,right){
//以最左邊的數為基準，取數值
let base=array[left];
while(left<right){
//從序列右端開始，向左遍歷，直到找到小于base的數
while(left<right && array[right] >= base) right--;
//找到比base小的元素，將這個元素放到最左邊的位置
array[left]=array[right];
//從序列左端開始，向右遍歷，直到找到大于base的數
while(left<right && array[left] <= base) left++;
//找到比base大的元素，將這個元素放到最右邊的位置
array[right]=array[left];
}
//最后將base放到left位置，此時，left位置的左側數值應比base小;
//而left位置的右側數值比base大
array[left]=base;
//回傳base下標
return left;
}
function QuickSort(array,left,right) {
//左下標一定小于右下標
if(left<right){
//對陣列進行分割，取下次分割的基準下標
let base=division(array,left,right);
//繼續對基準下標的左側進行遞回切割，以保最后的排序
QuickSort(array,left,base-1);
//繼續對基準下標的右側進行遞回切割，以保最后的排序
QuickSort(array,base+1,right);
}
return array;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(QuickSort(arr,0,arr.length-1));
- 時間復雜度：\(O(NlogN)\)
- 空間復雜度：\(O(logN)\)
不穩定的排序演算法
寫法二：利用array的內置函式
其實base一開始可以隨便選，這次我選正中間，利用splice()函式單獨切割出來，再比較左右子磁區的情況，之后就重新用concat()合并就好了，當然這樣的寫法會加大時間的開銷，
var QuickSort2=function(arr){
if(arr.length<=1) return arr;
var baseIndex = Math.floor(arr.length/2);
//單獨取出來
var base=arr.splice(baseIndex,1)[0];
let left=[],right=[];
for(let i=0;i<arr.length;i++){
if(arr[i]<base){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
return QuickSort2(left).concat([base],QuickSort2(right));
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(QuickSort2(arr));
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/499523.html
標籤：其他
下一篇：01背包面試題系列（一）