介绍

快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立地排序，当两个子数组都有序时整个数组也就有序了。快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序。归并排序将一个数组等分成两半，递归调用发生在处理整个数组之前；快速排序切分（partition）的位置取决于数组的内容，递归调用发生在处理整个数组之后。快速排序示意图：

介绍

归并：将两个有序的数组归并成一个更大的有序数组。归并排序：排序一个数组，先递归地将它分成两半分别排序，然后将结果归并起来。归并排序的优点是能够保证将任意长度为N的数组排序所需时间和NlogN成正比；主要缺点是它需要的额外空间和N成正比。

介绍

希尔排序是一种基于插入排序的快速的排序算法。插入排序对于大规模的乱序数组效率很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序数组排序。

介绍

排序就是将一组对象按照某种逻辑顺序重新排列的过程。排序算法的目标是将所有元素的主键按照某种方式排列。在java中，元素通常都是对象，对主键的描述则是通过一种内置的机制—Comparable接口。

排序算法类的模板：

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

/**
 * 排序算法类的模板
 * @author guangguang_duan
 *
 */
public class SortExample {

	public static void sort(Comparable[] a){
		//各种排序算法
	}
	
	private static boolean less(Comparable v, Comparable w){
		return v.compareTo(w) < 0;
	}
	
	private static void exch(Comparable[] a, int i, int j){
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
	
	private static void show(Comparable[] a){
		//单行中打印数组
		for(int i = 0; i < a.length; i++){
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}
	
	public static boolean isSorted(Comparable[] a){
		//测试数组元素是否有序
		for(int i = 1; i < a.length; i++){
			if(less(a[i],a[i-1])){
				return false;
			}
		}
		return true;
	}
	
	public static void main(String[] args) {
		//从标准输入读取字符串，将他们排序并输出
		String[] a = StdIn.readStrings();
		sort(a);
		assert isSorted(a);//确认排序后数组元素都是有序的
		show(a);
	}
}

介绍

输入一系列整数对，其中每个整数都表示一个某种类型的对象，一对整数p和q可以理解成“p和q是相连的”。我们假设“相连”是一种等价关系，这意味着它具有：

• 自反性：p和p是相连的；
• 对称性：如果p和q是相连的，那么q和p也是相连的；
• 传递性：如果p和q是相连的且q和r是相连的，那么p和r也是相连的。

当程序从输入中读取了整数对p,q时，如果已知的所有整数对都不能说明p和q是相连的，则将这对整数写到输出，如果已知的数据可以说明p和q是相连的，则忽略这对整数对继续处理下一对整数对。要求程序能够判断给定的整数对是否相连。

我们程序限定为网络问题，所以使用网络方面的术语：将对象称为触点，将整数对称为连接，将等价类称为连通分量。

union-find算法的API：

介绍

定义：链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该结点含有一个泛型的元素和一个指向另一条链表的引用。

结点是一个可能包含任意类型数据的抽象实体，它所包含的指向结点的应用显示了它在构造链表之中的作用。

介绍

栈是一种基于后进先出（LIFO）策略的集合类型。在应用程序中使用栈迭代器的一个典型原因是在用集合保存元素的同时颠倒它们的顺序。栈的一个典型用例：把标准输入的所有整数逆序排列。

1
2
3
4
5
6
7
8
9
10
11
12
13

public class StackOfType {

	public static void main(String[] args) {
		Stack<Integer> stack = new Stack<Integer>();
		while(!StdIn.isEmpty()){
			stack.push(StdIn.readInt());
		}
		
		for(int i : stack){
			System.out.println(i);
		}
	}
}

介绍

队列是一种基于先进先出（FIFO）策略的集合类型。按照任务产生的顺序来完成它们的策略。在应用程序中使用队列的主要原因是在用集合保存元素的同时保存它们的相对顺序：入列顺序和出列顺序相同。队列的一个典型用例：

介绍

许多基础数据类型都和对象的集合有关，具体来说，数据类型的值就是一组对象的集合，所有操作都是关于添加、删除或是访问集合中的对象。背包、队列和栈这三种数据类型，不同之处在于删除或者访问对象的顺序不同。

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

HashMap概述