二分查找

// 非递归算法

function binary_search(arr, key) {
var low = 0,
high = arr.length - 1;
while(low <= high){
var mid = parseInt((high + low) / 2);
if(key == arr[mid]){
return mid;
}else if(key > arr[mid]){
low = mid + 1;
}else if(key < arr[mid]){
high = mid -1;
}else{
return -1;
}
}
};
var arr = [1,2,3,4,5,6,7,8,9,10,11,23,44,86];
var result = binary_search(arr,10);
alert(result); // 9 返回目标元素的索引值

 
/* // 递归算法

function binary_search(arr,low, high, key) {
if (low > high){
return -1;
}
var mid = parseInt((high + low) / 2);
if(arr[mid] == key){
return mid;
}else if (arr[mid] > key){
high = mid - 1;
return binary_search(arr, low, high, key);
}else if (arr[mid] < key){
low = mid + 1;
return binary_search(arr, low, high, key);
}
};
var arr = [1,2,3,4,5,6,7,8,9,10,11,23,44,86];
var result = binary_search(arr, 0, 13, 10);

 
alert(result); // 9 返回目标元素的索引值 */
 
 

合并排序

function isArray1(arr){
if(Object.prototype.toString.call(arr) =='[object Array]'){
return true;
}else{
return false;
}
}
function merge(left,right){
var result=[];
if(!isArray1(left)){
left = [left];
}
if(!isArray1(right)){
right = [right];
}
while(left.length > 0&& right.length >0){
if(left[0]<right[0]){
result.push(left.shift());
}else{
result.push(right.shift());
}
}
return result.concat(left).concat(right);
}
function mergeSort(arr){
var len=arr.length;
var lim ,work=[];
var i,j,k;
if(len ==1){
return arr;
}
for(i=0;i<len;i++){
work.push(arr[i]);
}
work.push([]);
for(lim=len;lim>1;){//lim为分组长度
for(j=0,k=0;k<lim;j++,k=k+2){
work[j]=merge(work[k],work[k+1]);
}
work[j]=[];
lim=Math.floor((lim+1)/2);
}
return work[0];
}
var arr1 = [7,5,9,8];
var arr2 = [7,5,9,8,3,20,6,1,2];
console.log(mergeSort(arr1));//5,7,8,9
console.log(mergeSort(arr2));//1,2,3,5,6,7,8,9,20

快速排序

function quickSort(arr){
//如果数组<=1,则直接返回
if(arr.length<=1){return arr;}
var pivotIndex=Math.floor(arr.length/2);
//找基准，并把基准从原数组删除
var pivot=arr.splice(pivotIndex,1)[0];
//定义左右数组
var left=[];
var right=[];
//比基准小的放在left，比基准大的放在right
for(var i=0;i<arr.length;i++){
if(arr[i]<=pivot){
left.push(arr[i]);
}
else{
right.push(arr[i]);
}
}
//递归
return quickSort(left).concat([pivot],quickSort(right));
}
console.log(quickSort([1,3,5,3,7,3,6,4]));