算法

排序算法05：归并排序

算法介绍

  归并排序的算法逻辑为把两个有序的数组归并为一个有序的数组。

举个例子，对于一个长度为8的数组，有两种归并方式

自顶向下的归并:

  1. 先分为[0-3],[4-7],左右有序后再归并到一起就变成一个完整的有序数组了
  2. 让[0-3]有序又可以分为[0-1]、[2-3]有序，递归下去，最终归并为[0-3]有序

自底向上的归并：

  1. 先让[0-1],[2-3],[4-5],[6-7]有序
  2. 再让[0-3],[4-7]有序
  3. 最终归并[0-7],让整个数组有序

归并实现

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
/**
 * 原地归并
 * @param arr
 * @param start
 * @param mid
 * @param end
 */
function merge(arr,start,mid,end) {
    var i=start,j=mid+1;
    var temp = [];
    //数据复制一份将a[start..end]复制到temp[start..end],start不一定为0
    for(var m=start;m<=end;m++){
        temp[m] = arr[m];
    }

    for(var n=start;n<=end;n++){
        if(i>mid){
            //左边用尽（取右半边的元素）
            arr[n] = temp[j++];
        }else if(j>end){
            //右边用尽（取左半边的元素）
            arr[n] = temp[i++];
        }else if(temp[j]<temp[i]){
            //右半边的元素小于左半边的元素（取右半边的元素）
            arr[n] = temp[j++];
        }else{
            //右半边的元素大于左半边的元素（取左半边的元素）
            arr[n] = temp[i++];
        }
    }
}

下面这张原地归并轨迹的样例图来自于《算法》第四版，左侧为arr，右侧为temp数组

自顶向下的归并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 自顶向下的归并
 * @param arr
 * @param start
 * @param end
 */
function sortDown(arr,start,end) {
    //将数组arr[start..end]排序，这里的start并不一定是0
    if(end<=start) return;
    var mid = start + parseInt((end-start)/2);
    sortDown(arr,start,mid);        //- 将左半边排序
    sortDown(arr,mid+1,end);        //- 将右半边排序
    merge(arr,start,mid,end);       //- 归并结果
}

自底向上的归并

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 自底向上的归并
 * @param arr
 */
function sortUp(arr) {
    var len = arr.length;
    for(var sz=1;sz<len;sz=2*sz){
        for(var start=0;start<len-sz;start=start+2*sz){
            merge(arr,start,start+sz-1,Math.min(start+2*sz-1,len-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
/**
 * Created by YiYing on 2017/4/29.
 */

/**
 * 原地归并
 * @param arr
 * @param start
 * @param mid
 * @param end
 */
function merge(arr,start,mid,end) {
    var i=start,j=mid+1;
    var temp = [];
    //数据复制一份将a[start..end]复制到temp[start..end],start不一定为0
    for(var m=start;m<=end;m++){
        temp[m] = arr[m];
    }

    for(var n=start;n<=end;n++){
        if(i>mid){
            //左边用尽（取右半边的元素）
            arr[n] = temp[j++];
        }else if(j>end){
            //右边用尽（取左半边的元素）
            arr[n] = temp[i++];
        }else if(temp[j]<temp[i]){
            //右半边的元素小于左半边的元素（取右半边的元素）
            arr[n] = temp[j++];
        }else{
            //右半边的元素大于左半边的元素（取左半边的元素）
            arr[n] = temp[i++];
        }
    }
}

/**
 * 自顶向下的归并
 * @param arr
 * @param start
 * @param end
 */
function sortDown(arr,start,end) {
    //将数组arr[start..end]排序，这里的start并不一定是0
    if(end<=start) return;
    var mid = start + parseInt((end-start)/2);
    sortDown(arr,start,mid);        //- 将左半边排序
    sortDown(arr,mid+1,end);        //- 将右半边排序
    merge(arr,start,mid,end);       //- 归并结果
}

/**
 * 自底向上的归并
 * @param arr
 */
function sortUp(arr) {
    var len = arr.length;
    for(var sz=1;sz<len;sz=2*sz){
        for(var start=0;start<len-sz;start=start+2*sz){
            merge(arr,start,start+sz-1,Math.min(start+2*sz-1,len-1));
        }
    }
}

//测试代码
(function () {
    var arr1 = [4,5,6,0,3,5,21,7,9,0,1];
    console.log(arr1);
    sortDown(arr1,0,arr1.length-1);
    console.log(arr1);
    console.log("----------------");
    var arr2 = [4,5,6,0,3,5,21,7,9,0,1];
    console.log(arr2);
    sortUp(arr2);
    console.log(arr2);
})();

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
65
66
67
68
package com.algs;

public class Merge {

	private static void merge(int[] arr,int[] temp,int start,int mid,int end){
		int i=start,j=mid+1;
		//避免每次都创建数组对象
		//int[] temp = new int[arr.length];
		//数据复制一份将a[start..end]复制到temp[start..end],start不一定为0
		for(int m=start;m<=end;m++){
			temp[m] = arr[m];
		}
		for(int n=start;n<=end;n++){
	        if(i>mid){
	            //左边用尽（取右半边的元素）
	            arr[n] = temp[j++];
	        }else if(j>end){
	            //右边用尽（取左半边的元素）
	            arr[n] = temp[i++];
	        }else if(temp[j]<temp[i]){
	            //右半边的元素小于左半边的元素（取右半边的元素）
	            arr[n] = temp[j++];
	        }else{
	            //右半边的元素大于左半边的元素（取左半边的元素）
	            arr[n] = temp[i++];
	        }
	    }
	}

	private static void sortDown(int[] arr,int[] temp,int start,int end){
		//将数组arr[start..end]排序，这里的start并不一定是0
	    if(end<=start) return;
	    int mid = start + (end-start)/2;
	    sortDown(arr,temp,start,mid);        //- 将左半边排序
	    sortDown(arr,temp,mid+1,end);        //- 将右半边排序
	    merge(arr,temp,start,mid,end);       //- 归并结果
	}

	private static void sortUp(int[] arr,int[] temp){
		int len = arr.length;
	    for(int sz=1;sz<len;sz=2*sz){
	        for(int start=0;start<len-sz;start=start+2*sz){
	            merge(arr,temp,start,start+sz-1,Math.min(start+2*sz-1,len-1));
	        }
	    }
	}

	public static void main(String[] args) {
		int[] arr1  = {4,5,6,0,3,5,21,7,9,0,1};
		int[] temp1 = new int[arr1.length];
	    sortDown(arr1,temp1,0,arr1.length-1);
	    for(int m:arr1){
	    	System.out.print(m+" ");
	    }

	    System.out.println();
	    System.out.println("----------------");

	    int[] arr2  = {4,5,6,0,3,5,21,7,9,0,1};
	    int[] temp2 = new int[arr2.length];
	    sortUp(arr2,temp2);
	    for(int n:arr2){
	    	System.out.print(n+" ");
	    }
	}

}

总结

  1. 稳定。
  2. 非原地排序。
  3. 时间复杂度为NlogN
  4. 空间复杂度为N
  5. 归并排序的主要缺点是辅助数组所使用的额外空间和N的大小成正比
  6. 归并排序的递归使小规模问题中方法的调用过于频繁。使用插入排序处理小规模的子数组（比如长度小于15）一般可以将归并排序的运行时间缩短10%-15%
  7. 当数组长度为2的幂时，自顶向下和自底向上的归并排序所用的比较次数和数组的访问次数正好相同，只是顺序不同。其它时候，两种方法的比较和数组的访问次序会有所不同

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

上一篇：排序算法04：希尔排序
下一篇：排序算法06：快速排序

留言

欢迎交流想法。留言会通过 GitHub Issues 保存，首次使用需要登录 GitHub。

算法

排序算法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：归并排序

留言

欢迎交流想法。留言会通过 GitHub Issues 保存，首次使用需要登录 GitHub。

算法

排序算法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：希尔排序

留言

欢迎交流想法。留言会通过 GitHub Issues 保存，首次使用需要登录 GitHub。

算法

排序算法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：插入排序

留言

欢迎交流想法。留言会通过 GitHub Issues 保存，首次使用需要登录 GitHub。

算法

排序算法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：选择排序

留言

欢迎交流想法。留言会通过 GitHub Issues 保存，首次使用需要登录 GitHub。

Programmer

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

问题

  在码代码的过程中，经常会遇到在循环中移除指定元素的需求。按照常规的思路，直接一个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为数组下标，个人觉得这是最简洁、高效的代码实现了。

作者公众号：

留言

欢迎交流想法。留言会通过 GitHub Issues 保存，首次使用需要登录 GitHub。

其它

自营电商平台业务梳理

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

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

留言

欢迎交流想法。留言会通过 GitHub Issues 保存，首次使用需要登录 GitHub。

其它

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，则证明配置成功。

留言

欢迎交流想法。留言会通过 GitHub Issues 保存，首次使用需要登录 GitHub。

算法

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）的测试结果如图：

留言

欢迎交流想法。留言会通过 GitHub Issues 保存，首次使用需要登录 GitHub。

算法

算法的时间复杂度

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

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

留言

欢迎交流想法。留言会通过 GitHub Issues 保存，首次使用需要登录 GitHub。