function qSort(list) {
//检查数组的长度是否为0,是则不需要任何排序,返回空数组
if(list.length == 0) {
return [];
}
//创建两个数组,一个用来存放比基准小的元素,另一个存放比基准值大的元素
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:递归的过程大概是这样
灵魂画手
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"
执行步骤:
执行步骤.png
参考学习:
《数据结构与算法javascript描述》 《学习javascript数据结构与算法》