-
快速排序
快速排序是處理大數據集最快的排序算法之一库菲。它是一種分而治之的算法呈队，通過遞歸的方式將數據依次分解為包含較小元素和較大元素的不同子序列枪蘑。該算法通過不斷重復這個步驟知道所有數據都是有序的。
-
算法實現
這個算法首先要在列表中選擇一個元素作為基準值（pivot）陆馁。數據排序圍繞基準值進行找颓，將列表中小于基準值的元素移到數組的底部（左邊），將大于基準值的元素移到數組的頂部（右邊）叮贩。①選擇一個基準元素叮雳，將列表分成兩個子序列想暗；
②對列表重新排序，將所有小于基準值的元素放在基準值前面帘不，所有大于基準值的元素放在基準值的后面说莫；
③分別對較小的元素的子序列和較大元素的子序列重復步驟①和步驟②。
function qSort(list) {
//檢查數組的長度是否為0寞焙，是則不需要任何排序储狭，返回空數組
if(list.length == 0) {
return [];
}
//創(chuàng)建兩個數組，一個用來存放比基準小的元素捣郊，另一個存放比基準值大的元素
var left = [];
var right = [];
//基準值取自數組的第一個元素
var pivot = list[0];
//遍歷數組辽狈，根據它們與基準值的關系放到合適的數組中
for(var i=1;i<list.length;i++) {
if(list[i] < pivot) {
left.push(list[i]);
}else{
right.push(list[i]);
}
}
//然后對于較小的數組和較大的數組分別遞歸調用這個函數
return qSort(left).concat(pivot,qSort(right));
}
var test = [4,3,5,1,2];
console.log(qSort(test)); //[1,2,3,4,5]
ps：遞歸的過程大概是這樣
靈魂畫手
-
二分法算法
如果你要查找的數據是有序的，二分查找算法比順序查找算法更高效呛牲。
算法理解
二分搜索算法的原理和猜數字游戲類似刮萌，就是那個有人說“我正想著一個1到100的數字”的游戲。我們每回應一個數字娘扩，那個人就會說這個數字是高了着茸、低了還是對了。算法描述
①選擇中間值琐旁；
②如果選擇的值是待搜索的值涮阔，算法結束并返回；
③如果待搜索值比選中值要小灰殴，則返回步驟①并在選中值左邊的子數組中尋找敬特。
④如果待搜索值比選中值要大，則返回步驟①并在選中值右邊的子數組中尋找牺陶。算法實現
function binSearch(arr,data) {
//將傳入的數組用快速排序算法排序一下
var arr = qSort(arr);
//將最后一個元素所在的位置設為上邊界
var upperBound = arr.length-1;
//將數組的第一個位置設為下邊界
var lowerBound = 0;
while(lowerBound <= upperBound) {
//中點
var mid = Math.floor((upperBound + lowerBound)/2);
//如果待查詢的值大于中點元素伟阔，則將下邊界設置為中點元素所在下標加1，也就是選取數組的右半邊(不包括中點元素)掰伸，然后再在里面查找
if(arr[mid] < data) {
lowerBound = mid+1;
//如果待查詢的值小于中點元素减俏，同理如上
}else if(arr[mid] > data) {
upperBound = mid-1;
//否則如果相等，返回
}else {
return mid;
}
}
return -1;
}
var test = [1,2,3,4,5,6];
console.log(binSearch(test,2)); //位置"1"
執(zhí)行步驟：
執(zhí)行步驟.png
參考學習：
《數據結構與算法javascript描述》
《學習javascript數據結構與算法》
