斐波那次数列

// 节省内存空间,没有重复计算
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;
}