盒子
盒子
文章目录
  1. 二分查找:
  2. 快速排序

二分查找

二分查找:

是一种有(序数组中)查找特定元素的搜索算法, 查找过程中可以分为一下步骤:

  1. 首先, 从有序数组的中间的元素开始搜索, 如果改元素正好是目标元素, 则搜索过程结束, 否则进行下一步.
  2. 如果目标元素大于或者小于中间元素, 则在数组大于或小于中间元素的那一半区域查找, 然后重复第一步的操作
  3. 如果某一不数组为空, 则表示找不到目标元素.

代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 非递归
/**
* arr必须是有序列表
* Param: param
* Return: {undefined}
**/
let binary_search = (arr, key) => {
let low = 0,
high = arr.length - 1;
while(low <= high) {
let 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;
}
}
};
let arr = [1,2,3,4,5,6,7,8,9,10,11,23,44,86];
let result = binary_search(arr,10);
alert(result); // 9 返回目标元素的索引值

递归:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 返回目标元素的索引值

快速排序

快速排序是对冒泡排序的一种该经, 第一趟排序时将数据分成两个部分, 一部分比另一部分的数据都要小, 然后递归调用, 在两边都实行快速排序.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function quickSort (elements) {
if (elements.length <= 1) return elements;
let pivotIndex = Math.floor(elements.length / 2 );
let pivot = elements.splice(pivotIndex, 1)[0];
let left = [],
right = [];
for(let i = 0; i < elements.length; i++) {
if (elements[i] < pivot) {
left.push(elements[i]);
}else {
right.push(elements[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
}
var elements=[5,6,2,1,3,8,7,1.2,5.5,4.5];
alert(quickSort(elements));

原文地址