算法

基础数据结构04：背包

介绍

  背包是一种不支持从中删除元素的集合数据类型。它存在的目的就是帮助收集元素并迭代遍历收集到的元素。迭代的顺序不确定且与用例无关。

API

Java实现

  背包可以使用数组，也可以使用链表来实现。如果使用数组，需要考虑数组的动态扩容。这里使用链表来实现，避免数组扩容的问题。另外沿用上一篇stack的实现，只需要把push方法修改为add方法即可。虽然使用链表后，元素遍历是有一定顺序的，不过没用影响，因为当使用Bag数据结构时，默认会认为遍历的数据是无序的。

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
package com.algs.base;

import java.util.Iterator;
import java.util.NoSuchElementException;


public class LinkBag<Item> implements Iterable<Item> {
	private Node first;
	private int N;			// 背包中的元素数量

	// 背包中每个元素的类型为Node
	private class Node{
		Item item;
		Node next;
	}

	public boolean isEmpty(){return N==0;}
	public int size(){return N;}

	// 添加元素(跟栈的push一样)
	public void add(Item item){
		Node oldFirst = first;
		first = new Node();
		first.item = item;
		first.next = oldFirst;
		N++;
	}

	@Override
	public Iterator<Item> iterator()  {
        return new ListIterator();  
    }
	//链表遍历实现
    private class ListIterator implements Iterator<Item> {
        private Node current = first;

        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next;
            return item;
        }
    }

    public static void main(String[] args) {
    	LinkBag<String> bag = new LinkBag<String>();
    	bag.add("one");
    	bag.add("two");
    	bag.add("three");
		for(String node:bag){
			//打印结果为：three->two->one->
			System.out.print(node+"->");
		}
	}
}

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

上一篇：基础数据结构03：栈

留言

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

算法

基础数据结构03：栈

介绍

  栈是一种后进先出的数据结构。栈类似于一截一端封口的竹筒，不断像竹筒中放入东西，然后不断从中取出东西，最后放进竹筒中的东西总是最先被取出来，最先放进竹筒里的东西由于在竹筒的最底部，总是最后被取出来。

API

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
69
70
71
72
73
74
75
76
77
78
package com.algs.base;

import java.util.Iterator;
import java.util.NoSuchElementException;


public class LinkStack<Item> implements Iterable<Item> {
	private Node first;		// 栈顶，即最近添加的元素
	private int N;			// 栈中的元素数量

	// 栈中每个元素的类型为Node
	private class Node{
		Item item;
		Node next;
	}

	public boolean isEmpty(){return N==0;}
	public int size(){return N;}

	// 入栈
	public void push(Item item){
		Node oldFirst = first;
		first = new Node();
		first.item = item;
		first.next = oldFirst;
		N++;
	}
	// 出栈
	public Item pop(){
		Item item = first.item;
		first = first.next;
		if(first==null){
			System.out.println("栈为空");
			return null;
		}
		N--;
		return item;
	}

	@Override
	public Iterator<Item> iterator()  {
        return new ListIterator();  
    }
	//链表遍历实现
    private class ListIterator implements Iterator<Item> {
        private Node current = first;

        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next;
            return item;
        }
    }

    public static void main(String[] args) {
    	LinkStack<String> stack = new LinkStack<String>();
    	stack.push("one");
    	stack.push("two");
    	stack.push("three");
		for(String node:stack){
			//打印结果为：three->two->one->
			System.out.print(node+"->");
		}
		//删除一个元素
		System.out.println("");
		//打印结果为：node:three
		System.out.println("node:"+stack.pop());
		for(String node1:stack){
			//打印结果为：two->one->
			System.out.print(node1+"->");
		}
	}
}

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

上一篇：基础数据结构02：队列
下一篇：基础数据结构04：背包

留言

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

算法

基础数据结构02：队列

介绍

  队列是一种先进先出的数据结构。类似于一截水从一端流向另一端的水管，先进入水管的水最先从另一端出来。

API

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
package com.algs.base;

import java.util.Iterator;
import java.util.NoSuchElementException;


public class LinkQueue<Item> implements Iterable<Item> {

	private Node first;		// 指向最早添加的节点的链接
	private Node last;		// 指向最近添加的节点的链接
	private int N;			// 队列中的元素总数量

	// 队列中的一个元素
	private class Node{
		Item item;
		Node next;
	}

	public boolean isEmpty(){return N==0;}

	public int size(){return N;}

	// 向队列中添加一个元素
	public void enqueue(Item item){
		// 向链表的尾部添加一个元素
		Node oldLast = last;
		last = new Node();
		last.item = item;
		last.next = null;
		//只有一个节点时，首节点和尾节点相等
		if(isEmpty()) 	first = last;
		else			oldLast.next = last;
		N++;
	}

	//从队列中删除一个元素(先进先出)
	public Item dequeue(){
		if(first==null){
			System.out.println("队列中没有元素");
			return null;
		}
		// 从表头删除元素
		Item item = first.item;
		first = first.next;
		if(isEmpty())	last = null;
		N--;
		return item;
	}
	@Override
	public Iterator<Item> iterator()  {
        return new ListIterator();  
    }
	//链表遍历实现
    private class ListIterator implements Iterator<Item> {
        private Node current = first;

        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next;
            return item;
        }
    }

    public static void main(String[] args) {
    	LinkQueue<String> queue = new LinkQueue<String>();
    	queue.enqueue("One");
    	queue.enqueue("two");
    	queue.enqueue("three");
		for(String node:queue){
			//打印结果为：One->two->three->
			System.out.print(node+"->");
		}
		//删除一个元素
		System.out.println("");
		//打印结果为：node:One
		System.out.println("node:"+queue.dequeue());
		for(String node1:queue){
			//打印结果为：two->three->
			System.out.print(node1+"->");
		}
	}
}

说明

  对于队列的实现，除了可以使用链表，还可以使用数组来实现。但是在Java中的数组，初始化时必须指定数组的大小，所以当使用数组来实现队列时，需要动态调整队列的大小。
  当数组空间不够时，需要扩展空间。当队列中的元素只有空间的四分之一时，此时可以把数组的长度减半。

代码如下：

1
2
3
4
5
6
7
8
9
// 以数组来实现队列或栈时需动态调整数组的大小
private void resize(int max){
	//将队列中的元素移动到新数组中
	Item[] temp = (Item[])new Object[max];
	for(int i=0;i<N;i++){
		temp[i] = queue[i]; //queue为存放队列元素的数组
	}
	queue = temp;
}

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

上一篇：基础数据结构01：链表
下一篇：基础数据结构03：栈

留言

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

算法

基础数据结构01：链表

介绍

  链表的类似于一个连着一个的圆环。在链表中，要想访问某个节点，必须通过他的上一节点来访问。

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
69
70
71
72
73
74
75
76
77
78
79
80
81
package com.algs.base;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Link<Item> implements Iterable<Item> {
	private Node first = null;  // 链表的第一个元素
	private int n = 0;			// 链表的长度

	private class Node{
		private Item item;		// 链表节点的值
		private Node next;		// 指向下一节点

		public String toString(){
			return (String) this.item;
		}
	}

	// 向链表中添加数据
	public void add(Item item){
		Node oldFirst = first;
		first = new Node();
		first.item = item;
		first.next = oldFirst;
		n++;
	}

	// 翻转链表
	public void reverse(){
		Node next = first.next;
		first.next = null;				// 避免遍历时死循环
		while(next!=null){
			Node temp = next.next;
			next.next = first;
			first = next;
			next = temp;
		}
	}

	public int size(){
		return n;
	}

	@Override
	public Iterator<Item> iterator()  {
        return new ListIterator();  
    }
	//链表遍历实现
    private class ListIterator implements Iterator<Item> {
        private Node current = first;

        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next;
            return item;
        }
    }

	public static void main(String[] args) {
		Link<String> link = new Link<String>();
		link.add("one");
		link.add("two");
		link.add("three");
		for(String node:link){
			//打印结果为three->two->one->
			System.out.print(node+"->");
		}
		//翻转链表
		System.out.println("");
		link.reverse();
		for(String node:link){
			//打印结果为one->two->three->
			System.out.print(node+"->");
		}
	}

}

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

下一篇：基础数据结构02：队列

留言

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

Java

Eclipse下忽略掉node_modules目录相关配置

1.背景

  Eclipse项目中的静态资源采用webpack来打包，在项目中的webapp目录下会生成node_modules目录，里面包含node相关模块。由于资源文件较多，会造成Eclipse编译缓慢，另外这些文件不需要发不到运行服务器上，且不需要做版本控制。

2.相关配置

2.1 编译Eclipse项目时忽略掉node_modules目录

  选中项目右键-properties,如下图所示

2.2 SVN版本管理时忽略掉node_modules目录

  当使用Eclipse中的SVN来来就行版本控制时，选择node_modules目录后，发现添加至svn:ignore为灰色，不可用，无法忽略相关文件。可以通过如下配置来解决该问题。

2.3 项目打包发布时去掉node_modules目录

  在项目的maven pom.xml中build下的配置如下

1
2
3
4
5
6
7
8
9
10
<plugin>
	<groupId>org.apache.maven.plugins</groupId>
	<artifactId>maven-war-plugin</artifactId>
	<version>2.6</version>
	<configuration>
		<packagingExcludes>
			node_modules/**
		</packagingExcludes>
	</configuration>
</plugin>

留言

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

DBMS

MySQL两表关联的连接表该如何创建索引？

问题介绍

  创建数据库的索引，可以选择单列索引，也可以选择创建组合索引。

  遇到如下这种情况，用户表（user）与部门表（dept）通过部门用户关联表（deptuser）连接起来，如下图所示：

  问题就是，在这个关联表中该如何建立索引呢？

针对该表，有如下四种选择:

  1. 针对于user_uuid建立单列索引idx_user
  2. 针对于user_dept建立单列索引idx_dept
  3. 建立组合索引idx_user_dept,即（user_uuid,dept_uuid）
  4. 建立组合索引idx_dept_user,即（dept_uuid,user_uuid）

对关联表的查询，有如下四种情况：

1
2
3
4
5
6
7
8
9
10
11
12
-- 一、人员查所属部门用and方式
EXPLAIN SELECT d.dept_name,u.* FROM org_dept d,org_user u,org_dept_user duser WHERE u.user_uuid=duser.user_uuid AND d.dept_uuid=duser.dept_uuid  AND u.user_code="dev1";

-- 二、人员查所属部门用join方式
EXPLAIN SELECT d.dept_name,u.* FROM org_user u LEFT JOIN org_dept_user du ON u.user_uuid=du.user_uuid LEFT JOIN org_dept d ON du.dept_uuid=d.dept_uuid WHERE u.user_code="dev1";

-- 三、部门查人员用and方式
EXPLAIN SELECT d.dept_name,u.* FROM org_dept d,org_user u,org_dept_user du WHERE u.user_uuid=du.user_uuid AND d.dept_uuid=du.dept_uuid AND d.dept_code="D006";

-- 四、部门查所属人员用join方式
EXPLAIN SELECT d.dept_name,u.* FROM org_dept d LEFT JOIN org_dept_user du ON d.dept_uuid=du.dept_uuid LEFT JOIN org_user u ON u.user_uuid=du.user_uuid WHERE d.dept_code="D006";

测试验证

一.人员查所属部门用and方式

1.1 关联表无索引

1.2 单索引 Idx_dept

1.3 单索引 Idx_user

1.4 组合索引 Idx_dept_user

1.5 组合索引 Idx_user_dept

1.6 所有都建立上

二 、人员查所属部门用join方式

2.1 关联表无索引

2.2 单索引 Idx_dept

2.3 单索引 Idx_user

2.4 组合索引 Idx_dept_user

2.5 组合索引 Idx_user_dept

2.6 所有都建立上

三 、部门查人员用and方式

3.1 关联表无索引

3.2 单索引 Idx_dept

3.3 单索引 Idx_user

3.4 组合索引 Idx_dept_user

3.5 组合索引 Idx_user_dept

3.6 所有都建立上

四 、部门查所属人员用join方式

4.1 关联表无索引

4.2 单索引 Idx_dept

4.3 单索引 Idx_user

4.4 组合索引 Idx_dept_user

4.5 组合索引 Idx_user_dept

4.6 所有都建立上

结论

  通过上面的实际测试结果可以得出如下结论：针对于该关联表分别针对于user_uuid与dept_uuid建立单列索引idx_user,idx_dept最优。

  其中索引idx_user适用与通过人员ID查询出该人员所在的部门；索引idx_dept适用与通过部门查询出该部门下所属的人员。

其它

测试数据

Test.sql

相关资料

留言

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

算法

排序算法09：总结

  在这篇之前，对常见的8中排序算法进行了梳理，《算法》第四版中的这一张图对各种排序算法的性能特点做了总结。

  补充冒泡排序：稳定、原地排序、时间复杂度为n²，空间复杂度为1。

其它：

  1. 快速排序是最快的通用排序算法。
  2. 存在大量重复元素情况下，三向快速排序是不错的选择。
  3. 如果稳定性很重要而空间又不是问题，归并排序是最好的选择。
  4. 稳定性：如果一个排序算法能够保留数组中重复元素的相对位置则可以被称为是稳定的。
  5. 关于时间复杂度与空间复杂度中1、N、logN、N、NlogN、N²的含义可参见此文。

GitHub：https://github.com/AlbertKnag/algs-practice
（包含Java版与Javascript版所有排序算法样例代码）

上一篇：排序算法08：优先队列与堆排序

留言

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

算法

排序算法08：优先队列与堆排序

  堆排序一种是基于二叉堆的排序。本文将从优先队列讲起，循序渐进的实现堆排序。这也是《算法》第四版上讲解堆排序的大致章节结构。另外，本文所有的图都来自于此书。

优先队列

  普通队列是一种先进先出的数据结构，先放进队列的元素取值时优先被取出来。而优先队列是一种具有最高优先级元素先出的数据结构，比如每次取值都取最大的元素。

  优先队列有两个核心方法，一个是insert(val)向队列中添加元素，另外一个是delMax()删除最大元素（优先级最高的）并返回。可以考虑使用数组来存储优先队列的数据。

优先队列有如下三种实现方式：

  1. 有序数组(调用insert方法时使用类似插入排序把新增元素放到正确位置，调用delMax方法时直接取数组最后一个元素，因为此时元素已经是有序状态)
  2. 无序数组（调用insert方法时直接把元素放到数组中，调用dexMax方法时使用类似选择排序的方法从数组中找出最大元素，删除并返回）
  3. 堆

堆的算法

  优先队列可以使用一棵堆有序的二叉树来解决。什么叫做堆有序呢？当一棵二叉树的每个几点都大于它的两个子节点时，它被称为堆有序。那么，根节点就是堆有序的二叉树中的最大节点。

  二叉堆可以使用数组来存储。为了方便起见，根节点放在位置1处（位置0不使用），它的两个子节点分别放在位置2和位置3。同理可知，在一个堆中，位置k的节点的父节点的位置为k/2，而它的两个子节点的位置则分别为2k和2k+1.我们就可以这样在树的上下移动：访问a[k]节点的上一层就令k等于k/2，向下一层就令k等于2k或2k+1.

如下图所示：

  使用二叉堆，我们就能实现对数级别的插入元素和删除最大元素。

由下自上的堆有序化（上浮）

  当调用优先队列的insert方法时，我们首先把元素放置到数组的结尾，然后再把该元素上浮到正确的节点，最终形成堆有序状态。

代码如下：

1
2
3
4
5
6
7
8
9
//下标为k的元素上浮到正确位置
function swim(arr,k) {
    while(k>1 && less(arr,parseInt(k/2),k)){
        //父节点索引
        var parentNode = parseInt(k/2);
        exch(arr,parentNode,k);
        k = parentNode;
    }
}

由上至下的堆有序化（下沉）

  当调用优先队列的delMax方法时，我们下标为1的元素（最大元素）和数组最后一个元素交换，返回最大元素，数组长度减去1，即删除最后一个元素。此时的位置1元素不一定是最大元素，就需要下沉到正确位置，重新构造有序堆。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
//下标为k的元素下沉到正确位置
function sink(arr,k,len) {
    var len = len ||arr.length;
    while(2*k <= len){
        var j = 2*k;
        if(j<len && less(arr,j,j+1)) j++;
        if(!less(arr,k,j)) break;
        exch(arr,k,j);
        k = j;
    }
}

堆有序化示例图：

堆的操作示例图：

优先队列实现

  理解了实现堆有序的上浮和下沉两种方法，优先队列的实现就轻而易举了，代码如下：

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
/**
 * 优先队列
 * @constructor
 */
function MaxQueue() {
    this.queue = [];                //- 存储基于堆的完全二叉树
    this.len   = 0;                 //- 存储于queue[1..len]中，queue[0]未使用
}

/**
 * 向优先队列中插入元素
 * @param val
 */
MaxQueue.prototype.insert = function (val) {
    this.queue[++this.len] = val;    //- 从索引1开始添加元素
    //使新增元素上浮到树的正确位置
    swim(this.queue,this.len);
};

/**
 * 删除优先队列中的最大元素，并返回该元素
 * @returns {*}
 */
MaxQueue.prototype.delMax = function () {
    var max = this.queue[1];        //- 从根节点得到最大元素
    exch(this.queue,1,this.len--);  //- 把最后一个节点放到根节点上，并且让长度索引减一
    this.queue.length = this.len+1; //- 删除最后一个节点
    sink(this.queue,1);             //- 下沉根节点，恢复堆的有序性
    return max;
};

MaxQueue.prototype.show = function () {
    console.log(this.queue);
};

MaxQueue.prototype.isEmpty = function () {
    return this.len==0;
};

示例图：

堆排序

  理解了优先队列，堆排序的逻辑十分简单。第一步：让数组形成堆有序状态；第二步：把堆顶的元素放到数组最末尾，末尾的放到堆顶，在剩下的元素中下沉到正确位置，重复操作即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 堆排序算法
 * @constructor
 */
function HeapSort() {}
HeapSort.prototype.sort = function (arr) {
    var len = arr.length;
    //由于arr[0]不使用，放到最后使得能够被排序
    //注意：也可在less和exch中解决，见后面的Java完整代码实现。这里为了对应位置1的元素不使用，方便对照看代码与样例图。
    arr[len] = arr[0];
    //使用下沉来构造二叉堆
    for(var k=parseInt(len/2);k>=1;k--){
        sink(arr,k,len);
    }
    //不断把最大的arr[1]交换到最后，然后让新的arr[1]元素下沉到堆有序状态
    while (len>1){
        exch(arr,1,len--);
        sink(arr,1,len);
    }
    //删除未使用的arr[0]（也可在less和exch中解决，见Java代码实现）
    arr.splice(0,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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
/**
 * Created by YiYing on 2017/5/2.
 */
(function (W) {

    /**
     * 优先队列
     * @constructor
     */
    function MaxQueue() {
        this.queue = [];                //- 存储基于堆的完全二叉树
        this.len   = 0;                 //- 存储于queue[1..len]中，queue[0]未使用
    }

    /**
     * 向优先队列中插入元素
     * @param val
     */
    MaxQueue.prototype.insert = function (val) {
        this.queue[++this.len] = val;    //- 从索引1开始添加元素
        //使新增元素上浮到树的正确位置
        swim(this.queue,this.len);
    };

    /**
     * 删除优先队列中的最大元素，并返回该元素
     * @returns {*}
     */
    MaxQueue.prototype.delMax = function () {
        var max = this.queue[1];        //- 从根节点得到最大元素
        exch(this.queue,1,this.len--);  //- 把最后一个节点放到根节点上，并且让长度索引减一
        this.queue.length = this.len+1; //- 删除最后一个节点
        sink(this.queue,1);             //- 下沉根节点，恢复堆的有序性
        return max;
    };

    MaxQueue.prototype.show = function () {
        console.log(this.queue);
    };

    MaxQueue.prototype.isEmpty = function () {
        return this.len==0;
    };

    W.MaxQueue = MaxQueue;


    /**
     * 堆排序算法
     * @constructor
     */
    function HeapSort() {}
    HeapSort.prototype.sort = function (arr) {
        var len = arr.length;
        //由于arr[0]不使用，放到最后使得能够被排序
        //注意：也可在less和exch中解决，见后面的Java完整代码实现。这里为了对应位置1的元素不使用，方便对照看代码与样例图。
        arr[len] = arr[0];
        //使用下沉来构造二叉堆
        for(var k=parseInt(len/2);k>=1;k--){
            sink(arr,k,len);
        }
        //不断把最大的arr[1]交换到最后，然后让新的arr[1]元素下沉到堆有序状态
        while (len>1){
            exch(arr,1,len--);
            sink(arr,1,len);
        }
        //删除未使用的arr[0]（也可在less和exch中解决，见Java代码实现）
        arr.splice(0,1);
    };

    W.HeapSort = HeapSort;


    //下标为k的元素上浮到正确位置
    function swim(arr,k) {
        while(k>1 && less(arr,parseInt(k/2),k)){
            //父节点索引
            var parentNode = parseInt(k/2);
            exch(arr,parentNode,k);
            k = parentNode;
        }
    }

    //下标为k的元素下沉到正确位置
    function sink(arr,k,len) {
        var len = len ||arr.length;
        while(2*k <= len){
            var j = 2*k;
            if(j<len && less(arr,j,j+1)) j++;
            if(!less(arr,k,j)) break;
            exch(arr,k,j);
            k = j;
        }
    }

    function less(arr,m,n) {
        //可根据不同的数据类型设置比对规则，比如json。这里适用于数字与字符串。
        return arr[m]<arr[n];
    }

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


})(window);

//测试代码
(function () {
    //优先队列测试，依次从大到小输出元素
    var q = new MaxQueue();
    q.insert(3);
    q.insert(33);
    q.insert(9);
    q.insert(21);
    while (!q.isEmpty()){
        console.log(q.delMax())
    }

    //堆排序测试代码
    var arr = [4,5,6,0,3,5,21,7,9,0,1];
    new HeapSort().sort(arr);
    console.log(arr);
})();

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 Heap {
	/**
	 * 堆排序
	 * @param pq
	 */
	public static void sort(Comparable[] pq) {
        int n = pq.length;
        //构造堆结构
        for (int k = n/2; k >= 1; k--)
            sink(pq, k, n);
        //排序数组
        while (n > 1) {
            exch(pq, 1, n--);
            sink(pq, 1, n);
        }
    }

	//下沉元素
	private static void sink(Comparable[] pq, int k, int n) {
        while (2*k <= n) {
            int j = 2*k;
            if (j < n && less(pq, j, j+1)) j++;
            if (!less(pq, k, j)) break;
            exch(pq, k, j);
            k = j;
        }
    }

	//注意这里i和j都减去1
    private static boolean less(Comparable[] pq, int i, int j) {
        return pq[i-1].compareTo(pq[j-1]) < 0;
    }
    //注意这里i和j都减去1
    private static void exch(Object[] pq, int i, int j) {
        Object swap = pq[i-1];
        pq[i-1] = pq[j-1];
        pq[j-1] = swap;
    }

    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

	public static void main(String[] args) {
		String[] a = {"S","O","R","T","E","X","A","M","P","L","E"};
        Heap.sort(a);
        show(a);
	}
}

总结

  1. 不稳定。
  2. 原地排序。
  3. 时间复杂度为NlogN
  4. 空间复杂度为l

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

上一篇：排序算法07：三向快速排序
下一篇：排序算法09：总结

留言

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

算法

排序算法07：三向快速排序

算法介绍

  在上一篇排序算法06：快速排序中，可以知道，快速排序不停的递归切分数组。在有大量的重复元素情况下，这样的切分存在巨大的改进空间。三向切分的快速排序就是为了提升在有大量重复元素情况下快速排序的性能。

  快速排序把数组切分为两部分，分别对应与小于，大于切分元素的数组元素。而三向切分将数组切分为三部分，分别对应小于，等于，大于切分元素的数组元素。

  三向切分的快速排序的算法逻辑为：从左到右遍历数组一次，维护一个指针lt使得a[lo..lt-1]中的元素都小于v，一个指针gt使得a[gt+1..hi]中的元素都大于v，一个指针i使得a[gt..i-1]中的元素都等于v,a[i..gt]中的元素都还未确定。

三向切分的示意图：

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function quick3way(a,lo,hi) {
        if(hi<=lo){return;}
        var lt=lo,i=lo+1,gt=hi;
        var v = a[lo];              //- 选择a[lo]为需要切分的元素
        while (i<=gt){
            if(a[i] < v){
                exch(a,lt++,i++)
            }else if(a[i] > v){
                exch(a,i,gt--);
            }else{
                i++;
            }
        }
        /*程序运行到这里结果为:a[lo..lt-1] < v < a[gt+1,hi];其中v=a[lt..gt]*/
        quick3way(a,lo,lt-1);       //- 对左侧（a[lo..lt-1]）进行排序
        quick3way(a,gt+1,hi);       //- 对右侧(a[gt+1,hi])进行排序
    }

三向切分的轨迹：

完整代码

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
/**
 * Created by YiYing on 2017/4/30.
 */
(function (W) {
    function quick3way(a,lo,hi) {
        if(hi<=lo){return;}
        var lt=lo,i=lo+1,gt=hi;
        var v = a[lo];              //- 选择a[lo]为需要切分的元素
        while (i<=gt){
            if(a[i] < v){
                exch(a,lt++,i++)
            }else if(a[i] > v){
                exch(a,i,gt--);
            }else{
                i++;
            }
        }
        /*程序运行到这里结果为:a[lo..lt-1] < v < a[gt+1,hi];其中v=a[lt..gt]*/
        quick3way(a,lo,lt-1);       //- 对左侧（a[lo..lt-1]）进行排序
        quick3way(a,gt+1,hi);       //- 对右侧(a[gt+1,hi])进行排序
    }

    /**
     * 交换数组中m与n的位置
     * @param a  数组
     * @param m
     * @param n
     */
    function exch(a,m,n) {
        var swap    = a[m];
        a[m] = a[n];
        a[n] = swap;
    }

    W.Quick3way = function (a) {
        quick3way(a,0,a.length-1);
    }
})(window);

//测试代码
(function () {
    var chars = ['0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'];
    var arr = [];
    for(var i=0;i<1000000;i++){
        var id = Math.ceil(Math.random()*35);
        arr[i] = chars[id];
    }

    console.time("Quick3way");
    Quick3way(arr);      //- chrome下一百万数据平均120ms,明显优于快速排序
    console.timeEnd("Quick3way");
})();

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

package com.algs;

/**
 * 三向快速排序（适用于重复元素较多的情况）
 * @author YiYing
 * @data 2017年4月30日 下午10:34:09
 */
public class Quick3way {

    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int lt = lo, gt = hi;
        Comparable v = a[lo];
        int i = lo;
        while (i <= gt) {
            int cmp = a[i].compareTo(v);
            if      (cmp < 0) exch(a, lt++, i++);
            else if (cmp > 0) exch(a, i, gt--);
            else              i++;
        }

        //此时数组中的情况为：a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
        sort(a, lo, lt-1);		//- 对左侧进行排序
        sort(a, gt+1, hi);		//- 对右侧进行排序
    }


    //交换 a[i]和a[j]的位置
    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    public static void show(Integer[] a){
		for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
	}
	public static void main(String[] args) {
		Integer[] arr = {4,5,6,0,3,5,21,7,9,0,1};
		Quick3way.sort(arr,0,arr.length-1);
		Quick3way.show(arr);
	}
}


总结

  1. 不稳定。
  2. 原地排序。
  3. 时间复杂度为介于N到NlogN之间
  4. 空间复杂度为lgN
  5. 经测试验证，在存在大量重复元素情况下，三向切分的快速排序的平均排序时间明显快于快速排序

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

上一篇：排序算法06：快速排序
下一篇：排序算法08：优先队列与堆排序

留言

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

算法

排序算法06：快速排序

算法介绍

  快速排序是一种分治的排序算法。排序逻辑为：先挑一个元素来切分数组，最终让该元素的左侧都小于该元素，右侧的所有元素都大于该元素。递归的让左侧和右侧分别执行该操作，最终让整个数组变得有序。

快速排序示意图：

  咋眼一看快速排序跟归并排序很像，其实区别挺明显的。归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当左右两个数组有序时整个数组为自然有序状态。

快速排序的切分

  快速排序的核心在于数组的切分。切分的逻辑为，维护两个指针i和j，i从前往后移动，j从后往前移动。最终让切分元素的左侧都小于切分元素，右侧都大于切分元素。

切分示意图如下：

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
/**
     * 将数组a切分为a[lo...i-1],a[i],a[i+1,hi]
     * @param a     需要切分的数组
     * @param lo    起始位置
     * @param hi    结束位置
     */
    function partition(a,lo,hi) {
        var i = lo,j=hi+1;      //- i,j为左右扫描的指针
        var v = a[lo];          //- 选择第lo元素为切分元素，让lo左边的都小于a[lo],右边的都大于a[lo]
        while(true){
            //不断从前向后移动指针
            while (a[++i] < v){
                if(i==hi){break;}
            }
            //不断的从后往前移动指针
            while (v < a[--j]){
                if(j==lo){break;}
            }
            if(i>=j){break;}
            //较小的往前放，较小的往后放
            exch(a,i,j);
        }
        //把切分的元素放到正确的位置，交换lo与j的位置
        exch(a,lo,j);
        return j;
    }

一次切分的切分轨迹如下：

排序实现

切分完成了排序就比较简单了，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 快速排序
 * @param a     需要排序的数组
 * @param lo    起始位置
 * @param hi    结束位置
 */
function sort(a,lo,hi) {
    if(hi<=lo)return;
    var j = partition(a,lo,hi); //- 切分数组，让a[j]左边的都小于它，右边的都大于它。
    sort(a,lo,j-1);             //- 将左半部分a[lo..j-1]排序
    sort(a,j+1,hi);             //- 将右半部份a[j+1...hi]排序
}

完整代码

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/30.
 */

(function (W) {
    /**
     * 快速排序
     * @param a     需要排序的数组
     * @param lo    起始位置
     * @param hi    结束位置
     */
    function sort(a,lo,hi) {
        if(hi<=lo)return;
        var j = partition(a,lo,hi); //- 切分数组，让a[j]左边的都小于它，右边的都大于它。
        sort(a,lo,j-1);             //- 将左半部分a[lo..j-1]排序
        sort(a,j+1,hi);             //- 将右半部份a[j+1...hi]排序
    }

    /**
     * 将数组a切分为a[lo...i-1],a[i],a[i+1,hi]
     * @param a     需要切分的数组
     * @param lo    起始位置
     * @param hi    结束位置
     */
    function partition(a,lo,hi) {
        var i = lo,j=hi+1;      //- i,j为左右扫描的指针
        var v = a[lo];          //- 选择第lo元素为切分元素，让lo左边的都小于a[lo],右边的都大于a[lo]
        while(true){
            //不断从前向后移动指针
            while (a[++i] < v){
                if(i==hi){break;}
            }
            //不断的从后往前移动指针
            while (v < a[--j]){
                if(j==lo){break;}
            }
            if(i>=j){break;}
            //较小的往前放，较小的往后放
            exch(a,i,j);
        }
        //把切分的元素放到正确的位置，交换lo与j的位置
        exch(a,lo,j);
        return j;
    }

    /**
     * 交换数组中m与n的位置
     * @param a  数组
     * @param m
     * @param n
     */
    function exch(a,m,n) {
        var swap    = a[m];
        a[m] = a[n];
        a[n] = swap;
    }

    W.QuickSort = function (a) {
        sort(a,0,a.length);
    }
})(window);

//测试代码
(function () {
    //var arr = [4,5,6,0,3,5,21,7,9,0,1];
    //console.log(arr);
    var chars = ['0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'];
    var arr = [];
    for(var i=0;i<1000000;i++){
        var id = Math.ceil(Math.random()*35);
        arr[i] = chars[id];
    }
    console.time("QuickSort");
    QuickSort(arr);      //- chrome下一百万数据平均250ms,如果不计算长度，则小于200ms
    console.timeEnd("QuickSort");
})();

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

package com.algs;


public class Quick {

	public static void sort(Comparable[] a) {
        sort(a, 0, a.length - 1);
    }

	//让数组从a[lo] 到 a[hi]有序
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j-1);
        sort(a, j+1, hi);
    }

	// 切分数组a[lo..hi] 最终让数组满足如下状态： a[lo..j-1] <= a[j] <= a[j+1..hi]
    // 并返回j
    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        Comparable v = a[lo];
        while (true) {
            while (less(a[++i], v))
                if (i == hi) break;
            while (less(v, a[--j]))
                if (j == lo) break;
            if (i >= j) break;
            exch(a, i, j);
        }
        // 把切分的元素放到j的位置上
        exch(a, lo, j);
        return j;
    }

     // 判断v < w ?
     private static boolean less(Comparable v, Comparable w) {
         return v.compareTo(w) < 0;
     }

     // 交换 a[i]和 a[j]
     private static void exch(Object[] a, int i, int j) {
         Object swap = a[i];
         a[i] = a[j];
         a[j] = swap;
     }

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

	public static void main(String[] args) {
		Integer[] a = {1,55,32,2,3,4};
		sort(a);
		show(a);
	}

}

总结

  1. 不稳定。
  2. 原地排序。
  3. 时间复杂度为NlogN
  4. 空间复杂度为lgN
  5. 快速排序最好的情况是每次都正好能将数组对半分
  6. 如果使用左右两个辅助数组可以方便实现切分，但把数组复制回去的成本会大大降低排序的速度
  7. 归并排序和希尔排序一般都比快速排序慢。原因为：快速排序切分中用一个递增的索引将数组元素和一个定值比较。而归并排序和希尔排序在内循环中移动数据的频率较高。

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

上一篇：排序算法05：归并排序
下一篇：排序算法07：三向快速排序

留言

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