斐波那次数列
// 节省内存空间,没有重复计算
function fibonacci(n){
if (n < 2) {
return;
}
let tmp1 = 1;
let tmp2 = 1;
let tmp3;
for (var i = 1; i < n; i++) {
tmp3 = tmp1 + tmp2;
tmp1 = tmp2;
tmp2 = tmp3;
}
return tmp3;
}
console.log(fibonacci(9))
快速排序
function quickSort(arr) {
// 交换
function swap(arr, a, b) {
console.log('swap ' + arr[a] + ' ' + arr[b])
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
// 分区
function partition(arr, left, right) {
/**
* 开始时不知最终pivot的存放位置,可以先将pivot交换到后面去
* 这里直接定义最右边的元素为基准
*/
var pivot = arr[right];
/**
* 存放小于pivot的元素时,是紧挨着上一元素的,否则空隙里存放的可能是大于pivot的元素,
* 故声明一个storeIndex变量,并初始化为left来依次紧挨着存放小于pivot的元素。
*/
var storeIndex = left;
for (var i = left; i < right; i++) {
if (arr[i] < pivot) {
/**
* 遍历数组,找到小于的pivot的元素,(大于pivot的元素会跳过)
* 将循环i次时得到的元素,通过swap交换放到storeIndex处,
* 并对storeIndex递增1,表示下一个可能要交换的位置
*/
swap(arr, storeIndex, i);
storeIndex++;
}
}
// 最后: 将pivot交换到storeIndex处,基准元素放置到最终正确位置上
swap(arr, right, storeIndex);
console.log('storeIndex ' + storeIndex)
return storeIndex;
}
function sort(arr, left, right) {
if (left > right) return;
/*
以最后一个为标准,比它小的移动到前面,
存储一个index。index最后一个是它,前面是比它小的数。
*/
var storeIndex = partition(arr, left, right);
// 然后依次递归调用index左边和右边的项
sort(arr, left, storeIndex - 1);
sort(arr, storeIndex + 1, right);
}
sort(arr, 0, arr.length - 1);
return arr;
}