JavaScript专题系列(3)
关注公众号
获取最新福利
微信公众号

JavaScript专题系列(3)

时间: 12/12/2017作者: ll浏览量: 1677

本专题分三部分:

  1. JavaScript专题系列(1)
  2. JavaScript专题系列(2)
  3. JavaScript专题系列(3)

14. 惰性函数

14.1 需求

我们现在需要写一个 foo 函数,这个函数返回首次调用时的 Date 对象,注意是首次。

解决一:普通方法

var t;
function foo() {
    if (t) return t;
    t = new Date()
    return t;
}

问题有两个,一是污染了全局变量,二是每次调用 foo 的时候都需要进行一次判断。

解决二:闭包

我们很容易想到用闭包避免污染全局变量。

var foo = (function() {
    var t;
    return function() {
        if (t) return t;
        t = new Date();
        return t;
    }
})();

然而还是没有解决调用时都必须进行一次判断的问题。

解决三:函数对象

函数也是一种对象,利用这个特性,我们也可以解决这个问题。

function foo() {
    if (foo.t) return foo.t;
    foo.t = new Date();
    return foo.t;
}

依旧没有解决调用时都必须进行一次判断的问题。

解决四:惰性函数

不错,惰性函数就是解决每次都要进行判断的这个问题,解决原理很简单,重写函数。

var foo = function() {
    var t = new Date();
    foo = function() {
        return t;
    };
    return foo();
};

14.2 更多应用

DOM 事件添加中,为了兼容现代浏览器和 IE 浏览器,我们需要对浏览器环境进行一次判断:

// 简化写法
function addEvent (type, el, fn) {
    if (window.addEventListener) {
        el.addEventListener(type, fn, false);
    }
    else if(window.attachEvent){
        el.attachEvent('on' + type, fn);
    }
}

问题在于我们每当使用一次 addEvent 时都会进行一次判断。

利用惰性函数,我们可以这样做:

function addEvent (type, el, fn) {
    if (window.addEventListener) {
        addEvent = function (type, el, fn) {
            el.addEventListener(type, fn, false);
        }
    }
    else if(window.attachEvent){
        addEvent = function (type, el, fn) {
            el.attachEvent('on' + type, fn);
        }
    }
}

这段函数,在第一次执行的时候,addEvent并不会绑定事件,只是对addEvent重新赋值了一次,可以这样修改:

function addEvent (type, el, fn) {
    if (window.addEventListener) {
        el.addEventListener(type, fn, false);
        addEvent = function (type, el, fn) {
            el.addEventListener(type, fn, false);
        }
    }
    else if(window.attachEvent){
        el.attachEvent('on' + type, fn);
        addEvent = function (type, el, fn) {
            el.attachEvent('on' + type, fn);
        }
    }
}

或者立即执行它,或者直接addEvent()先执行一次。

当然我们也可以使用闭包的形式:

var addEvent = (function(){
    if (window.addEventListener) {
        return function (type, el, fn) {
            el.addEventListener(type, fn, false);
        }
    }
    else if(window.attachEvent){
        return function (type, el, fn) {
            el.attachEvent('on' + type, fn);
        }
    }
})();

当我们每次都需要进行条件判断,其实只需要判断一次,接下来的使用方式都不会发生改变的时候,想想是否可以考虑使用惰性函数。

重要参考

Lazy Function Definition Pattern

15. 函数组合

15.1 需求

我们需要写一个函数,输入 'kevin',返回 'HELLO, KEVIN'。

尝试

var toUpperCase = function(x) { return x.toUpperCase(); };
var hello = function(x) { return 'HELLO, ' + x; };

var greet = function(x){
    return hello(toUpperCase(x));
};

greet('kevin');

还好我们只有两个步骤,首先小写转大写,然后拼接字符串。如果有更多的操作,greet 函数里就需要更多的嵌套,类似于 fn3(fn2(fn1(fn0(x))))。

优化

试想我们写个 compose 函数:

var compose = function(f,g) {
    return function(x) {
        return f(g(x));
    };
};

greet 函数就可以被优化为:

var greet = compose(hello, toUpperCase);
greet('kevin');

利用 compose 将两个函数组合成一个函数,让代码从右向左运行,而不是由内而外运行,可读性大大提升。这便是函数组合。

但是现在的 compose 函数也只是能支持两个参数,如果有更多的步骤呢?我们岂不是要这样做:

compose(d, compose(c, compose(b, a)))

为什么我们不写一个帅气的 compose 函数支持传入多个函数呢?这样就变成了:

compose(d, c, b, a)

compose

我们直接抄袭 underscore 的 compose 函数的实现:

function compose() {
    var args = arguments;
    var start = args.length - 1;
    return function() {
        var i = start;
        var result = args[start].apply(this, arguments);
        while (i--) result = args[i].call(this, result);
        return result;
    };
};

现在的 compose 函数已经可以支持多个函数了,然而有了这个又有什么用呢?

在此之前,我们先了解一个概念叫做 pointfree。

pointfree

pointfree 指的是函数无须提及将要操作的数据是什么样的。依然是以最初的需求为例:

// 需求:输入 'kevin',返回 'HELLO, KEVIN'。

// 非 pointfree,因为提到了数据:name
var greet = function(name) {
    return ('hello ' + name).toUpperCase();
}

// pointfree
// 先定义基本运算,这些可以封装起来复用
var toUpperCase = function(x) { return x.toUpperCase(); };
var hello = function(x) { return 'HELLO, ' + x; };

var greet = compose(hello, toUpperCase);
greet('kevin');

我们再举个稍微复杂一点的例子,为了方便书写,我们需要借助在[《JavaScript专题之函数柯里化》]中写到的 curry 函数:

// 需求:输入 'kevin daisy kelly',返回 'K.D.K'

// 非 pointfree,因为提到了数据:name
var initials = function (name) {
    return name.split(' ').map(compose(toUpperCase, head)).join('. ');
};

// pointfree
// 先定义基本运算
var split = curry(function(separator, str) { return str.split(separator) })
var head = function(str) { return str.slice(0, 1) }
var toUpperCase = function(str) { return str.toUpperCase() }
var join = curry(function(separator, arr) { return arr.join(separator) })
var map = curry(function(fn, arr) { return arr.map(fn) })

var initials = compose(join('.'), map(compose(toUpperCase, head)), split(' '));

initials("kevin daisy kelly");

从这个例子中我们可以看到,利用柯里化(curry)和函数组合 (compose) 非常有助于实现 pointfree。

也许你会想,这种写法好麻烦呐,我们还需要定义那么多的基础函数……可是如果有工具库已经帮你写好了呢?比如ramda.js

// 使用 ramda.js
var initials = R.compose(R.join('.'), R.map(R.compose(R.toUpper, R.head)), R.split(' '));

而且你也会发现:

Pointfree 的本质就是使用一些通用的函数,组合出各种复杂运算。上层运算不要直接操作数据,而是通过底层函数去处理。即不使用所要处理的值,只合成运算过程。

那么使用 pointfree 模式究竟有什么好处呢?

pointfree 模式能够帮助我们减少不必要的命名,让代码保持简洁和通用,更符合语义,更容易复用,测试也变得轻而易举。

15.2 实战

这个例子来自于Favoring Curry

假设我们从服务器获取这样的数据:

var data = {
    result: "SUCCESS",
    tasks: [
        {id: 104, complete: false,            priority: "high",
                  dueDate: "2013-11-29",      username: "Scott",
                  title: "Do something",      created: "9/22/2013"},
        {id: 105, complete: false,            priority: "medium",
                  dueDate: "2013-11-22",      username: "Lena",
                  title: "Do something else", created: "9/22/2013"},
        {id: 107, complete: true,             priority: "high",
                  dueDate: "2013-11-22",      username: "Mike",
                  title: "Fix the foo",       created: "9/22/2013"},
        {id: 108, complete: false,            priority: "low",
                  dueDate: "2013-11-15",      username: "Punam",
                  title: "Adjust the bar",    created: "9/25/2013"},
        {id: 110, complete: false,            priority: "medium",
                  dueDate: "2013-11-15",      username: "Scott",
                  title: "Rename everything", created: "10/2/2013"},
        {id: 112, complete: true,             priority: "high",
                  dueDate: "2013-11-27",      username: "Lena",
                  title: "Alter all quuxes",  created: "10/5/2013"}
    ]
};

我们需要写一个名为 getIncompleteTaskSummaries 的函数,接收一个 username 作为参数,从服务器获取数据,然后筛选出这个用户的未完成的任务的 ids、priorities、titles、和 dueDate 数据,并且按照日期升序排序。

以 Scott 为例,最终筛选出的数据为:

[
    {id: 110, title: "Rename everything", 
        dueDate: "2013-11-15", priority: "medium"},
    {id: 104, title: "Do something", 
        dueDate: "2013-11-29", priority: "high"}
]

普通的方式为:

// 第一版 过程式编程
var fetchData = function() {
    // 模拟
    return Promise.resolve(data)
};

var getIncompleteTaskSummaries = function(membername) {
     return fetchData()
         .then(function(data) {
             return data.tasks;
         })
         .then(function(tasks) {
             return tasks.filter(function(task) {
                 return task.username == membername
             })
         })
         .then(function(tasks) {
             return tasks.filter(function(task) {
                 return !task.complete
             })
         })
         .then(function(tasks) {
             return tasks.map(function(task) {
                 return {
                     id: task.id,
                     dueDate: task.dueDate,
                     title: task.title,
                     priority: task.priority
                 }
             })
         })
         .then(function(tasks) {
             return tasks.sort(function(first, second) {
                 var a = first.dueDate,
                     b = second.dueDate;
                 return a < b ? -1 : a > b ? 1 : 0;
             });
         })
         .then(function(task) {
             console.log(task)
         })
};

getIncompleteTaskSummaries('Scott')

如果使用 pointfree 模式:

// 第二版 pointfree 改写
var fetchData = function() {
    return Promise.resolve(data)
};

// 编写基本函数
var prop = curry(function(name, obj) {
    return obj[name];
});

var propEq = curry(function(name, val, obj) {
    return obj[name] === val;
});

var filter = curry(function(fn, arr) {
    return arr.filter(fn)
});

var map = curry(function(fn, arr) {
    return arr.map(fn)
});

var pick = curry(function(args, obj){
    var result = {};
    for (var i = 0; i < args.length; i++) {
        result[args[i]] = obj[args[i]]
    }
    return result;
});

var sortBy = curry(function(fn, arr) {
    return arr.sort(function(a, b){
        var a = fn(a),
            b = fn(b);
        return a < b ? -1 : a > b ? 1 : 0;
    })
});

var getIncompleteTaskSummaries = function(membername) {
    return fetchData()
        .then(prop('tasks'))
        .then(filter(propEq('username', membername)))
        .then(filter(propEq('complete', false)))
        .then(map(pick(['id', 'dueDate', 'title', 'priority'])))
        .then(sortBy(prop('dueDate')))
        .then(console.log)
};

getIncompleteTaskSummaries('Scott')

如果直接使用 ramda.js,你可以省去编写基本函数:

// 第三版 使用 ramda.js
var fetchData = function() {
    return Promise.resolve(data)
};

var getIncompleteTaskSummaries = function(membername) {
    return fetchData()
        .then(R.prop('tasks'))
        .then(R.filter(R.propEq('username', membername)))
        .then(R.filter(R.propEq('complete', false)))
        .then(R.map(R.pick(['id', 'dueDate', 'title', 'priority'])))
        .then(R.sortBy(R.prop('dueDate')))
        .then(console.log)
};

getIncompleteTaskSummaries('Scott')

当然了,利用 compose,你也可以这样写:

// 第四版 使用 compose
var fetchData = function() {
    return Promise.resolve(data)
};

var getIncompleteTaskSummaries = function(membername) {
    return fetchData()
        .then(R.compose(
            console.log,
            R.sortBy(R.prop('dueDate')),
            R.map(R.pick(['id', 'dueDate', 'title', 'priority'])
            ),
            R.filter(R.propEq('complete', false)),
            R.filter(R.propEq('username', membername)),
            R.prop('tasks'),
        ))
};

getIncompleteTaskSummaries('Scott')

compose 是从右到左依此执行,当然你也可以写一个从左到右的版本,但是从右向左执行更加能够反映数学上的含义。

ramda.js 提供了一个 R.pipe 函数,可以做的从左到右,以上可以改写为:

// 第五版 使用 R.pipe
var getIncompleteTaskSummaries = function(membername) {
    return fetchData()
        .then(R.pipe(
            R.prop('tasks'),
            R.filter(R.propEq('username', membername)),
            R.filter(R.propEq('complete', false)),
            R.map(R.pick(['id', 'dueDate', 'title', 'priority'])
            R.sortBy(R.prop('dueDate')),
            console.log,
        ))
};

关于组合函数,这里另外推介一篇reduce与redux中compose函数

16. 函数记忆

16.1 定义

函数记忆是指将上次的计算结果缓存起来,当下次调用时,如果遇到相同的参数,就直接返回缓存中的数据。

举个例子:

function add(a, b) {
    return a + b;
}

// 假设 memoize 可以实现函数记忆
var memoizedAdd = memoize(add);

memoizedAdd(1, 2) // 3
memoizedAdd(1, 2) // 相同的参数,第二次调用时,从缓存中取出数据,而非重新计算一次

原理

实现这样一个 memoize 函数很简单,原理上只用把参数和对应的结果数据存到一个对象中,调用时,判断参数对应的数据是否存在,存在就返回对应的结果数据。

第一版

我们来写一版:

// 第一版 (来自《JavaScript权威指南》)
function memoize(f) {
    var cache = {};
    return function(){
        var key = arguments.length + Array.prototype.join.call(arguments, ",");
        if (key in cache) {
            return cache[key]
        }
        else {
            return cache[key] = f.apply(this, arguments)
        }
    }
}

我们来测试一下:

var add = function(a, b, c) {
  return a + b + c
}

var memoizedAdd = memoize(add)

console.time('use memoize')
for(var i = 0; i < 100000; i++) {
    memoizedAdd(1, 2, 3)
}
console.timeEnd('use memoize')

console.time('not use memoize')
for(var i = 0; i < 100000; i++) {
    add(1, 2, 3)
}
console.timeEnd('not use memoize')

在 Chrome 中,使用 memoize 大约耗时 60ms,如果我们不使用函数记忆,大约耗时 1.3 ms 左右。

注意

什么,我们使用了看似高大上的函数记忆,结果却更加耗时,这个例子近乎有 60 倍呢!

所以,函数记忆也并不是万能的,你看这个简单的场景,其实并不适合用函数记忆。

需要注意的是,函数记忆只是一种编程技巧,本质上是牺牲算法的空间复杂度以换取更优的时间复杂度,在客户端 JavaScript 中代码的执行时间复杂度往往成为瓶颈,因此在大多数场景下,这种牺牲空间换取时间的做法以提升程序执行效率的做法是非常可取的。

第二版

因为第一版使用了 join 方法,我们很容易想到当参数是对象的时候,就会自动调用 toString 方法转换成 [Object object],再拼接字符串作为 key 值。我们写个 demo 验证一下这个问题:

var propValue = function(obj){
    return obj.value
}

var memoizedAdd = memoize(propValue)

console.log(memoizedAdd({value: 1})) // 1
console.log(memoizedAdd({value: 2})) // 1

两者都返回了 1,显然是有问题的,所以我们看看 underscore 的 memoize 函数是如何实现的:

// 第二版 (来自 underscore 的实现)
var memoize = function(func, hasher) {
    var memoize = function(key) {
        var cache = memoize.cache;
        var address = '' + (hasher ? hasher.apply(this, arguments) : key);
        if (!cache[address]) {
            cache[address] = func.apply(this, arguments);
        }
        return cache[address];
    };
    memoize.cache = {};
    return memoize;
};

从这个实现可以看出,underscore 默认使用 function 的第一个参数作为 key,所以如果直接使用

var add = function(a, b, c) {
  return a + b + c
}

var memoizedAdd = memoize(add)

memoizedAdd(1, 2, 3) // 6
memoizedAdd(1, 2, 4) // 6

肯定是有问题的,如果要支持多参数,我们就需要传入 hasher 函数,自定义存储的 key 值。所以我们考虑使用 JSON.stringify:

var memoizedAdd = memoize(add, function(){
    var args = Array.prototype.slice.call(arguments)
    return JSON.stringify(args)
})

console.log(memoizedAdd(1, 2, 3)) // 6
console.log(memoizedAdd(1, 2, 4)) // 7

如果使用 JSON.stringify,参数是对象的问题也可以得到解决,因为存储的是对象序列化后的字符串。

16.2 适用场景

我们以斐波那契数列为例:

var count = 0;
var fibonacci = function(n){
    count++;
    return n < 2? n : fibonacci(n-1) + fibonacci(n-2);
};
for (var i = 0; i <= 10; i++){
    fibonacci(i)
}

console.log(count) // 453

我们会发现最后的 count 数为 453,也就是说 fibonacci 函数被调用了 453 次!也许你会想,我只是循环到了 10,为什么就被调用了这么多次,所以我们来具体分析下:

当执行 fib(0) 时,调用 1 次

当执行 fib(1) 时,调用 1 次

当执行 fib(2) 时,相当于 fib(1) + fib(0) 加上 fib(2) 本身这一次,共 1 + 1 + 1 = 3 次

当执行 fib(3) 时,相当于 fib(2) + fib(1) 加上 fib(3) 本身这一次,共 3 + 1 + 1 = 5 次

当执行 fib(4) 时,相当于 fib(3) + fib(2) 加上 fib(4) 本身这一次,共 5 + 3 + 1 = 9 次

当执行 fib(5) 时,相当于 fib(4) + fib(3) 加上 fib(5) 本身这一次,共 9 + 5 + 1 = 15 次

当执行 fib(6) 时,相当于 fib(5) + fib(4) 加上 fib(6) 本身这一次,共 15 + 9 + 1 = 25 次

当执行 fib(7) 时,相当于 fib(6) + fib(5) 加上 fib(7) 本身这一次,共 25 + 15 + 1 = 41 次

当执行 fib(8) 时,相当于 fib(7) + fib(6) 加上 fib(8) 本身这一次,共 41 + 25 + 1 = 67 次

当执行 fib(9) 时,相当于 fib(8) + fib(7) 加上 fib(9) 本身这一次,共 67 + 41 + 1 = 109 次

当执行 fib(10) 时,相当于 fib(9) + fib(8) 加上 fib(10) 本身这一次,共 109 + 67 + 1 = 177

所以执行的总次数为:177 + 109 + 67 + 41 + 25 + 15 + 9 + 5 + 3 + 1 + 1 = 453 次!

如果我们使用函数记忆呢?

var count = 0;
var fibonacci = function(n) {
    count++;
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};

fibonacci = memoize(fibonacci)

for (var i = 0; i <= 10; i++) {
    fibonacci(i)
}

console.log(count) // 12

我们会发现最后的总次数为 12 次,因为使用了函数记忆,调用次数从 453 次降低为了 12 次!

兴奋的同时不要忘记思考:为什么会是 12 次呢?

从 0 到 10 的结果各储存一遍,应该是 11 次呐?咦,那多出来的一次是从哪里来的?

所以我们还需要认真看下我们的写法,在我们的写法中,其实我们用生成的 fibonacci 函数覆盖了原本了 fibonacci 函数,当我们执行 fibonacci(0) 时,执行一次函数,cache 为 {0: 0},但是当我们执行 fibonacci(2) 的时候,执行 fibonacci(1) + fibonacci(0),因为 fibonacci(0) 的值为 0,!cache[address] 的结果为 true,又会执行一次 fibonacci 函数。原来,多出来的那一次是在这里!

多说一句

也许你会觉得在日常开发中又用不到 fibonacci,这个例子感觉实用价值不高呐,其实,这个例子是用来表明一种使用的场景,也就是如果需要大量重复的计算,或者大量计算又依赖于之前的结果,便可以考虑使用函数记忆。而这种场景,当你遇到的时候,你就会知道的。

17. 递归

17.1 定义

程序调用自身的编程技巧称为递归(recursion)。

阶乘

以阶乘为例:

function factorial(n) {
    if (n == 1) return n;
    return n * factorial(n - 1)
}

console.log(factorial(5)) // 5 * 4 * 3 * 2 * 1 = 120

示意图(图片来自 wwww.penjee.com):

斐波那契数列

在[《JavaScript专题之函数记忆》]中讲到过的斐波那契数列也使用了递归:

function fibonacci(n){
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(5)) // 1 1 2 3 5

递归条件

从这两个例子中,我们可以看出:

构成递归需具备边界条件、递归前进段和递归返回段,当边界条件不满足时,递归前进,当边界条件满足时,递归返回。阶乘中的 n == 1 和 斐波那契数列中的 n < 2 都是边界条件。

总结一下递归的特点:

  1. 子问题须与原始问题为同样的事,且更为简单;
  2. 不能无限制地调用本身,须有个出口,化简为非递归状况处理。

了解这些特点可以帮助我们更好的编写递归函数。

执行上下文栈

《JavaScript深入之执行上下文栈》中,我们知道:

当执行一个函数的时候,就会创建一个执行上下文,并且压入执行上下文栈,当函数执行完毕的时候,就会将函数的执行上下文从栈中弹出。

试着对阶乘函数分析执行的过程,我们会发现,JavaScript 会不停的创建执行上下文压入执行上下文栈,对于内存而言,维护这么多的执行上下文也是一笔不小的开销呐!那么,我们该如何优化呢?

答案就是尾调用。

尾调用

尾调用,是指函数内部的最后一个动作是函数调用。该调用的返回值,直接返回给函数。

举个例子:

// 尾调用
function f(x){
    return g(x);
}

然而

// 非尾调用
function f(x){
    return g(x) + 1;
}

并不是尾调用,因为 g(x) 的返回值还需要跟 1 进行计算后,f(x)才会返回值。

两者又有什么区别呢?答案就是执行上下文栈的变化不一样。

为了模拟执行上下文栈的行为,让我们定义执行上下文栈是一个数组:

 ECStack = [];

我们模拟下第一个尾调用函数执行时的执行上下文栈变化:

// 伪代码
ECStack.push(<f> functionContext);

ECStack.pop();

ECStack.push(<g> functionContext);

ECStack.pop();

我们再来模拟一下第二个非尾调用函数执行时的执行上下文栈变化:

ECStack.push(<f> functionContext);

ECStack.push(<g> functionContext);

ECStack.pop();

ECStack.pop();

也就说尾调用函数执行时,虽然也调用了一个函数,但是因为原来的的函数执行完毕,执行上下文会被弹出,执行上下文栈中相当于只多压入了一个执行上下文。然而非尾调用函数,就会创建多个执行上下文压入执行上下文栈。

函数调用自身,称为递归。如果尾调用自身,就称为尾递归。

所以我们只用把阶乘函数改造成一个尾递归形式,就可以避免创建那么多的执行上下文。但是我们该怎么做呢?

阶乘函数优化

我们需要做的就是把所有用到的内部变量改写成函数的参数,以阶乘函数为例:

function factorial(n, res) {
    if (n == 1) return res;
    return factorial(n - 1, n * res)
}

console.log(factorial(4, 1)) // 24

然而这个很奇怪呐……我们计算 4 的阶乘,结果函数要传入 4 和 1,我就不能只传入一个 4 吗?

这个时候就要用到我们在[《JavaScript专题之偏函数》]中编写的 partial 函数了:

var newFactorial = partial(factorial, _, 1)

newFactorial(4) // 24

17.2 应用

如果你看过JavaScript 专题系列的文章,你会发现递归有着很多的应用。

作为专题系列的第十八篇,我们来盘点下之前的文章中都有哪些涉及到了递归:

  1. 《JavaScript 专题之数组扁平化》
function flatten(arr) {
    return arr.reduce(function(prev, next){
        return prev.concat(Array.isArray(next) ? flatten(next) : next)
    }, [])
}
  1. 《JavaScript 专题之深浅拷贝》
var deepCopy = function(obj) {
    if (typeof obj !== 'object') return;
    var newObj = obj instanceof Array ? [] : {};
    for (var key in obj) {
        if (obj.hasOwnProperty(key)) {
            newObj[key] = typeof obj[key] === 'object' ? deepCopy(obj[key]) : obj[key];
        }
    }
    return newObj;
}
  1. 《JavaScript 专题之从零实现jQuery的extend》
// 非完整版本,完整版本请点击查看具体的文章
function extend() {

    ...

    // 循环遍历要复制的对象们
    for (; i < length; i++) {
        // 获取当前对象
        options = arguments[i];
        // 要求不能为空 避免extend(a,,b)这种情况
        if (options != null) {
            for (name in options) {
                // 目标属性值
                src = target[name];
                // 要复制的对象的属性值
                copy = options[name];

                if (deep && copy && typeof copy == 'object') {
                    // 递归调用
                    target[name] = extend(deep, src, copy);
                }
                else if (copy !== undefined){
                    target[name] = copy;
                }
            }
        }
    }

    ...

};
  1. 《JavaScript 专题之如何判断两个对象相等》
// 非完整版本,完整版本请点击查看具体的文章
// 属于间接调用
function eq(a, b, aStack, bStack) {

    ...

    // 更复杂的对象使用 deepEq 函数进行深度比较
    return deepEq(a, b, aStack, bStack);
};

function deepEq(a, b, aStack, bStack) {

    ...

    // 数组判断
    if (areArrays) {

        length = a.length;
        if (length !== b.length) return false;

        while (length--) {
            if (!eq(a[length], b[length], aStack, bStack)) return false;
        }
    }
    // 对象判断
    else {

        var keys = Object.keys(a),
            key;
        length = keys.length;

        if (Object.keys(b).length !== length) return false;
        while (length--) {

            key = keys[length];
            if (!(b.hasOwnProperty(key) && eq(a[key], b[key], aStack, bStack))) return false;
        }
    }

}
  1. 《JavaScript 专题之函数柯利化》
// 非完整版本,完整版本请点击查看具体的文章
function curry(fn, args) {
    length = fn.length;

    args = args || [];

    return function() {

        var _args = args.slice(0),

            arg, i;

        for (i = 0; i < arguments.length; i++) {

            arg = arguments[i];

            _args.push(arg);

        }
        if (_args.length < length) {
            return curry.call(this, fn, _args);
        }
        else {
            return fn.apply(this, _args);
        }
    }
}

写在最后

递归的内容远不止这些,比如还有汉诺塔、二叉树遍历等递归场景,本篇就不过多展开。

18. 乱序

乱序

乱序的意思就是将数组打乱。

嗯,没有了,直接看代码吧。

18.1 Math.random

一个经常会遇见的写法是使用 Math.random():

var values = [1, 2, 3, 4, 5];

values.sort(function(){
    return Math.random() - 0.5;
});

console.log(values)

Math.random() - 0.5随机得到一个正数、负数或是 0,如果是正数则降序排列,如果是负数则升序排列,如果是 0 就不变,然后不断的升序或者降序,最终得到一个乱序的数组。

看似很美好的一个方案,实际上,效果却不尽如人意。不信我们写个 demo 测试一下:

var times = [0, 0, 0, 0, 0];

for (var i = 0; i < 100000; i++) {

    let arr = [1, 2, 3, 4, 5];

    arr.sort(() => Math.random() - 0.5);

    times[arr[4]-1]++;

}

console.log(times)

测试原理是:将 [1, 2, 3, 4, 5] 乱序 10 万次,计算乱序后的数组的最后一个元素是 1、2、3、4、5 的次数分别是多少。

一次随机的结果为:

[30636, 30906, 20456, 11743, 6259]

该结果表示 10 万次中,数组乱序后的最后一个元素是 1 的情况共有 30636 次,是 2 的情况共有 30906 次,其他依此类推。

我们会发现,最后一个元素为 5 的次数远远低于为 1 的次数,所以这个方案是有问题的。

可是我明明感觉这个方法还不错呐?初见时还有点惊艳的感觉,为什么会有问题呢?

是的!我很好奇!

18.2 插入排序

如果要追究这个问题所在,就必须了解 sort 函数的原理,然而 ECMAScript 只规定了效果,没有规定实现的方式,所以不同浏览器实现的方式还不一样。

为了解决这个问题,我们以 v8 为例,v8 在处理 sort 方法时,当目标数组长度小于 10 时,使用插入排序;反之,使用快速排序和插入排序的混合排序。

所以我们来看看 v8 的源码,因为是用 JavaScript 写的,大家也是可以看懂的。

源码地址:https://github.com/v8/v8/blob/master/src/js/array.js

为了简化篇幅,我们对[1, 2, 3]这个数组进行分析,数组长度为 3,此时采用的是插入排序。

插入排序的源码是:

function InsertionSort(a, from, to) {
    for (var i = from + 1; i < to; i++) {
        var element = a[i];
        for (var j = i - 1; j >= from; j--) {
            var tmp = a[j];
            var order = comparefn(tmp, element);
            if (order > 0) {
                a[j + 1] = tmp;
            } else {
                break;
            }
        }
        a[j + 1] = element;
    }
};

其原理在于将第一个元素视为有序序列,遍历数组,将之后的元素依次插入这个构建的有序序列中。

我们来个简单的示意图:

具体分析

明白了插入排序的原理,我们来具体分析下 [1, 2, 3] 这个数组乱序的结果。

演示代码为:

var values = [1, 2, 3];

values.sort(function(){
    return Math.random() - 0.5;
});

注意此时 sort 函数底层是使用插入排序实现,InsertionSort 函数的 from 的值为 0,to 的值为 3。

我们开始逐步分析乱序的过程:

因为插入排序视第一个元素为有序的,所以数组的外层循环从 i = 1 开始,a[i] 值为 2,此时内层循环遍历,比较 compare(1, 2),因为 Math.random() - 0.5 的结果有 50% 的概率小于 0 ,有 50% 的概率大于 0,所以有 50% 的概率数组变成 [2, 1, 3],50% 的结果不变,数组依然为 [1, 2, 3]。

假设依然是 [1, 2, 3],我们再进行一次分析,接着遍历,i = 2,a[i] 的值为 3,此时内层循环遍历,比较 compare(2, 3):

有 50% 的概率数组不变,依然是 [1, 2, 3],然后遍历结束。

有 50% 的概率变成 [1, 3, 2],因为还没有找到 3 正确的位置,所以还会进行遍历,所以在这 50% 的概率中又会进行一次比较,compare(1, 3),有 50% 的概率不变,数组为 [1, 3, 2],此时遍历结束,有 50% 的概率发生变化,数组变成 [3, 1, 2]。

综上,在 [1, 2, 3] 中,有 50% 的概率会变成 [1, 2, 3],有 25% 的概率会变成 [1, 3, 2],有 25% 的概率会变成 [3, 1, 2]。

另外一种情况 [2, 1, 3] 与之分析类似,我们将最终的结果汇总成一个表格: image.png 为了验证这个推算是否准确,我们写个 demo 测试一下:

var times = 100000;
var res = {};

for (var i = 0; i < times; i++) {

    var arr = [1, 2, 3];
    arr.sort(() => Math.random() - 0.5);

    var key = JSON.stringify(arr);
    res[key] ? res[key]++ :  res[key] = 1;
}

// 为了方便展示,转换成百分比
for (var key in res) {
    res[key] = res[key] / times * 100 + '%'
}

console.log(res)

这是一次随机的结果: image.png 我们会发现,乱序后,3 还在原位置(即 [1, 2, 3] 和 [2, 1, 3]) 的概率有 50% 呢。

所以根本原因在于什么呢?其实就在于在插入排序的算法中,当待排序元素跟有序元素进行比较时,一旦确定了位置,就不会再跟位置前面的有序元素进行比较,所以就乱序的不彻底。

那么如何实现真正的乱序呢?而这就要提到经典的 Fisher–Yates 算法。

18.3 Fisher–Yates

为什么叫 Fisher–Yates 呢? 因为这个算法是由 Ronald Fisher 和 Frank Yates 首次提出的。

话不多说,我们直接看 JavaScript 的实现:

function shuffle(a) {
    var j, x, i;
    for (i = a.length; i; i--) {
        j = Math.floor(Math.random() * i);
        x = a[i - 1];
        a[i - 1] = a[j];
        a[j] = x;
    }
    return a;
}

原理很简单,就是遍历数组元素,然后将当前元素与以后随机位置的元素进行交换,从代码中也可以看出,这样乱序的就会更加彻底。

如果利用 ES6,代码还可以简化成:

function shuffle(a) {
    for (let i = a.length; i; i--) {
        let j = Math.floor(Math.random() * i);
        [a[i - 1], a[j]] = [a[j], a[i - 1]];
    }
    return a;
}

还是再写个 demo 测试一下吧:

var times = 100000;
var res = {};

for (var i = 0; i < times; i++) {
    var arr = shuffle([1, 2, 3]);

    var key = JSON.stringify(arr);
    res[key] ? res[key]++ :  res[key] = 1;
}

// 为了方便展示,转换成百分比
for (var key in res) {
    res[key] = res[key] / times * 100 + '%'
}

console.log(res)

这是一次随机的结果: image.png 真正的实现了乱序的效果!

19. 解读 v8 排序源码

前言

v8 是 Chrome 的 JavaScript 引擎,其中关于数组的排序完全采用了 JavaScript 实现。

排序采用的算法跟数组的长度有关,当数组长度小于等于 10 时,采用插入排序,大于 10 的时候,采用快速排序。(当然了,这种说法并不严谨)。

我们先来看看插入排序和快速排序。

19.1 插入排序

原理

将第一个元素视为有序序列,遍历数组,将之后的元素依次插入这个构建的有序序列中。

图示

实现

function insertionSort(arr) {
    for (var i = 1; i < arr.length; i++) {
        var element = arr[i];
        for (var j = i - 1; j >= 0; j--) {
            var tmp = arr[j];
            var order = tmp - element;
            if (order > 0) {
                arr[j + 1] = tmp;
            } else {
                break;
            }
        }
        arr[j + 1] = element;
    }
    return arr;
}

var arr = [6, 5, 4, 3, 2, 1];
console.log(insertionSort(arr));

时间复杂度

时间复杂度是指执行算法所需要的计算工作量,它考察当输入值大小趋近无穷时的情况,一般情况下,算法中基本操作重复执行的次数是问题规模 n 的某个函数。

最好情况:数组升序排列,时间复杂度为:O(n)

最坏情况:数组降序排列,时间复杂度为:O(n²)

稳定性

稳定性,是指相同的元素在排序后是否还保持相对的位置。

要注意的是对于不稳定的排序算法,只要举出一个实例,即可说明它的不稳定性;而对于稳定的排序算法,必须对算法进行分析从而得到稳定的特性。

比如 [3, 3, 1],排序后,还是 [3, 3, 1],但是其实是第二个 3 在 第一个 3 前,那这就是不稳定的排序算法。

插入排序是稳定的算法。

优势

当数组是快要排序好的状态或者问题规模比较小的时候,插入排序效率更高。这也是为什么 v8 会在数组长度小于等于 10 的时候采用插入排序。

19.2 快速排序

原理

  1. 选择一个元素作为"基准"
  2. 小于"基准"的元素,都移到"基准"的左边;大于"基准"的元素,都移到"基准"的右边。
  3. 对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

示例

示例和下面的实现方式来源于阮一峰老师的《快速排序(Quicksort)的Javascript实现》

以数组 [85, 24, 63, 45, 17, 31, 96, 50] 为例:

第一步,选择中间的元素 45 作为"基准"。(基准值可以任意选择,但是选择中间的值比较容易理解。)

image.png

第二步,按照顺序,将每个元素与"基准"进行比较,形成两个子集,一个"小于45",另一个"大于等于45"。

image.png

第三步,对两个子集不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

image.png

实现

然而这种实现方式需要额外的空间用来储存左右子集,所以还有一种原地(in-place)排序的实现方式。 ```var quickSort = function(arr) {   if (arr.length <= 1) { return arr; } // 取数组的中间元素作为基准   var pivotIndex = Math.floor(arr.length / 2);   var pivot = arr.splice(pivotIndex, 1)[0];

  var left = [];   var 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)); };

然而这种实现方式需要额外的空间用来储存左右子集,所以还有一种原地(in-place)排序的实现方式。

**图示**

我们来看看原地排序的实现图示:
![](https://raw.githubusercontent.com/mqyqingfeng/Blog/master/Images/sort/quicksort.gif)

为了让大家看明白快速排序的原理,我调慢了执行速度。

在这张示意图里,基准的取值规则是取最左边的元素,黄色代表当前的基准,绿色代表小于基准的元素,紫色代表大于基准的元素。

我们会发现,绿色的元素会紧挨在基准的右边,紫色的元素会被移到后面,然后交换基准和绿色的最后一个元素,此时,基准处于正确的位置,即前面的元素都小于基准值,后面的元素都大于基准值。然后再对前面的和后面的多个元素取基准,做排序。

**in-place实现**

function quickSort(arr) { // 交换元素 function swap(arr, a, b) { var temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; }

function partition(arr, left, right) {
    var pivot = arr[left];
    var storeIndex = left;

    for (var i = left + 1; i <= right; i++) {
        if (arr[i] < pivot) {
            swap(arr, ++storeIndex, i);
        }
    }

    swap(arr, left, storeIndex);

    return storeIndex;
}

function sort(arr, left, right) {
    if (left < right) {
        var storeIndex = partition(arr, left, right);
        sort(arr, left, storeIndex - 1);
        sort(arr, storeIndex + 1, right);
    }
}

sort(arr, 0, arr.length - 1);

return arr;

}

console.log(quickSort(6, 7, 3, 4, 1, 5, 9, 2, 8))


**稳定性**

快速排序是不稳定的排序。如果要证明一个排序是不稳定的,你只用举出一个实例就行。

所以我们举一个呗~

就以数组 [1, 2, 3, 3, 4, 5] 为例,因为基准的选择不确定,假如选定了第三个元素(也就是第一个 3) 为基准,所有小于 3 的元素在前面,大于等于 3 的在后面,排序的结果没有问题。可是如果选择了第四个元素(也就是第二个 3 ),小于 3 的在基准前面,大于等于 3 的在基准后面,第一个 3 就会被移动到 第二个 3 后面,所以快速排序是不稳定的排序。

**时间复杂度**

阮一峰老师的实现中,基准取的是中间元素,而原地排序中基准取最左边的元素。快速排序的关键点就在于基准的选择,选取不同的基准时,会有不同性能表现。

快速排序的时间复杂度最好为 O(nlogn),可是为什么是 nlogn 呢?来一个并不严谨的证明:

在最佳情况下,每一次都平分整个数组。假设数组有 n 个元素,其递归的深度就为 log2n + 1,时间复杂度为 O(n)[(log2n + 1)],因为时间复杂度考察当输入值大小趋近无穷时的情况,所以会忽略低阶项,时间复杂度为:o(nlog2n)。

如果一个程序的运行时间是对数级的,则随着 n 的增大程序会渐渐慢下来。如果底数是 10,lg1000 等于 3,如果 n 为 1000000,lgn 等于 6,仅为之前的两倍。如果底数为 2,log21000 的值约为 10,log21000000 的值约为 19,约为之前的两倍。我们可以发现任意底数的一个对数函数其实都相差一个常数倍而已。所以我们认为 O(logn)已经可以表达所有底数的对数了,所以时间复杂度最后为: O(nlogn)。

而在最差情况下,如果对一个已经排序好的数组,每次选择基准元素时总是选择第一个元素或者最后一个元素,那么每次都会有一个子集是空的,递归的层数将达到 n,最后导致算法的时间复杂度退化为 O(n²)。

这也充分说明了一个基准的选择是多么的重要,而 v8 为了提高性能,就对基准的选择做了很多优化。

**v8基准选择**

v8 选择基准的原理是从头和尾之外再选择一个元素,然后三个值排序取中间值。

当数组长度大于 10 但是小于 1000 的时候,取中间位置的元素,实现代码为:

// 基准的下标 // >> 1 相当于除以 2 (忽略余数) third_index = from + ((to - from) >> 1);

当数组长度大于 1000 的时候,每隔 200 ~ 215 个元素取一个值,然后将这些值进行排序,取中间值的下标,实现的代码为:

// 简单处理过 function GetThirdIndex(a, from, to) { var t_array = new Array();

// & 位运算符
var increment = 200 + ((to - from) & 15);

var j = 0;
from += 1;
to -= 1;

for (var i = from; i < to; i += increment) {
    t_array[j] = [i, a[i]];
    j++;
}
// 对随机挑选的这些值进行排序
t_array.sort(function(a, b) {
    return comparefn(a[1], b[1]);
});
// 取中间值的下标
var third_index = t_array[t_array.length >> 1][0];
return third_index;

}

也许你会好奇 200 + ((to - from) & 15) 是什么意思?

& 表示是按位与,对整数操作数逐位执行布尔与操作。只有两个操作数中相对应的位都是 1,结果中的这一位才是 1。

以 15 & 127 为例:

15 二进制为: (0000 1111)

127 二进制为:(1111 1111)

按位与结果为:(0000 1111)= 15

所以 15 & 127 的结果为 15。

注意 15 的二进制为: 1111,这就意味着任何和 15 按位与的结果都会小于或者等于 15,这才实现了每隔 200 ~ 215 个元素取一个值。

**v8 源码**

终于到了看源码的时刻!源码地址为:[https://github.com/v8/v8/blob/master/src/js/array.js#L758](https://github.com/v8/v8/blob/master/src/js/array.js#L758)。

function InsertionSort(a, from, to) { for (var i = from + 1; i < to; i++) { var element = a[i]; for (var j = i - 1; j >= from; j--) { var tmp = a[j]; var order = comparefn(tmp, element); if (order > 0) { a[j + 1] = tmp; } else { break; } } a[j + 1] = element; } };

function QuickSort(a, from, to) {

var third_index = 0;
while (true) {
        // Insertion sort is faster for short arrays.
    if (to - from <= 10) {
        InsertionSort(a, from, to);
        return;
    }
    if (to - from > 1000) {
        third_index = GetThirdIndex(a, from, to);
    } else {
        third_index = from + ((to - from) >> 1);
    }
    // Find a pivot as the median of first, last and middle element.
    var v0 = a[from];
    var v1 = a[to - 1];
    var v2 = a[third_index];

    var c01 = comparefn(v0, v1);
    if (c01 > 0) {
        // v1 < v0, so swap them.
        var tmp = v0;
        v0 = v1;
        v1 = tmp;
    } // v0 <= v1.
    var c02 = comparefn(v0, v2);
    if (c02 >= 0) {
        // v2 <= v0 <= v1.
        var tmp = v0;
        v0 = v2;
        v2 = v1;
        v1 = tmp;
    } else {
        // v0 <= v1 && v0 < v2
        var c12 = comparefn(v1, v2);
        if (c12 > 0) {
            // v0 <= v2 < v1
            var tmp = v1;
            v1 = v2;
            v2 = tmp;
        }
    }

    // v0 <= v1 <= v2
    a[from] = v0;
    a[to - 1] = v2;

    var pivot = v1;

    var low_end = from + 1; // Upper bound of elements lower than pivot.
    var high_start = to - 1; // Lower bound of elements greater than pivot.

    a[third_index] = a[low_end];
    a[low_end] = pivot;

    // From low_end to i are elements equal to pivot.
    // From i to high_start are elements that haven't been compared yet.

    partition: for (var i = low_end + 1; i < high_start; i++) {
        var element = a[i];
        var order = comparefn(element, pivot);
        if (order < 0) {
            a[i] = a[low_end];
            a[low_end] = element;
            low_end++;
        } else if (order > 0) {
            do {
                high_start--;
                if (high_start == i) break partition;
                var top_elem = a[high_start];
                order = comparefn(top_elem, pivot);
            } while (order > 0);

            a[i] = a[high_start];
            a[high_start] = element;
            if (order < 0) {
                element = a[i];
                a[i] = a[low_end];
                a[low_end] = element;
                low_end++;
            }
        }
    }


    if (to - high_start < low_end - from) {
        QuickSort(a, high_start, to);
        to = low_end;
    } else {
        QuickSort(a, from, low_end);
        from = high_start;
    }
}

}

var arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0];

function comparefn(a, b) { return a - b }

QuickSort(arr, 0, arr.length) console.log(arr)

我们以数组 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] 为例,分析执行的过程。

1.执行 QuickSort 函数 参数 from 值为 0,参数 to 的值 112.10 < to - from < 1000 第三个基准元素的下标为 (0 + 11 >> 1) = 5,基准值 a[5] 为 53.比较 a[0] a[10] a[5] 的值,然后根据比较结果修改数组,数组此时为 [0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10]

4.将基准值和数组的第(from + 1)个即数组的第二个元素互换,此时数组为 [0, 5, 8, 7, 6, 9, 4, 3, 2, 1, 10],此时在基准值 5 前面的元素肯定是小于 5 的,因为第三步已经做了一次比较。后面的元素是未排序的。

我们接下来要做的就是把后面的元素中小于 5 的全部移到 5 的前面。

5.然后我们进入 partition 循环,我们依然以这个数组为例,单独抽出来写个 demo 讲一讲

// 假设代码执行到这里,为了方便演示,我们直接设置 low_end 等变量的值 // 可以直接复制到浏览器中查看数组变换效果 var a = [0, 5, 8, 7, 6, 9, 4, 3, 2, 1, 10] var low_end = 1; var high_start = 10; var pivot = 5;

console.log('起始数组为', a)

partition: for (var i = low_end + 1; i < high_start; i++) {

var element = a[i];
console.log('循环当前的元素为:', a[i])
var order = element - pivot;

if (order < 0) {
    a[i] = a[low_end];
    a[low_end] = element;
    low_end++;
    console.log(a)
}
else if (order > 0) {
    do {
        high_start--;
        if (high_start == i) break partition;
        var top_elem = a[high_start];
        order = top_elem - pivot;
    } while (order > 0);

    a[i] = a[high_start];
    a[high_start] = element;

    console.log(a)

    if (order < 0) {
        element = a[i];
        a[i] = a[low_end];
        a[low_end] = element;
        low_end++;
    }
    console.log(a)
}

}

console.log('最后的结果为', a) console.log(low_end) console.log(high_start) ``` 6.此时数组为 [0, 5, 8, 7, 6, 9, 4, 3, 2, 1, 10],循环从第三个元素开始,a[i] 的值为 8,因为大于基准值 5,即 order > 0,开始执行 do while 循环,do while 循环的目的在于倒序查找元素,找到第一个小于基准值的元素,然后让这个元素跟 a[i] 的位置交换。 第一个小于基准值的元素为 1,然后 1 与 8 交换,数组变成 [0, 5, 1, 7, 6, 9, 4, 3, 2, 8, 10]。high_start 的值是为了记录倒序查找到哪里了。

7.此时 a[i] 的值变成了 1,然后让 1 跟 基准值 5 交换,数组变成了 [0, 1, 5, 7, 6, 9, 4, 3, 2, 8, 10],low_end 的值加 1,low_end 的值是为了记录基准值的所在位置。

8.循环接着执行,遍历第四个元素 7,跟第 6、7 的步骤一致,数组先变成 [0, 1, 5, 2, 6, 9, 4, 3, 7, 8, 10],再变成 [0, 1, 2, 5, 6, 9, 4, 3, 7, 8, 10]

9.遍历第五个元素 6,跟第 6、7 的步骤一致,数组先变成 [0, 1, 2, 5, 3, 9, 4, 6, 7, 8, 10],再变成 [0, 1, 2, 3, 5, 9, 4, 6, 7, 8, 10]

10.遍历第六个元素 9,跟第 6、7 的步骤一致,数组先变成 [0, 1, 2, 3, 5, 4, 9, 6, 7, 8, 10],再变成 [0, 1, 2, 3, 4, 5, 9, 6, 7, 8, 10]

11.在下一次遍历中,因为 i == high_start,意味着正序和倒序的查找终于找到一起了,后面的元素肯定都是大于基准值的,此时退出循环

12.遍历后的结果为 [0, 1, 2, 3, 4, 5, 9, 6, 7, 8, 10],在基准值 5 前面的元素都小于 5,后面的元素都大于 5,然后我们分别对两个子集进行 QuickSort

13.此时 low_end 值为 5,high_start 值为 6,to 的值依然是 10,from 的值依然是 0,to - high_start < low_end - from 的结果为 true,我们对 QuickSort(a, 6, 10),即对后面的元素进行排序,但是注意,在新的 QuickSort 中,因为 to - from 的值小于 10,所以这一次其实是采用了插入排序。所以准确的说,当数组长度大于 10 的时候,v8 采用了快速排序和插入排序的混合排序方法。

14.然后 to = low_end 即设置 to 为 5,因为 while(true) 的原因,会再执行一遍,to - from 的值为 5,执行 InsertionSort(a, 0, 5),即对基准值前面的元素执行一次插入排序。

15.因为在 to - from <= 10 的判断中,有 return 语句,所以 while 循环结束。

16.v8 在对数组进行了一次快速排序后,然后对两个子集分别进行了插入排序,最终修改数组为正确排序后的数组。

比较

最后来张示意图感受下插入排序和快速排序:

极客教程网
——一个你值得来的网站
编程笔记:学习分享,与君共勉!
电子书:系统完整的学习!
轮子库:介绍各种库、插件的用途
在线工具:极客工具,在线工具,在线运行
前端导航:前端导航,前端资源聚合平台
微信公众号
极客教程(geekjc)
QQ群:
495489065

Copyright © 2018 - ~ All Rights Reserved. Made By ll 备案号:粤ICP备15001588号-4