数据结构与算法分析

2018/08/21 JavaSE

数学知识

指数

对数

计算机科学中,除非特殊声明,否则所有的对数都是以2为底的。

级数

模运算

如果N整除A-B,那么就说A与B模N同余,记为$A \equiv B(mod N)$ 。直观地看,这意味着无论是A还是B被N去除,所得余数都是相同的。 于是,$81 \equiv 61 \equiv 1(mod 10)$。如同等号的情形一样,若$A \equiv B(mod N)$,则$A + C \equiv B + C(mod N)$以及$AD \equiv BD(mod N)$。

递归简论

递归调用将反复进行直到基准情形出现。

public static int f(int x){
	// 处理基准情况
	if(X == 0){
		return 0;
	}
	else{
		// 递归调用
		return 2 * f(x - 1) + x * x;
	}
}

导致递归的前两个基本法则:

  1. 基准情形(base case) 。必须总要有某些基准的情形,它们不用递归就能求解。
  2. 不断推进(making progress) 。对于那些要递归求解的情形,递归调用必须总能够朝着一个基准情形推进。

递归的四条基本法则:

  1. 基准情形。
    • 必须总要有某些基准情形,它无需递归就能解出。
  2. 不断推进。
    • 对于那些需要递归求解的情形,每一次递归调用都必须要使状况朝向一种基准情形推进。
  3. 设计法则。
    • 假设所有的递归调用都能运行。
    • 这意味着,当设计递归程序时一般没有必要知道簿记管理的细节,你不必试图追踪大量的递归调用。
    • 递归的主要问题是隐含的簿记开销。虽然这些开销几乎总是合理的(因为递归程序不仅简化了算法设计而且也有助于给出更加简洁的代码),但是递归绝不应该作为简单for循环的代替物。
  4. 合成效益法则(compound interest rule) 。
    • 在求解一个问题的同一实例时,切勿在不同的递归调用中做重复性的工作。

泛型

如果除去对象的基本类型外,实现方法是相同的,那么就可以用泛型实现(generic implementation) 来描述这种基本的功能。

数组类型的兼容性

Person[] arr = new Employee[5]; //编译: arrays are compatible
arr[O] =new Student(...); //编译: Student IS-A Person

两旬都编译,而arr[0]实际上是引用一个Employee,可是StudentIS-NOT-A Employee。这样就产生了类型混乱。 运行时系统(runtime system) (Java 虚拟机)不能抛出ClassCastException异常,因为不存在类型转换。

避免这种问题的最容易的方法是指定这些数组不是类型兼容的。可是,在Java中数组却是类型兼容的。这叫作协变数组类型(covariant araay type)。 每个数组都明了它所允许存储的对象的类型。如果将一个不兼容的类型插入到数组中,那么虚拟机将抛出一个ArrayStoreException异常。

在较早版本的Java中是需要数组的协变性的,否则下面的代码无法编译。

public void findMax(Comparable[] arr){...};
public static void main(String [] args) {
	Shape [] shl = { new Circle(2.0),
					 new Square(3.0),
					 new Rectangle(3.0, 4.0) } ;
	String [] stl = { "Joe", "Bob", "Bill", "Zeke" } ;
	System.out.println(findMax(shl));
	System.out.println(findMax(stl));
}

带有限制的通配符

泛型(以及泛型集合)不是协变的(但有意义),而数组是协变的。若无附加的语法,则用户就会避免使用集合(collection),因为失去协变性使得代码缺少灵活性。

Collection<? extends Shape> arr)

泛型限制

static的语境

static的语境在一个泛型类中,static方法和static域均不可引用类的类型变量,因为在类型擦除后类型变量就不存在了。 另外,由于实际上只存在一个原始的类,因此static域在该类的诸泛型实例之间是共享的。

泛型类型的实例化

不能创建一个泛型类型的实例。如果T是一个类型变量,则语句

T obj = new T(); // 右边是非法的

泛型数组对象

也不能创建一个泛型的数组。如果T是一个类型变量,则语句

T[] arr = new T[10]; // 右边是非法的

参数化类型的数组

参数化类型的数组的实例化是非法的。

// Type safety: The expression of type MyClass[] needs unchecked conversion to conform to MyClass<T>[]
MyClass<T>[] array = new MyClass<T>[]; 

算法分析

数学基础

典型的增长率

函数 名称
$C$ 常数
$logN$ 对数
$log^2N$ 对数平方的
$N$ 线性的
$NlogN$  
$N^2$ 二次的
$N^3$ 三次的
$2^N$ 指数的

要分析的问题

通常,要分析的最重要的资源就是运行时间。主要因素则是所使用的算法以及对该算法的输入。

  • 典型的情形是,输入的大小是主要的考虑方面。
    • 不过,通常这没有什么重要意义,因为它不代表典型的行为。
  • 偶尔也分析一个算法最好情形的性能。

仅仅从磁盘读入数据所用的时间很可能在数量级上比求解问题所需要的时间还要大。这是许多有效算法的典型特点。数据的读入一般是个瓶颈;一旦数据读入,问题就会迅速解决。 但是,对于低效率的算法情况就不同了,它必然要占用大量的计算机资源。

因此只要可能,使得算法足够有效而不至成为问题的瓶颈是非常重要的。

运算时间计算

一般法则

  • for循环
    • 一个for循环的运行时间至多是该for循环内部那些语旬(包括测试)的运行时间乘以迭代的次数。
  • 嵌套的for循环
    • 从里向外分析这些循环。在一组嵌套循环内部的一条语旬总的运行时间为该语旬的运行时间乘以该组所有的for循环的大小的乘积。
  • 顺序语句
    • 将各个语旬的运行时间求和即可(这意味着,其中的最大值就是所得的运行时间)。
    • 如$O(N)+O(N^2)=O(N^2)$
  • if/else语句
    • 一个if/else语旬的运行时间从不超过判断的运行时间再加上各个分支中运行时间长者的总的运行时间。
/**
 * Linear-time maximum contiguous subsequence sum algorithm.
 * seqStart and seqEnd represent the actual best sequence.
 */
public static int maxSubSum4(int[] a) {
	int maxSum = 0;
	int thisSum = 0;
	for (int j = 0, j = 0; j < a.length; j++) {
		thisSum += a[j];
		if (thisSum > maxSum) {
			maxSum = thisSum;
		} else if (thisSum < 0) {
			thisSum = 0;
		}
	}
	return maxSum;
}

如果数组在磁盘上或通过互联网传送,那么它就可以被按顺序读入,在主存中不必存储数组的任何部分,在任意时刻,算法都能对它已经读入的数据给出子序列问题的正确答案(其他算法不具有这个特性)。

具有这种特性的算法叫作联机算法(on-line algorithm) 。仅需要常釐空间并以线性时间运行的联机算法几乎是完美的算法。

运行时问中的对数

如果一个算法用常数时间(O(1))将问题的大小削减为其一部分(通常是1/2),那么该算法就是O(log N)。 另一方面,如果使用常数时间只是把问题减少一个常数的数量(如将问题减少1),那么这种算法就是O(N)的。

List

删除偶数位置,不使用ArrayList因为删除代价高。

public static void removeEvensVer1(List<Integer> lst) {
	int i = 0;
	while (i < lst.size()) {
		// 对于LinkedList,get调用效率不高
		if (lst.get(i) % 2 == 0) {
			// remove效率同样低
			lst.remove(i);
		} else {
			i++;
		}
	}
}
public static void removeEvensVer2(List<Integer> lst) {
	for (Integer x : lst) {
		if (x % 2 == 0) {
			// remove不高效,而且会报错
			lst.remove(x);
		}
	}
}
public static void removeEvensVer3(List<Integer> lst) {
	Iterator<Integer> itr = lst.iterator();
	while (itr.hasNext()) {
		if (itr.next() % 2 == 0) {
			// 常数时间
			itr.remove();
		}
	}
}
public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
	void remove();
	// set方法解决LinkedList对值的变更问题
    void set(E e);
    void add(E e);
}

二叉树(binary tree) 是一棵树,其中每个节点都不能有多于两个的儿子。 二叉树的一个性质是一棵平均二叉树的深度要比节点个数N小得多,平均深度为($O\sqrt{N}$)。对于即二叉查找树(binary search tree),深度平均值为($O(logN)$)。

AVL树通过旋转和双旋转达到恢复平衡。

M阶B树是一个可用于磁盘存储,通过分裂和领养合并来调整树。

散列

解决哈希冲突

分离链接法

将散列到同一个值的所有元素保留到一个表中。

开放定址法(不用链表)

使用探测散列表。

  • 线性探测法
  • 平方探测法
  • 双散列

Rehash

优先队列(堆)

二叉堆

结构性质

堆是一棵被完全填满的二叉树,有可能的例外是在底层,底层上的元素从左到右填入。这样的树称为完全二叉树(complete binary tree)

一棵完全二叉树

高是$logN$。

一个重要的观察发现,因为完全二叉树这么有规律,所以它可以用一个数组表示而不需要使用链。

完全二叉树的数组实现

对于数组中任一位置i上的元素,其左儿子在位置2i上,右儿子在左儿子后的单元(2i + 1)中,它的父亲则在位置i/2上。 因此,这里不仅不需要链,而且遍历该树所需要的操作极简单,在大部分计算机上运行很可能非常快。 这种实现方法的唯一问题在于,最大的堆大小需要事先估计,但一般这并不成问题(而且如果需要,可以重新调整大小)。

堆序性质

让操作快速执行的性质是堆序性质(heap-order property)。由于想要快速找出最小元,因此最小元应该在根上。 如果考虑任意子树也应该是一个堆,那么任意节点就应该小千它的所有后裔。

基本的堆操作

insert

上滤(percolate up);新元素在堆中上滤直到找出正确的位置。

尝试插入14: 创建一个空穴,再将空穴上冒:

上滤

/**
 * Insert into the priority queue, maintaining heap order.
 * Duplicates are allowed.
 *
 * @param x the item to insert.
 */
public void insert(AnyType x) {
	if (currentSize == array.length - 1) {
		enlargeArray(array.length * 2 + 1);
	}
	// Percolate up
	int hole = ++currentSize;
	for (array[0] = x; x.compareTo(array[hole / 2]) < 0; hole /= 2) {
		array[hole] = array[hole / 2];
	}
	array[hole] = x;
}
deleteMin

下滤。

下滤

/**
 * Remove the smallest item from the priority queue.
 *
 * @return the smallest item, or throw an com.songxp.algorithm.UnderflowException if empty.
 */
public AnyType deleteMin() {
	if (isEmpty()){
		throw new UnderflowException();
	}
	AnyType minItem = findMin();
	array[1] = array[currentSize--];
	percolateDown(1);
	return minItem;
}
/**
 * Internal method to percolate down in the heap.
 *
 * @param hole the index at which the percolate begins.
 */
private void percolateDown(int hole) {
	int child;
	AnyType tmp = array[hole];
	for (; hole * 2 <= currentSize; hole = child) {
		child = hole * 2;
		if (child != currentSize &&
				array[child + 1].compareTo(array[child]) < 0) {
			child++;
		}
		if (array[child].compareTo(tmp) < 0) {
			array[hole] = array[child];
		} else {
			break;
		}
	}
	array[hole] = tmp;
}
其他的堆操作
  • decreaseKey(降低关键字的值)
    • 通过上滤对堆进行调整
  • increaseKey(增加关键字的值)
    • 用下滤来完成。
  • delete(删除)
    • 首先执行decreaseKey(p, 无穷)然后再执行deleteMin()来完成。
  • buildHeap(构建堆)
    • 一般的算法是将N项以任意顺序放入树中,保持结构特性。此时,如果percolateDown(i)从节点i下滤
/**
 * Construct the binary heap given an array of items.
 */
public BinaryHeap(AnyType[] items) {
	currentSize = items.length;
	array = (AnyType[]) new Comparable[(currentSize + 2) * 11 / 10];
	int i = 1;
	for (AnyType item : items) {
		array[i++] = item;
	}
	buildHeap();
}
/**
 * Establish heap order property from an arbitrary
 * arrangement of items. Runs in linear time.
 */
private void buildHeap() {
	for (int i = currentSize / 2; i > 0; i--) {
		percolateDown(i);
	}
}

buildHeap

优先队列的应用

选择问题

输入是N个元素以及一个整数k,这N个元素的集可以是全序集。该选择问题是要找出第k个最大的元素。

只考虑找出第k个最小的元素。该算法很简单。将N个元素读入一个数组。然后对该数组应用buildHeap算法。最后,执行k次deleteMin操作。 从该堆最后提取的元素就是答案。显然,只要改变堆序性质,就可以求解原始的问题:找出第k个最大的元素。

如果使用buildHeap,则构造堆的最坏情形用时$O(N)$,而每次deleteMin用时$O(logN)$。由于有K次deleleeMin,因此得到总的运行时间为$O(N+klogN)$。 如果k=O(NllogN),那么运行时间取决于buildHeap操作,即$O(N)$。对于大的K值,运行时间为$O(klogN)$。如果k=N/2,那么运行时间为$\Theta(NlogN)$。

注意,如果对k=N运行该程序并在元素离开堆时记录它们的值,那么实际上已经对输入文件以时间$O(N log N)$做了排序。细化该想法,得到一种快速的排序算法,叫作堆排序(heapsort)。

使用有k个元素的堆,对剩余元素进行比较判断是否删除并插入新元素到堆中,最后弹出堆元素得到结果。时间复杂度是$N log k$。如果k=N/2,那么运行时间为$\Theta(NlogN)$。

堆的一个缺点是将连个堆合并成一个堆是困难的操作。

排序

  • 希尔排序用一个时间单位比较元素a[i]和a[i-hk]。
  • 堆排序用一个时间单位比较元素a[i] 和a[i*2+1]。
  • 使用三数中值分割法的快速排序以常数个时间单位比较a[lefet]、a[ceneter]和a[right] 。

插入排序

public static <AnyType extends Comparable<? super AnyType>>
void insertionSort(AnyType[] a) {
	int j;
	for (int p = 1; p < a.length; p++) {
		AnyType tmp = a[p];
		for (j = p; j > 0 && tmp.compareTo(a[j - 1]) < 0; j--) {
			a[j] = a[j - 1];
		}
		a[j] = tmp;
	}
}

由于嵌套循环的每一个都花费N次迭代,因此插入排序为$O(N^2)$,而且这个界是精确的,因为以反序的输入可以达到该界。

另一方面,如果输入数据已预先排序,那么运行时间为O(N),因为内层for循环的检测总是立即判定不成立而终止。 事实上,如果输入几乎被排序(该术语将在下一节更严格地定义),那么插入排序将运行得很快。 由于这种变化差别很大,因此值得去分析该算法平均情形的行为。 实际上,和各种其他排序算法一样,插入排序的平均情形也是$\Theta(NlogN)$。

定理:通过交换两个相邻元素进行排序的任何算法平局都需要$\Omega(N^2)。$

希尔排序

希尔排序(Shellsort)的名称源于它的发明者Donald Shell,该算法是冲破二次时间屏障的第一批算法之一。 它通过比较相距一定间隔的元素来工作;各趟比较所用的距离随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止。 由于这个原因,希尔排序有时也叫作缩减增量排序(diminishing increment sort)。

希尔排序使用一个序列h1, h2, … , ht, 叫作增量序列(increment sequence) 。只要h1 = 1, 任何增量序列都是可行的,不过,有些增量序列比另外一些增蜇序列更好。 在使用增量hk的一趟排序之后,对于每一个i都有a[i]<=a[i + hk](此时该不等式是有意义的);所有相隔hk的元素都被排序。此时称文件是从排序的(hk - sorted) 。

希尔排序的一个重要性质是,一个hk排序的文件(然后将是hk-1排序的)保持它的hk排序性。 假如情况不是这样的话,那么该算法很可能也就没什么价值了,因为前面各趟排序的成果就会被后面各趟排序给打乱。

/**
 * Shellsort, using Shell's (poor) increments.
 *
 * @param a an array of Comparable items.
 */
public static <AnyType extends Comparable<? super AnyType>>
void shellsort(AnyType[] a) {
	int j;

	for (int gap = a.length / 2; gap > 0; gap /= 2) {
		for (int i = gap; i < a.length; i++) {
			AnyType tmp = a[i];
			for (j = i; j >= gap && tmp.compareTo(a[j - gap]) < 0; j -= gap) {
				a[j] = a[j - gap];
			}
			a[j] = tmp;
		}
	}
}

使用希尔增量时(ht=N/2,hk=(hk+1)/2)希尔排序的最坏情形运行时间为$\Theta(N^2)$。

使用Hibbard增量(1,3,7…,$2^k-1$)的希尔排序的最坏情形运行时间为$\Theta(N^{3/2})$。

使用Hibbard增量的希尔排序平均情形运行时间基于模拟的结果被认为是$\Theta(N^{5/4})$,但是没有人能够证明该结果。Pratt证明了$\Theta(N^{3/2})$的界适用于广泛的增量序列。

Sedgewick提出了集中增量序列,其最坏情形运行时间(也是可以达到的)为$O(N^{4/3})$。对于这些增量序列的平均运行时间猜测为$O(N^{7/6})$。 经验研究指出,在实践中这些序列的运行要比Hibbard的好得多,其中最好的是序列{1, 5, 19, 41, 109, ···},该序列中的项或者是$9·4^i-9·2^i + 1$ 的形式,或者是$4^i - 3·2^i + 1$的形式。 该算法通过将这些值放到一个数组中最容易实现。虽然有可能存在某个增蜇序列使得能够对希尔排序的运行时间给出重大改进,但是,这个增量序列在实践中还是最为人们称道的。

希尔排序的性能在实践中是完全可以接受的,即使是对于数以万计的N仍是如此。编程的简单特点使得它成为对适度地大量的输入数据经常选用的算法。

堆排序

优先队列可以用于以$O(N log N)$时间的排序。基于该思想的算法叫作堆排序(heapsort),它给出了至今所见到的最佳的大O运行时间。

建立N个元素的二叉堆的基本策略,这个阶段花费$O(N)$时间。然后执行N次deleteMin操作。按照顺序,最小的元素先离开堆。 通过将这些元素记录到第二个数组然后再将数组拷贝回来,得到N个元素的排序。由于每个deleteMin花费时间$O(log N)$,因此总的运行时间是$O(N log N)$。

该算法的主要问题在于它使用了一个附加的数组。因此,存储需求增加一倍。在某些实例中这可能是个问题。

注意,将第二个数组拷贝回第一个数组的附加时间消耗只是O(N), 这不可能显著影响运行时间。这里的问题是空间的问题。

回避使用第二个数组的聪明的方法是利用这样的事实:在每次deleteMin之后,堆缩小1。因此,位于堆中最后的单元可以用来存放刚刚删去的元素。

/**
 * Internal method for heapsort.
 *
 * @param i the index of an item in the heap.
 * @return the index of the left child.
 */
private static int leftChild(int i) {
	return 2 * i + 1;
}

/**
 * Internal method for heapsort that is used in deleteMax and buildHeap.
 *
 * @param a an array of Comparable items.
 * @index i the position from which to percolate down.
 * @int n the logical size of the binary heap.
 */
private static <AnyType extends Comparable<? super AnyType>>
void percDown(AnyType[] a, int i, int n) {
	int child;
	AnyType tmp;

	for (tmp = a[i]; leftChild(i) < n; i = child) {
		child = leftChild(i);
		if (child != n - 1 && a[child].compareTo(a[child + 1]) < 0) {
			child++;
		}
		if (tmp.compareTo(a[child]) < 0) {
			a[i] = a[child];
		} else {
			break;
		}
	}
	a[i] = tmp;
}

/**
 * Standard heapsort.
 *
 * @param a an array of Comparable items.
 */
public static <AnyType extends Comparable<? super AnyType>>
void heapsort(AnyType[] a) {
	for (int i = a.length / 2 - 1; i >= 0; i--)  /* buildHeap */ {
		percDown(a, i, a.length);
	}
	for (int i = a.length - 1; i > 0; i--) {
		swapReferences(a, 0, i);                /* deleteMax */
		percDown(a, 0, i);
	}
}

/**
 * Method to swap to elements in an array.
 *
 * @param a      an array of objects.
 * @param index1 the index of the first object.
 * @param index2 the index of the second object.
 */
public static <AnyType> void swapReferences(AnyType[] a, int index1, int index2) {
	AnyType tmp = a[index1];
	a[index1] = a[index2];
	a[index2] = tmp;
}

对N个互异项的随机排列进行堆排序所用比较的平均次数为$2N log N - O(N log log N)$。

归并排序

归并排序(mergesort)。归并排序以$O(N log N)$最坏情形时间运行,而所使用的比较次数几乎是最优的。它是递归算法一个好的实例。

这个算法中基本的操作是合并两个已排序的表。因为这两个表是已排序的,所以若将输出放到第3个表中,则该算法可以通过对输入数据一趟排序来完成。

基本的合并算法是取两个输入数组A和B,一个输出数组C,以及3个计数器Actr、Bctr、Cctr,它们初始置于对应数组的开始端。 A[Actr]和B[Bctr]中的较小者被拷贝到C中的下一个位置,相关的计数器向前推进一步。当两个输入表有一个用完的时候,则将另一个表中剩余部分拷贝到C中。

合并例程

合并两个已排序的表的时间显然是线性的,因为最多进行N-1次比较,其中N是元素的总数。 每次比较都把一个元素添加到C中,但最后的比较除外,它至少添加两个元素。

因此,归并排序算法很容易描述。如果N=1,那么只有一个元素需要排序,答案是显然的。 否则,递归地将前半部分数据和后半部分数据各自归并排序,得到排序后的两部分数据,然后使用合并算法再将这两部分合并到一起。

该算法是经典的分治(divide-and-conquer) 策略,它将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段解得的各答案修补在一起。

/**
 * Mergesort algorithm.
 *
 * @param a an array of Comparable items.
 */
public static <AnyType extends Comparable<? super AnyType>>
void mergeSort(AnyType[] a) {
	AnyType[] tmpArray = (AnyType[]) new Comparable[a.length];

	mergeSort(a, tmpArray, 0, a.length - 1);
}

/**
 * Internal method that makes recursive calls.
 *
 * @param a        an array of Comparable items.
 * @param tmpArray an array to place the merged result.
 * @param left     the left-most index of the subarray.
 * @param right    the right-most index of the subarray.
 */
private static <AnyType extends Comparable<? super AnyType>>
void mergeSort(AnyType[] a, AnyType[] tmpArray,
				int left, int right) {
	if (left < right) {
		int center = (left + right) / 2;
		mergeSort(a, tmpArray, left, center);
		mergeSort(a, tmpArray, center + 1, right);
		merge(a, tmpArray, left, center + 1, right);
	}
}
/**
 * Internal method that merges two sorted halves of a subarray.
 *
 * @param a        an array of Comparable items.
 * @param tmpArray an array to place the merged result.
 * @param leftPos  the left-most index of the subarray.
 * @param rightPos the index of the start of the second half.
 * @param rightEnd the right-most index of the subarray.
 */
private static <AnyType extends Comparable<? super AnyType>>
void merge(AnyType[] a, AnyType[] tmpArray, int leftPos, int rightPos, int rightEnd) {
	int leftEnd = rightPos - 1;
	int tmpPos = leftPos;
	int numElements = rightEnd - leftPos + 1;

	// Main loop
	while (leftPos <= leftEnd && rightPos <= rightEnd) {
		if (a[leftPos].compareTo(a[rightPos]) <= 0) {
			tmpArray[tmpPos++] = a[leftPos++];
		} else {
			tmpArray[tmpPos++] = a[rightPos++];
		}
	}

	while (leftPos <= leftEnd)    // Copy rest of first half
	{
		tmpArray[tmpPos++] = a[leftPos++];
	}

	while (rightPos <= rightEnd)  // Copy rest of right half
	{
		tmpArray[tmpPos++] = a[rightPos++];
	}

	// Copy tmpArray back
	for (int i = 0; i < numElements; i++, rightEnd--) {
		a[rightEnd] = tmpArray[rightEnd];
	}
}

merge例程很精巧。如果对merge的每个递归调用均局部声明一个临时数组,那么在任一时刻就可能有logN个临时数组处在活动期。 精密的考察表明,由于merge是mergeSort的最后一行,因此在任一时刻只需要一个临时数组在活动,而且这个临时数组可以在public型的mergeSort驱动程序中建立。 不仅如此,还可以使用该临时数组的任意部分;将使用与输入数组a相同的部分,这就达到本节末尾描述的改进。

虽然归并排序的运行时间是$O(N log N)$, 但是它有一个明显的问题,即合并两个已排序的表用到线性附加内存。 在整个算法中还要花费将数据拷贝到临时数组再拷贝回来这样一些附加的工作,它明显减慢了排序的速度。这种拷贝可以通过在递归的那些交替层次上审慎地交换a和tmpArray的角色得以避免。

快速排序

快速排序(quicksort)是实践中的一种快速的排序算法,它的平均运行时间是O(NlogN)。该算法之所以特别快,主要是由于非常精练和高度优化的内部循环。 它的最坏情形性能为$O(N^2)$,但经过稍许努力可使这种情形极难出现。

通过将快速排序和堆排序结合,由于堆排序的$O(NlogN)$最坏情形运行时间,可以对几乎所有的输入都能达到快速排序的快速运行时间。 (在递归之层到达depth(初始值近似为2logN)时对当前的子数组调用heapsort,当进行递归调用时使depth减1,当它为0时切换到heapsort。)

像归并排序一样,快速排序也是一种分治的递归算法。

public static void sort(List<Integer> items) {
	if (items.size() > 1) {
		List<Integer> smaller = new ArrayList<>();
		List<Integer> same = new ArrayList<>();
		List<Integer> larger = new ArrayList<>();

		Integer chosenItem = items.get(items.size() / 2);
		for (Integer i : items) {
			if (i < chosenItem) {
				smaller.add(i);
			} else if (i > chosenItem) {
				larger.add(i);
			} else {
				same.add(i);
			}
		}
		sort(smaller); // Recursive call!
		sort(larger); // Recursive call!

		items.clear();
		items.addAll(smaller);
		items.addAll(same);
		items.addAll(larger);

	}
}

描述最常用的快速排序的实现——“经典快速排序”,其中输入存放在数组里,且算法不产生额外的数组。

将数组S排序的基本算法由下列简单的四步组成:

  1. 如果S中元素个数是0或1,则返回。
  2. 取S中任一元素v,称之为枢纽元(pivot)。
  3. 将S-{v}(S中其余元素)划分成两个不相交的集合:$S1={x \in S-{v} x<=v}和S2={x \in S-{v} x>=v}$。
  4. 返回{quicksort(S1)后跟v,继而返回quicksort(S2)}。

由于对那些等于枢纽元的元素的处理上,第3步分割的描述不是唯一的,因此这就成了一种设计决策。一部分好的实现方法是将这种情形尽可能有效地处理。 直观地看,希望把等于枢纽元的大约一半的关键字分到S1中,而另外的一半分到S2中,很像希望二叉查找树保待平衡的情形。

如同归并排序那样,快速排序递归地解决两个子问题并需要线性的附加工作(第3步),不过,与归并排序不同,这两个子问题并不保证具有相等的大小,这是个潜在的隐患。 快速排序更快的原因在于,第3步分割成两组实际上是在适当的位置进行并且非常有效,它的高效不仅可以弥补大小不等的递归调用的不足而且还能有所超出。

快速排序的各步

/**
 * Quicksort algorithm.
 *
 * @param a an array of Comparable items.
 */
public static <AnyType extends Comparable<? super AnyType>>
void quicksort(AnyType[] a) {
	quicksort(a, 0, a.length - 1);
}
/**
 * Internal quicksort method that makes recursive calls.
 * Uses median-of-three partitioning and a cutoff of 10.
 *
 * @param a     an array of Comparable items.
 * @param left  the left-most index of the subarray.
 * @param right the right-most index of the subarray.
 */
private static <AnyType extends Comparable<? super AnyType>>
void quicksort(AnyType[] a, int left, int right) {
	if (left + CUTOFF <= right) {
		// 获取中值,并做顺序交换,变更起始位置,防止极端数据产生坏的结果
		AnyType pivot = median3(a, left, right);

		// Begin partitioning
		int i = left, j = right - 1;
		for (; ; ) {
			while (a[++i].compareTo(pivot) < 0) {
			}
			while (a[--j].compareTo(pivot) > 0) {
			}
			if (i < j) {
				swapReferences(a, i, j);
			} else {
				break;
			}
		}

		swapReferences(a, i, right - 1);   // Restore pivot

		quicksort(a, left, i - 1);    // com.songxp.algorithm.Sort small elements
		quicksort(a, i + 1, right);   // com.songxp.algorithm.Sort large elements
	} else  // Do an insertion sort on the subarray
	{
		insertionSort(a, left, right);
	}
}
/**
 * Method to swap to elements in an array.
 *
 * @param a      an array of objects.
 * @param index1 the index of the first object.
 * @param index2 the index of the second object.
 */
public static <AnyType> void swapReferences(AnyType[] a, int index1, int index2) {
	AnyType tmp = a[index1];
	a[index1] = a[index2];
	a[index2] = tmp;
}

/**
 * Return median of left, center, and right.
 * Order these and hide the pivot.
 */
private static <AnyType extends Comparable<? super AnyType>>
AnyType median3(AnyType[] a, int left, int right) {
	int center = (left + right) / 2;
	if (a[center].compareTo(a[left]) < 0) {
		swapReferences(a, left, center);
	}
	if (a[right].compareTo(a[left]) < 0) {
		swapReferences(a, left, right);
	}
	if (a[right].compareTo(a[center]) < 0) {
		swapReferences(a, center, right);
	}
	// Place pivot at position right - 1
	swapReferences(a, center, right - 1);
	return a[right - 1];
}

选取枢纽元

  • 选取第一个元素或者两个互异的关键字中的较大者作为枢纽元,是一种错误的方法。
  • 一种安全的方法是使用随机选区,但是随机数的生成一般开销很大,根本减少不了算法其余部分的平均运行时间。
  • 三数中值分割法(Median-of-Three Partitioning)
    • 一组N个数的中值(也叫作中位数)是第N/2个最大的数。枢纽元的最好的选择是数组的中值。不幸的是,这很难算出并且会明显减慢快速排序的速度。
    • 这样的中值的估计量可以通过随机选取三个元素并用它们的中值作为枢纽元而得到。
    • 事实上,随机性并没有多大的帮助,因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。

分割策略

分割是一种很容易出错或低效的操作,但使用一种已知方法是安全的。

第一步是通过将枢纽元与最后的元素交换使得枢纽元离开要被分割的数据段。 i从第一个元素开始而j从倒数第二个元素开始。

原始输入

在分割阶段要做的就是把所有小元素移到数组的左边而把所有大元素移到数组的右边。“小”和“大”是相对于枢纽元而言的。

当i在j的左边时,将i右移,移过那些小于枢纽元的元素,并将j左移,移过那些大于枢纽元的元素。 当i和j停止时,i指向一个大元素而j指向一个小元素。如果i在j的左边,那么将这两个元素互换,其效果是把一个大元素推向右边而把一个小元素推向左边。

移动交换

在最后一步当枢纽元与i所指向的元素交换时,知道在位置p<i的每一个元素都必然是小元素,这是因为或者位置p包含一个从它开始移动的小元素, 或者位置p上原来的大元素在交换期间被置换了。类似的论断指出,在位置p>i上的元素必然都是大元素。

考虑的一个重要的细节是如何处理那些等于枢纽元的元素。 问题在于当i遇到一个等于枢纽元的元素时是否应该停止,以及当j遇到一个等于枢纽元的元素时是否应该停止。 直观地看,i和j应该做相同的工作,否则分割将出现偏向一方的倾向。例如,如果i停止而j不停,那么所有等于枢纽元的元素都将被分到S2中。

考虑数组中所有的元索都相等的情况。如果i和j都停止,那么在相等的元素间将有很多次交换。虽然这似乎没有什么意义,但是其正面的效果则是i和j将在中间交错, 因此当枢纽元被替代时,这种分割建立了两个几乎相等的子数组。此时总的运行时间为$O(N log N)$。

如果i和j都不停止,那么就应该有相应的程序防止i和j越出数组的端点,不进行交换的操作。 虽然这样似乎不错,但是正确的实现方法却要把枢纽元交换到i最后到过的位置,这个位置是倒数第二个位置(或最后的位置,这依赖于精确的实现)。 这样的做法将会产生两个非常不均衡的子数组。如果所有的关键字都是相同的,那么运行时间则是O(N2)。对于预排序的输入而言,其效果与使用第一个元素作为枢纽元相同。

进行不必要的交换建立两个均衡的子数组要比蛮干冒险得到两个不均衡的子数组好。 因此,如果i和j遇到等千枢纽元的关键字,那么就让i和j都停止。对于这种输入,这实际上是四种可能性中唯一的一种不花费二次时间的可能。

小数组

对于很小的数组(N<=20),快速排序不如插入排序。 不仅如此,因为快速排序是递归的,所以这样的情形经常发生。通常的解决方法是对于小的数组不使用递归的快速排序,而代之以诸如插入排序这样的对小数组有效的排序算法。

使用这种策略实际上可以节省大约15%(相对于不用截止的做法而自始至终使用快速排序时)的运行时间。 一种好的截止范围(cut off range)是N=10,虽然在5到20之间任一截止范围都有可能产生类似的结果。 这种做法也避免了一些有害的退化情形,如取三个元素的中值而实际上却只有一个或两个元素的情况。

选择问题的线性期望算法

快速选择的步骤如下:

  1. 如果 S =1,那么k=1并将S中的元素作为答案返回。如果正在使用小数组的截止(cutoff)方法且|S|<=CUTOFF,则将S排序并返回第k个最小元素。
  2. 选取一个枢纽元$v \in S$。
  3. 将集合S- v 分割成S1和S2,就像在快速排序中所做的那样。
  4. 分情况计算
    • 如果k<=|S1|,那么第k个最小元必然在S1中。在这种情况下,返回quickselect(S1,k)。
    • 如果k=1+|S1|,那么枢纽元就是第k个最小元,将它作为答案返回。
    • 否则,这第k个最小元就在S2中,它是S2中的第(k- S1 -1)个最小元。进行一次递归调用并返回quickselect(S2,k- S1 -1)。

快速选择的最坏请和快速排序相同,也是$O(N^2)$。平均运行时间是$O(N)$。

/**
 * Quick selection algorithm.
 * Places the kth smallest item in a[k-1].
 *
 * @param a an array of Comparable items.
 * @param k the desired rank (1 is minimum) in the entire array.
 */
public static <AnyType extends Comparable<? super AnyType>>
void quickSelect(AnyType[] a, int k) {
	quickSelect(a, 0, a.length - 1, k);
}

/**
 * Internal selection method that makes recursive calls.
 * Uses median-of-three partitioning and a cutoff of 10.
 * Places the kth smallest item in a[k-1].
 *
 * @param a     an array of Comparable items.
 * @param left  the left-most index of the subarray.
 * @param right the right-most index of the subarray.
 * @param k     the desired index (1 is minimum) in the entire array.
 */
private static <AnyType extends Comparable<? super AnyType>>
void quickSelect(AnyType[] a, int left, int right, int k) {
	if (left + CUTOFF <= right) {
		AnyType pivot = median3(a, left, right);

		// Begin partitioning
		int i = left, j = right - 1;
		for (; ; ) {
			while (a[++i].compareTo(pivot) < 0) {
			}
			while (a[--j].compareTo(pivot) > 0) {
			}
			if (i < j) {
				swapReferences(a, i, j);
			} else {
				break;
			}
		}

		swapReferences(a, i, right - 1);   // Restore pivot

		if (k <= i) {
			quickSelect(a, left, i - 1, k);
		} else if (k > i + 1) {
			quickSelect(a, i + 1, right, k);
		}
	} else  // Do an insertion sort on the subarray
	{
		insertionSort(a, left, right);
	}
}

线性时间的排序:桶排序和基数排序

桶排序(bucket sort)。为使桶排序能够正常工作,必须要有一些附加的信息。输入数据A1,A2,…,AN必须仅由小于M的正整数组成(显然还有可能对此进行扩充)。 如果是这种情况,那么算法很简单:使用一个大小为M的称为count的数组,初始化为全0。 于是,count有M个单元(或称为桶),初始为空。当读入Ai时,count[Ai]增1。在所有的团团输入数据被读入后,扫描数组count,打印出排序后的表。 该算法用时O(M+N)。如果M为O(N),那么总时间就是O(N)。

尽管桶排序看似太平凡而用处不大,但是实际上却存在许多其输入只是一些小整数的情况,使用像快速排序这样的排序方法真的是小题大作了。 一个这样的例子便是基数排序(radix sort) 。

基数排序的一个应用是将字符串排序。如果所有字符串都有同样的长度L,则对每个字符使用桶,可以实现在O(NL)时间内的基数排序。 在代码中,假设所有字符都是ASCII码,位于Unicode字符集的前256位。 在每一趟中,把一个元素加到合适的桶里,然后当所有的桶都填好后,逐步走过这些桶,把所有东西倒回到数组里去。

注意,当一个桶被填好,又在下一趟被清空时,从当前趟得到的顺序是被保留的。

/*
 * Radix sort an array of Strings
 * Assume all are all ASCII
 * Assume all have same length
 */
public static void radixSortA(String[] arr, int stringLen) {
	final int BUCKETS = 256;
	ArrayList<String>[] buckets = new ArrayList[BUCKETS];
	for (int i = 0; i < BUCKETS; i++) {
		buckets[i] = new ArrayList<>();
	}
	for (int pos = stringLen - 1; pos >= 0; pos--) {
		for (String s : arr) {
			buckets[s.charAt(pos)].add(s);
		}
		int idx = 0;
		for (ArrayList<String> thisBucket : buckets) {
			for (String s : thisBucket) {
				arr[idx++] = s;
			}
			thisBucket.clear();
		}
	}
}

计数基数排序(counting radix sort)是基数排序的另一种实现,它避免使用ArrayList。取而代之的是一个计数器,记录每个桶里会装多少个元素; 这个信息可以放在一个数组count里,于是count[k]就是桶k中元素的个数。然后可以用另一个数组offset,使得offset[k]表示值严格小于k的元素的个数。 则当在最后的扫描中第一次见到K时,offset[k]告诉一个可以把k写进去的有效的数组位置(但是不得不为这个写操作使用一犀个临时数组),这一步做完后,offset[k]就加1。

计数基数排序因此不需要维护一堆表。要做更进一步的优化,还可以不用offset,而是重用cou洹数组。修改方法是,一开始让count[k+l]表示桶k中元素的个数。 等这个信息计算完成后,按下标从小到大扫描count数组,把count[k]加上count[k-1]。容易验证,这样扫描后,count数组里就存了跟原来offset数组里存的完全一样的信息。

/*
 * Counting radix sort an array of Strings
 * Assume all are all ASCII
 * Assume all have same length
 */
public static void countingRadixSort(String[] arr, int stringLen) {
	final int BUCKETS = 256;
	int N = arr.length;
	String[] buffer = new String[N];
	String[] in = arr;
	String[] out = buffer;
	for (int pos = stringLen - 1; pos >= 0; pos--) {
		int[] count = new int[BUCKETS + 1];
		for (int i = 0; i < N; i++) {
			count[in[i].charAt(pos) + 1]++;
		}
		for (int b = 1; b <= BUCKETS; b++) {
			count[b] += count[b - 1];
		}
		for (int i = 0; i < N; i++) {
			out[count[in[i].charAt(pos)]++] = in[i];
		}
		// swap in and out roles
		String[] tmp = in;
		in = out;
		out = tmp;
	}
	// if odd number of passes, in is buffer, out is arr; so copy back
	if (stringLen % 2 == 1) {
		System.arraycopy(in, 0, out, 0, arr.length);
	}
}

一般地,计数基数排序比用ArrayList要好,但是它在定位方面较差(out不是顺序填入的),所以令人惊讶的是,它并不总是比用一个ArrayList数组更快。

可以把两个版本的基数排序中的任一个扩展为可以处理变长的字符串。基本算法是,首先将字符串按其长度排序。 并不看全部的字符串,而是只看那些已知是充分长的字符串。由于字符串长度都是小整数,所以初始的长度排序可以用一一桶排序!

定长字符串的计数基数排序:

/*
 * Radix sort an array of Strings
 * Assume all are all ASCII
 * Assume all have length bounded by maxLen
 */
public static void radixSort(String[] arr, int maxLen) {
	final int BUCKETS = 256;

	ArrayList<String>[] wordsByLength = new ArrayList[maxLen + 1];
	ArrayList<String>[] buckets = new ArrayList[BUCKETS];

	for (int i = 0; i < wordsByLength.length; i++) {
		wordsByLength[i] = new ArrayList<>();
	}

	for (int i = 0; i < BUCKETS; i++) {
		buckets[i] = new ArrayList<>();
	}
	// 长度进行桶排序
	for (String s : arr) {
		wordsByLength[s.length()].add(s);
	}
	// 放回数组
	int idx = 0;
	for (ArrayList<String> wordList : wordsByLength) {
		for (String s : wordList) {
			arr[idx++] = s;
		}
	}

	int startingIndex = arr.length;
	for (int pos = maxLen - 1; pos >= 0; pos--) {
		startingIndex -= wordsByLength[pos + 1].size();
		// 处理pos有字符的情况
		for (int i = startingIndex; i < arr.length; i++) {
			buckets[arr[i].charAt(pos)].add(arr[i]);
		}

		idx = startingIndex;
		for (ArrayList<String> thisBucket : buckets) {
			for (String s : thisBucket) {
				arr[idx++] = s;
			}

			thisBucket.clear();
		}
	}
}

外部排序

大部分内部排序算法都用到内存可直接寻址的事实。 如果输入数据在磁带上,那么所有这些操作就失去了它们的效率,因为磁带上的元素只能被顺序访问。 即使数据在磁盘上,由于转动磁盘和移动磁头所需的延迟,仍然存在实际上的效率损失。

多路合并

两个顺串的合并操作通过将每一个输入磁带转到每个顺串的开头来进行。然后,找到较小的元素,把它放到输出磁带上,并将相应的输入磁带向前推进。

如果有K盘输入磁带,那么这种方法以相同的方式工作,唯一的区别在于,它发现k个元素中最小的元素稍微复杂一些。 可以通过使用优先队列找出这些元素中的最小元。为了得出下一个写到磁盘上的元素,进行一次deleteMin操作。 将相应的磁带向前推进,如果在输入磁带上的顺串尚未完成,那么将新元素插入到优先队列中。

总结

对于大部分一般的内部排序的应用,选用的方法不是插入排序、希尔排序、归并排序就是快速排序,这主要是由输入的大小以及底层环境来决定的。

  • 插入排序适用于非常少量的输入。
  • 对于中等规模的输入,希尔排序是个不错的选择。只要增量序列合适,它可以只用少量代码就给出优异的表现。
  • 归并排序最坏情况下的表现为O(MogN),但是需要额外空间。然而,它用到的比较次数是近乎最优的,因为任何仅用元素比较来进行排序的算法都会对某些输入序列必须用至少log(N!)次比较。
  • 快速排序自己并不保证提供这种最坏时间复杂度,并且编程比较麻烦。但是,它可以几乎肯定地做到O(MogN),并且跟堆排序组合在一起就可以保证最坏情况下有O(N log N)。
  • 用基数排序可以将字符串在线性时间内排序,这在某些情况下是相对于基于比较的排序法而言更实际的另一种选择。

不相交集类

解决动态等价问题的方案有两种。

  • 一种方案保证指令find能够以常数最坏情形运行时间执行,
  • 而另一种方案则保证指令union能够以常数最坏情形运行时间执行。

业已证明二者不能同时以常数最坏情形运行时间执行。

算法设计技巧

贪婪算法

贪婪算法分阶段地工作。在每一个阶段,可以认为所做决定是好的,而不考虑将来的后果。通常,这意味着选择的是某个局部最优。 这种“眼下能够拿到的就拿”的策略是这类算法名称的来源。当算法终止时,希望局部最优等于全局最优。 如果是这样的话,那么算法就是正确的;否则,算法得到的是一个次最优解(suboptimal solution)。 如果不要求绝对最佳答案,那么有时使用简单的贪婪算法生成近似的答案,而不是使用通常产生准确答案所需要的复杂算法。

分治算法

用于设计算法的另一种常用技巧为分治算法(divide and conquer) 。分治算法由两部分组成:

  • 分(divide) : 递归解决较小的问题(当然,基本情况除外)。
  • 治(conquer): 然后从子问题的解构建原问题的解。

传统上,在正文中至少含有两个递归调用的例程叫作分治算法,而正文中只含一个递归调用的例程不是分治算法。一般坚持子问题是不相交的(即基本上不重叠)。


参考《github》。

以上总结于《数据结构与算法分析 Java语言描述》

Search

    Post Directory