排序算法04：希尔排序

算法介绍

  从上一篇《插入排序》可以知道，当最小元素恰好在最后一个时，需要移动的次数为N-1。当一个从大到小排列的数组使用插入排序变成从小到大排列时，需要比乱序状态下耗费更多的时间。原因为插入排序是从后往前一位一位的往前交换，如果能把靠后的较小元素只交换（移动）一次就插入到靠前位置，则能有效的缩短排序时间。希尔排序就是这样一种算法。

  希尔排序通过一个序列让靠后的元素一次性移动到前面，最后使用插入排序让数组变成有序状态。

  举个例子。长度为100的数组，挑选出[1,10,20,50]这么一个序列，这个数列的含义就是每次元素移动的间隔。

  1. 让间隔50的数据相对有序（arr[0]<arr[49]<arr[99]）
  2. 让间隔20的数据相对有序（arr[0]<arr[19]<arr[39]<arr[59]<arr[79]<arr[99]）
  3. 让间隔10的数据相对有序（arr[0]<arr[9]<arr[19]<arr[29]<arr[39]……）
  4. 让间隔1的数据现对有序(步长为1实际上就是插入排序)

下图为《算法》第四版上希尔排序排序轨迹样例：

这张图是对SHELLSORTEXAMPLE字符序列排序，序列为13、4、1。

可视化效果：这里

Javascript实现

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

/**
 * Created by YiYing on 2017/4/22.
 */
(function (W) {

    function Shell(arr) {
        this.arr = arr;
    }

    /**
     * 冒泡排序算法实现
     */
    Shell.prototype.sort = function () {
        var len = this.arr.length;
        var h   = 1;
        //自动生成序列。步长序列为1、4、13、40、121、364、1093......
        while(h<parseInt(len/3)){
            h = h*3+1;
        }
        while(h>=1){
            for(var i=h;i<len;i++){
                //当h>1时，实际上是把后面的一次性移动到前面。最后h为1时实际上就是对arr进行插入排序
                for(var j=i;j>=h && this.less(j,j-h);j=j-h){
                    this.exchange(j,j-h);
                }
            }
            //每执行一次，步长依次递减，最终步长递减为1。
            h = parseInt(h/3);
        }
    };

    /**
     * 判断m是否小于n
     * @param m
     * @param n
     */
    Shell.prototype.less = function (m,n) {
        //可根据不同的数据类型设置比对规则，比如json。这里适用于数字与字符串。
        return this.arr[m]<this.arr[n];
    };

    /**
     * 交换数组中m与n的位置
     * @param m
     * @param n
     */
    Shell.prototype.exchange = function (m,n) {
        var swap    = this.arr[m];
        this.arr[m] = this.arr[n];
        this.arr[n] = swap;
    };

    /**
     * 打印排序后的数组
     */
    Shell.prototype.show = function () {
        console.log(this.arr);
    };

    /**
     * 判断是否已排序
     * @returns {boolean}
     */
    Shell.prototype.isSorted = function () {
        var len = this.arr.length;
        for(var i=1;i<len;i++){
            if(this.less(i,i-1)){
                return false;
            }
        }
        return true;
    };

    W.Shell = Shell;
})(window);

//测试代码
(function () {
    var arr = [4,5,6,0,3,5,21,7,9,0,1];
    var shell = new Shell(arr);
    console.log("排序前："+shell.isSorted());
    shell.sort();
    console.log("排序后："+shell.isSorted());
    shell.show();
})();

Java实现

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

package com.algs;

public class Shell {

	/**
	 * 希尔排序实现逻辑
	 * @param arr
	 */
	public static void sort(int[] arr){
		int len = arr.length;
		int h	= 1;
		//自动生成序列。步长序列为1、4、13、40、121、364、1093......
		while(h<len/3){
			h = 3*h+1;
		}
        while(h>=1){
        	for(int i=h;i<len;i++){
        		//当h>1时，实际上是把后面的一次性移动到前面。最后h为1时实际上就是对arr进行插入排序
        		for(int j=i;j>=h && less(arr[j],arr[j-h]);j -= h){
        			exchange(arr,j,j-h);
        		}
        	}
        	//每执行一次，步长依次递减，最终步长递减为1。
        	h = h/3;
        }
	}

	/**
	 * 比较m是否小于n
	 * @param m
	 * @param n
	 * @return
	 */
	private static boolean less(int m,int n) {
        return m < n;
    }

	/**
	 * 交换m与n的位置
	 * @param a
	 * @param m
	 * @param n
	 */
	private static void exchange(int[] a, int m, int n) {
        int swap = a[m];
        a[m] = a[n];
        a[n] = swap;
    }

	public static void show(int[] a){
		for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
	}

	public static void main(String[] args) {
		int[] arr = {4,5,6,0,3,5,21,7,9,0,1};
		Shell.sort(arr);
		Shell.show(arr);
	}
}


总结

  1. 不稳定。
  2. 原地排序。
  3. 时间复杂度为：目前无法准确评估时间复杂度。但是肯定小于平方级别，大于线性对数级别。详细可见《算法》第四版P162
  4. 空间复杂度为：常数级别。
  5. 希尔排序比插入排序、选择排序更快。且数组越大，优势越大。
  6. 对于递增序列可以随意选择，目前无法证明某个序列是最优的。

GitHub：https://github.com/AlbertKnag/algs-practice

上一篇：排序算法03：插入排序
下一篇：排序算法05：归并排序

展开全文 >>

排序算法03：插入排序

算法介绍

步骤：

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果被扫描的元素（已排序）大于新元素，将该元素后移一位
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

排序演示：

可视化效果：这里

Javascript实现

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

/**
 * Created by YiYing on 2017/4/22.
 */
(function (W) {

    function Insertion(arr) {
        this.arr = arr;
    }

    /**
     * 插入排序算法实现
     */
    Insertion.prototype.sort = function () {
        var len = this.arr.length;
        for(var i=1;i<len;i++){
            //在已经有序之中，从后往前比对，依次交换，直到插入到正确的位置即可
            for(var j=i;j>0&&this.less(j,j-1);j--){
                this.exchange(j,j-1);
            }
        }
    };

    /**
     * 判断m是否小于n
     * @param m
     * @param n
     */
    Insertion.prototype.less = function (m,n) {
        //可根据不同的数据类型设置比对规则，比如json。这里适用于数字与字符串。
        return this.arr[m]<this.arr[n];
    };

    /**
     * 交换数组中m与n的位置
     * @param m
     * @param n
     */
    Insertion.prototype.exchange = function (m,n) {
        var swap    = this.arr[m];
        this.arr[m] = this.arr[n];
        this.arr[n] = swap;
    };

    /**
     * 打印排序后的数组
     */
    Insertion.prototype.show = function () {
        console.log(this.arr);
    };

    /**
     * 判断是否已排序
     * @returns {boolean}
     */
    Insertion.prototype.isSorted = function () {
        var len = this.arr.length;
        for(var i=1;i<len;i++){
            if(this.less(i,i-1)){
                return false;
            }
        }
        return true;
    };

    W.Insertion = Insertion;
})(window);

//测试代码
(function () {
    var arr = [4,5,6,0,3,5,21,7,9,0,1];
    var insertion = new Insertion(arr);
    console.log("排序前："+insertion.isSorted());
    insertion.sort();
    console.log("排序后："+insertion.isSorted());
    insertion.show();
})();

Java实现

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package com.algs;

public class Insertion {

	/**
	 * 插入排序实现逻辑
	 * @param arr
	 */
	public static void sort(int[] arr){
		int len = arr.length;
        for (int i = 1; i < len; i++) {
        	//在已经有序之中，从后往前比对，依次交换，直到插入到正确的位置即可
            for (int j = i; j>0&&less(arr[j], arr[j-1]); j--) {
                exchange(arr, j, j-1);
            }
        }
	}

	/**
	 * 比较m是否小于n
	 * @param m
	 * @param n
	 * @return
	 */
	private static boolean less(int m,int n) {
        return m < n;
    }

	/**
	 * 交换m与n的位置
	 * @param a
	 * @param m
	 * @param n
	 */
	private static void exchange(int[] a, int m, int n) {
        int swap = a[m];
        a[m] = a[n];
        a[n] = swap;
    }

	public static void show(int[] a){
		for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
	}

	public static void main(String[] args) {
		int[] arr = {4,5,6,0,3,5,21,7,9,0,1};
		Insertion.sort(arr);
		Insertion.show(arr);
	}
}

总结

  1. 实验证明（《算法》第四版P160），插入排序比选择排序更快。
  2. 稳定。相同元素排序后能保持排序前的相对顺序。
  3. 原地排序。
  4. 时间复杂度为：介于线性级别与平方级别之间。取决于输入元素的排列情况。
  5. 空间复杂度为：常数级别。

GitHub：https://github.com/AlbertKnag/algs-practice

上一篇：排序算法02：选择排序
下一篇：排序算法04：希尔排序

展开全文 >>

排序算法02：选择排序

算法介绍

  首先，从[0,len]中找到数组中最小的元素，让它与第一个元素交换。接着从[1,len]中找出最小的元素，让它与第二个元素交换。循环往复，最终使得数组从小到大排序。

可视化效果：这里

Javascript实现

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/**
 * Created by YiYing on 2017/4/22.
 */
(function (W) {

    function Selection(arr) {
        this.arr = arr;
    }

    /**
     * 选择排序算法实现
     */
    Selection.prototype.sort = function () {
        var len = this.arr.length;
        for(var i=0;i<len;i++){
            var min = i;
            //找出最小元素
            for(var j=i+1;j<len;j++){
                if(this.less(j,min)){
                    min = j;
                }
            }
            //把最小元素放到最前面
            this.exchange(i,min);
        }
    };

    /**
     * 判断m是否小于n
     * @param m
     * @param n
     */
    Selection.prototype.less = function (m,n) {
        //可根据不同的数据类型设置比对规则，比如json。这里适用于数字与字符串。
        return this.arr[m]<this.arr[n];
    };

    /**
     * 交换数组中m与n的位置
     * @param m
     * @param n
     */
    Selection.prototype.exchange = function (m,n) {
        var swap    = this.arr[m];
        this.arr[m] = this.arr[n];
        this.arr[n] = swap;
    };

    /**
     * 打印排序后的数组
     */
    Selection.prototype.show = function () {
        console.log(this.arr);
    };

    /**
     * 判断是否已排序
     * @returns {boolean}
     */
    Selection.prototype.isSorted = function () {
        var len = this.arr.length;
        for(var i=1;i<len;i++){
            if(this.less(i,i-1)){
                return false;
            }
        }
        return true;
    };

    W.Selection = Selection;
})(window);

//测试代码
(function () {
    var arr = [4,5,6,0,3,5,21,7,9,0,1];
    var selection = new Selection(arr);
    console.log("排序前："+selection.isSorted());
    selection.sort();
    console.log("排序后："+selection.isSorted());
    selection.show();
})();

Java实现

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package com.algs;

public class Selection {

  /**
   * 插入排序实现逻辑
   * @param arr
   */
  public static void sort(int[] arr){
    int len = arr.length;
        for (int i = 0; i < len; i++) {
            int min = i;
            for (int j = i+1; j < len; j++) {
                if (less(arr[j], arr[min])) min = j;
            }
            exchange(arr, i, min);
        }
  }

  /**
   * 比较m是否小于n
   * @param m
   * @param n
   * @return
   */
  private static boolean less(int m,int n) {
        return m < n;
    }

  /**
   * 交换m与n的位置
   * @param a
   * @param m
   * @param n
   */
  private static void exchange(int[] a, int m, int n) {
        int swap = a[m];
        a[m] = a[n];
        a[n] = swap;
    }

  public static void show(int[] a){
    for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
  }

  public static void main(String[] args) {
    int[] arr = {4,5,6,0,3,5,21,7,9,0,1};
    Selection.sort(arr);
    Selection.show(arr);
  }
}

总结

  • 运行时间和输入无关。

    为了找出最小元素而扫描一遍数组并不能为下一遍扫描提供信息。长度一致，一个有序的数组或值全部相当的数组和一个无序的数组排序所需的时间一致。

  • 数据移动是最少的。

    一个长度为N的数组只需要N次交换即可完成排序。

  • 不稳定。

    无法保证排序前与排序后重复元素的相对顺序一致。举例：序列[5,8,5,2,9]，第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

  • 原地排序。

  • 时间复杂度为：平方级别。

  • 空间复杂度为：常数级别。

GitHub：https://github.com/AlbertKnag/algs-practice

上一篇：排序算法01：冒泡排序
下一篇：排序算法03：插入排序

展开全文 >>

排序算法01：冒泡排序

算法介绍

步骤：

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对第0个到第n-1个数据做同样的工作。这时，最大的数就“浮”到了数组最后的位置上。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

可视化效果：这里

Javascript实现

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

/**
 * Created by YiYing on 2017/4/22.
 */
(function (W) {

    function Bubble(arr) {
        this.arr = arr;
    }

    /**
     * 冒泡排序算法实现
     */
    Bubble.prototype.sort = function () {
        var len = this.arr.length;
        for(var i=0;i<len;i++){
            //将最大的元素不断的沉到底部
            for(var j=0;j<len-i-1;j++){
                if(this.less(j+1,j)){
                    this.exchange(j+1,j);
                }
            }
        }
    };

    /**
     * 判断m是否小于n
     * @param m
     * @param n
     */
    Bubble.prototype.less = function (m,n) {
        //可根据不同的数据类型设置比对规则，比如json。这里适用于数字与字符串。
        return this.arr[m]<this.arr[n];
    };

    /**
     * 交换数组中m与n的位置
     * @param m
     * @param n
     */
    Bubble.prototype.exchange = function (m,n) {
        var swap    = this.arr[m];
        this.arr[m] = this.arr[n];
        this.arr[n] = swap;
    };

    /**
     * 打印排序后的数组
     */
    Bubble.prototype.show = function () {
        console.log(this.arr);
    };

    /**
     * 判断是否已排序
     * @returns {boolean}
     */
    Bubble.prototype.isSorted = function () {
        var len = this.arr.length;
        for(var i=1;i<len;i++){
            if(this.less(i,i-1)){
                return false;
            }
        }
        return true;
    };

    W.Bubble = Bubble;
})(window);

//测试代码
(function () {
    var arr = [4,5,6,0,3,5,21,7,9,0,1];
    var bubble = new Bubble(arr);
    console.log("排序前："+bubble.isSorted());
    bubble.sort();
    console.log("排序后："+bubble.isSorted());
    bubble.show();
})();

总结

  1. 稳定。相同元素排序后能保持排序前的相对顺序。
  2. 原地排序。
  3. 时间复杂度为：平方级别。
  4. 空间复杂度为：常数级别。

GitHub：https://github.com/AlbertKnag/algs-practice

下一篇：排序算法02：选择排序

展开全文 >>

循环删除数组元素的几种姿势

问题

  在码代码的过程中，经常会遇到在循环中移除指定元素的需求。按照常规的思路，直接一个for循环，然后在循环里面来个if判断，在判断中删除掉指定元素即可。但是实际情况往往不会像预想的那样顺利运行。下面以一段Javascript代码为例演示这一过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
(function () {
    var arr = [1,2,2,3,4,5];
    var len = arr.length;
    for(var i=0;i<len;i++){
        //打印数组中的情况，便于跟踪数组中数据的变化
        console.log(i+"="+arr[i]);
        //删除掉所有为2的元素
        if(arr[i]==2){
            arr.splice(i,1);
        }
    }
    console.log(arr);
})();

运行结果如下：

  从最终的结果可以看到实际上只删除掉了匹配的其中一个元素，而另外一个元素还存在。

  从打印出的运行过程不难发现，原因为当删除掉了一个元素后，数组的索引发生的变化，造成了程序的异常。

解决

找到了问题的原因，就不难解决问题了。

姿势一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(function () {
    var arr = [1,2,2,3,4,5];
    var len = arr.length;
    for(var i=0;i<len;i++){
        //打印数组中的情况，便于跟踪数组中数据的变化
        console.log(i+"="+arr[i]);
        //删除掉所有为2的元素
        if(arr[i]==2){
            //注意对比这行代码：删除元素后调整i的值
            arr.splice(i--,1);
        }
    }
    console.log(arr);
})();

上面的代码看起来不大好理解，有没有看起来更易于理解的代码呢？请看下面

姿势二

1
2
3
4
5
6
7
8
9
10
11
12
(function () {
    var arr = [1,2,2,3,4,5];
    var len = arr.length-1;
    //start from the top
    for(var i=len;i>=0;i--){
        console.log(i+"="+arr[i]);
        if(arr[i]==2){
            arr.splice(i,1);
        }
    }
    console.log(arr);
})();

从后往前遍历可以有效解决问题，也容易理解，那么还有没有跟简洁的实现呢？接着看下面代码

姿势三

1
2
3
4
5
6
7
8
9
10
11
(function () {
    var arr = [1,2,2,3,4,5];
    var i = arr.length;
    while(i--){
        console.log(i+"="+arr[i]);
        if(arr[i]==2){
            arr.splice(i,1);
        }
    }
    console.log(arr);
})();

使用while(i--),i为数组下标，个人觉得这是最简洁、高效的代码实现了。

作者公众号：

展开全文 >>

自营电商平台业务梳理

  目前的电商越来越深入人心，一些有自家产品的企业也跃跃欲试，希望能建立自己的网上销售平台，不再满足于借助第三方系统，比如天猫旗舰店等。希望 “All Control”。

  针对这样的需求，对自营电商平台的业务做了一个简单的梳理，整理出如下这张图。

展开全文 >>

nginx+tomcat+memcached配置session共享

背景

  两台tomcat，通过nginx来实现负载均衡，使用memcached来解决session共享问题。

tomcat配置

分别拷贝jar包到tomcatA、tomcatB的lib目录下

包含如下这些jar包，从这里下载

1
2
3
4
5
6
7
8
9
asm-3.2.jar
kryo-1.04.jar
kryo-serializers-0.11.jar
memcached-session-manager-1.7.0.jar
memcached-session-manager-tc7-1.8.1.jar
minlog-1.2.jar
msm-kryo-serializer-1.7.0.jar
reflectasm-1.01.jar
spymemcached-2.7.3.jar

配置context.xml

1
2
3
4
5
6
7
8
9
10
<Manager className="de.javakaffee.web.msm.MemcachedBackupSessionManager"
	   memcachedNodes="n1:127.0.0.1:11211"
	lockingMode="auto"
	sticky="false"
	requestUriIgnorePattern= ".*\.(png|gif|jpg|css|js)$"
	sessionBackupAsync= "false"
	sessionBackupTimeout= "100"
	copyCollectionsForSerialization="true"
	transcoderFactoryClass="de.javakaffee.web.msm.serializer.kryo.KryoTranscoderFactory"
		/>

nginx配置

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
user  nobody;  
worker_processes  4;  
error_log  logs/error.log;  
events {  
    worker_connections  1024;  
}  

http {  
    include       mime.types;  
    default_type  application/octet-stream;  
    sendfile        on;  
    keepalive_timeout  65;  
    gzip  on;  
    upstream  myserver   {  
              server   127.0.0.1:8080;  
              server   127.0.0.1:8081;  
    }  
    server {  
        listen       80;  
        server_name  127.0.0.2;  
        charset utf-8;  
        location / {  
            root   html;  
            index  index.html index.htm;  
            proxy_pass        http://myserver;  
            proxy_set_header  X-Real-IP  $remote_addr;  
            client_max_body_size  100m;  
        }  


        location ~ ^/(WEB-INF)/ {
            deny all;
        }


        error_page   500 502 503 504  /50x.html;  
        location = /50x.html {  
            root   html;  
        }  


    }  
}

说明：

  1. tomcatA的地址为127.0.0.1:8080
  2. tomcatB的地址为127.0.0.1:8081
  3. 通过在浏览器上输入127.0.0.2，请求会动态分配到A和B上

验证Session共享是否配置成功

1.在tomcatA的webapp下新增test.jsp页面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<%@ page language="java" contentType="text/html; charset=ISO-8859-1"
	pageEncoding="ISO-8859-1"%>
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<title>tomcatA</title>
</head>
<body>
	SessionID:<%=session.getId()%>
	<%
		out.println("tomcatA");
	%>
</body>
</html>

2.在tomcatB的webapp下新增test.jsp页面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<%@ page language="java" contentType="text/html; charset=ISO-8859-1"
  pageEncoding="ISO-8859-1"%>
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<title>tomcatB</title>
</head>
<body>
  SessionID:<%=session.getId()%>
  <%
    out.println("tomcatB");
  %>
</body>
</html>

  浏览器请求127.0.0.2/projectName/test.jsp，多刷新几下，如果seseionID一直不变，而不断切换A和B，则证明配置成功。

展开全文 >>

JavaScript数组倒序算法与性能对比

  最近正在撸算法第四版，关于JS中数组的倒序，想到如下几种实现方式。

for push

1
2
3
4
5
6
7
(function (arr) {
    var result = [],len=arr.length-1;
    for(var right=len;right>=0;right--){
        result.push(arr[right])
    }
    console.log(result.join(""));
})("字符倒序测试.".split(""));

for swap half

1
2
3
4
5
6
7
8
9
10
11
12
13
(function (array) {
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0; left < length / 2; left += 1)
    {
        right = length - 1 - left;
        var temporary = array[left];
        array[left] = array[right];
        array[right] = temporary;
    }
    console.log(array.join(""));
})("字符倒序测试.".split(""));

native reverse

1
2
3
4
(function (arr) {
    var result = arr.reverse();
    console.log(result.join(""));
})("字符倒序测试.".split(""));

性能对比

  本来想再写一个性能测试的样例，在写之前感觉应该已经有人做过这件事了，所以Google了一下，找到Stackoverflow上这篇答案，循着找到一个很全面的性能测试样例，点击这里。点击Run tests即能在对应的测试环境下测试各种算法的性能情况。

在我本地环境（Testing in Chrome 56.0.2924 / Windows 10 0.0.0）的测试结果如图：

展开全文 >>

算法的时间复杂度

  关于算法的时间复杂度经常会看到比如logN,NlogN等。之前一直觉得搞不清楚，来一个问题不知道怎么得出该算法的时间复杂度。最近在撸《算法》第四版,是时候祭出下面这张图了。

  时间复杂度这个东西，其实更准确点说应该是描述一个算法在问题规模不断增大时对应的时间增长曲线。所以，这些增长数量级并不是一个准确的性能评价，可以理解为一个近似值，时间的增长近似于logN、NlogN的曲线。

展开全文 >>

JavaScript实现二分查找

  最近撸《算法》第四版，开篇就是一个Java版本的二分查找算法，下面以JS实现一下。

  二分查找的前提为：数组、有序。逻辑为：优先和数组的中间元素比较，如果等于中间元素，则直接返回。如果不等于则取半继续查找。

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * 二分查找，递归实现。
 * @param target
 * @param arr
 * @param start
 * @param end
 * @returns {*}
 */
function binarySearch(target,arr,start,end) {
    if( start > end){return -1}
    var start   = start || 0;
    var end     = end || arr.length-1;

    var mid = parseInt(start+(end-start)/2);
    if(target==arr[mid]){
        return mid;
    }else if(target>arr[mid]){
        return binarySearch(target,arr,mid+1,end);
    }else{
        return binarySearch(target,arr,start,mid-1);
    }
    return -1;
}


/**
 * 有序的二分查找，返回-1或存在的数组下标。不使用递归实现。
 * @param target
 * @param arr
 * @returns {*}
 */
function binarySearch(target,arr) {
    var start   = 0;
    var end     = arr.length-1;

    while (start<=end){
        var mid = parseInt(start+(end-start)/2);
        if(target==arr[mid]){
            return mid;
        }else if(target>arr[mid]){
            start   = mid+1;
        }else{
            end     = mid-1;
        }
    }
    return -1;
}

  写完有序，自然而然的想到了无序的情况如何使用二分查找呢？马上想到先使用快排分组，分好组再二分。代码如下：

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
27
28
29
30
31
/**
 * 无序的二分查找。返回true/false
 * @param target
 * @param arr
 * @returns {boolean}
 */
function binarySearch(target,arr) {
    while (arr.length>0){
        //使用快速排序。以mid为中心划分大小，左边小，右边大。
        var left    = [];
        var right   = [];
        //选择第一个元素作为基准元素(基准元素可以为任意一个元素)
        var pivot   = arr[0];
        //由于取了第一个元素，所以从第二个元素开始循环
        for(var i=1;i<arr.length;i++){
            var item = arr[i];
            //大于基准的放右边，小于基准的放左边
            item>pivot ? right.push(item) : left.push(item);
        }

        //得到经过排序的新数组
        if(target==pivot){
            return true;
        }else if(target>pivot){
            arr     = right;
        }else{
            arr     = left;
        }
    }
    return false;
}

  写完用快速排序实现的无序二分查找，仔细想了一下该算法的时间复杂度，发现还不如直接一个for循环来得快……囧

  睡完一觉起来感觉也不是一无是处，这是一个用时间换空间的好办法，大规模问题下有助于节省内存开销。

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家