桶排序

桶排序(bucket sort)假设输入均匀而独立的分布在区间[0,1)上,在满足假设时,可以以线性时间运行。

基本思想:把区间划分成n个相同大小的子区间,或称桶。然后将n个输入数分布到各个桶中,由于输入数在区间上均匀分布,一般不会出现一个桶中出现太多数的情况。然后对各个桶进行分别排序,最后将各桶中元素合并即可。

Java程序实现

(简便起见,程序中链表和排序部分使用Java标准库)

[code lang=”java”]import java.util.LinkedList; import java.util.Collections;

public class BucketSort{ @SuppressWarnings("unchecked") public static Double[] sort(double[] A){ int n = A.length; LinkedList<Double>[] B = (LinkedList<Double>[])new LinkedList[n]; for(int i = 0; i < n; i++){ int index = (int)Math.floor(A[i] * n); LinkedList<Double> list = B[index]; if(list == null){ list = new LinkedList<Double>(); B[index] = list; } list.add(Double.valueOf(A[i])); } for(int i = 0; i < n; i++){ LinkedList<Double> list = B[i]; if(list != null){ Collections.sort(list); } } LinkedList<Double> result = new LinkedList<Double>(); for(int i = 0; i < n; i++){ if(B[i] != null){ result.addAll(B[i]); } } Double[] C = (Double[]) result.toArray(new Double[n]); return C; }

public static void main(String[] args){
	double[] array = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
	for(double i : array){
		System.out.print(i + &quot;,&quot;);
	}
	System.out.print(&quot;\n&quot;);
	Double[] result = sort(array);
	for(double i : result){
		System.out.print(i + &quot;,&quot;);
	}
}

} [/code]

算法复杂度

输入符合均匀分布时,桶排序的期望运行时间为\(\Theta(n)\)。当输入不满足均匀分布,如果输入满足:各个桶尺寸的平方和与总的元素数呈线性关系,桶排序仍以线性时间运行。

Published: 09 Sep 2011

基数排序

基数排序(radix sort)从最低位到最高位依次对数字的每一位进行排序,待最高位排序结束后,整个数字的排序也完成了。对于按位排序算法,需要保证排序是稳定的,否则基数排序会出错。下面的实现中按位排序使用计数排序

Java程序实现

[code lang=”java”]public class RadixSort{ public static void countingSortByDigit(int[]A, int[]B, int k, int digit){ int[] C = new int[k + 1]; for(int i : C){ C[i] = 0; } int digitNum; for(int j = 0; j < A.length; j++){ //取数字的相应位数字用于排序 digitNum = A[j] / (int)Math.pow(10, digit) % 10; C[digitNum]++; } for(int i = 1; i <= k; i++){ C[i] = C[i] + C[i - 1]; } for(int j = A.length - 1; j >= 0; j–){ digitNum = A[j] / (int)Math.pow(10, digit) % 10; B[C[digitNum] - 1] = A[j]; C[digitNum]–; } }

public static int[] radixSort(int[]A, int d){
	for(int i = 0; i &lt; d; i++){
		int[] B = new int[A.length];
		countingSortByDigit(A, B, 9, i);
		A = B;
	}
	return A;
}

public static void main(String[] args){
	int[] A = {329, 457, 657, 839, 436, 720, 355};
	for(int i : A){
		System.out.print(i + &quot;,&quot;);
	}
	System.out.print(&quot;\n&quot;);
	A = radixSort(A, 3);
	for(int i : A){
		System.out.print(i + &quot;,&quot;);
	}
} }[/code]

算法复杂度

给定n个d位数,每一个数位可以取k种可能的值。如果所用的稳定排序需要\(\Theta(n+k)\)的时间,基数排序能以\(\Theta(d(n+k))\)的时间正确地对这些数进行排序。当d为常数、\(k=O(n)\)时,基数排序具有线性运行时间。

练习题8.3-4

说明如何在O(n)时间内,对0到\(n^2-1\)之间的n个数进行排序。

Answer:将这n个数转换为基数为n的2位数,然后使用基数排序,则排序时间为\(\Theta(2(n))\)=\(\Theta(n)\)。

Published: 04 Sep 2011

那些认真写博客的人

在写博客和读博客的过程中发现了很多优秀的博主和博客,比如刘未鹏的博客、王建硕的博客、结构之法-算法之道博客,还有本科同学maigo的人人网日志等等。

每当看到这样的博客,总会有敬佩和催人奋进的感觉,那些经年累月积累下来的文字里能让人看到认真生活的力量,那些博主就是题目中认真写博客的人。

我从去年九月建立独立博客站点,不知不觉一年过去了。回顾我的博文,自觉只能算是个写博客的人,还不够认真。其实可以写更多的,但许多话题在要不要写的犹豫中错过了。这类话题往往是因为担心写的太简单被鄙视,比如学习和工作过程中积累的知识经验等。不过我已渐渐放下了这种担心,因为许多东西不记录下来就流逝了,再遇到类似问题还要查找、实验解决方法,既然写下来是有用的,何必担心无谓的"鄙视"呢,即使有什么鄙视,也正是进步的动力。

许多时候仰望太久,以至于不愿意也没有勇气从最简单的事情着手。另一些时候,总觉得太晚了不愿意开始动手做,实际上回头来看,每当觉得晚的时候,如果开始,往往并不晚。晚只是偷懒的借口。关于写博客,刘未鹏说,"写博客这件事情给我最大的体会就是,一件事情如果你能够坚持做8年,那么不管效率和频率多低,最终总能取得一些很可观的收益。"

坚持下去,即便是写博客这样"简单"的事也能做出成绩来。如果在坚持过程中感到迷茫,记得:许多迷茫和焦虑来自人生观和生活目标的缺失,而这种缺失(模糊)往往在同别人的比较中更显突出。你应当有自己的生活方式,不要随波逐流。

Published: 03 Sep 2011

计数排序

计数排序假设n个输入元素中的每一个都是介于0到k之间的整数,此处k为某个整数。当\(k=O(n)\)时,计数排序的运行时间为\(\Theta(n)\)。

计数排序的基本思想:对每一个输入元素x,确定出小于x的元素个数。根据这一信息把x直接放到最终输出数组的位置上。

假定输入是数组A[0..n-1],length[A]=n。此外需要两个辅助数组:存放排序结果的数组B[0..n-1],提供临时存储区的C[0..k]。(此处数组下标均从0开始,和《算法导论》伪代码描述不同。)

程序实现

[code lang=”java”] public class CountingSort{ public static void sort(int[]A, int[]B, int k){ int[] C = new int[k + 1]; for(int i : C){ C[i] = 0; } for(int j = 0; j < A.length; j++){ C[A[j]]++; } for(int i = 1; i <=k; i++){ C[i] = C[i] + C[i - 1]; } for(int j = A.length - 1; j >= 0; j–){ B[C[A[j]] - 1] = A[j]; C[A[j]]–; } } public static void main(String[] args){ int[] A = {2,5,3,0,2,3,0,3}; int[] B = new int[A.length]; int k = 5;

	for(int i : A){
		System.out.print(i + &quot;,&quot;);
	}
	System.out.print(&quot;\n&quot;);
	sort(A, B, k);
	for(int i : B){
		System.out.print(i + &quot;,&quot;);
	}
} }[/code]

排序过程实际是四个循环,前三个循环统计出小于等于每个输入元素的数字个数,最后一个循环根据这些个数将待排序的数依次放到新数组中合适的位置。

计数排序的一个重要性质:稳定性,即具有相同值的元素在输出数组中的相对次序没有改变。当卫星数据随被排序的元素一起移动时,稳定性比较重要。

Published: 01 Sep 2011

测试Latex for WordPess

\(\alpha+\beta\) \(!\alpha+\beta\) \(\alpha+\beta\geq\gamma!\)

Published: 01 Sep 2011

快速排序

快速排序是一种排序算法,对包含n个数的输入数组,最坏情况运行时间为O(n^2),平均运行时间为O(nlgn),可以进行就地排序。快速排序通常是用于排序的最佳的使用选择。

和合并排序一样,快速排序也是基于分治模式,对一个典型子数组A[p..r]排序的分治过程包含三个步骤:

分解:将数组A[p..r]分成两个(可能空)的子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每个元素都小于等于A[q],而且小于等于A[q+1..r]中的元素。下标q在这个过程中计算。

解决:递归调用快速排序,对子数组A[p..q-1]和A[q+1..r]排序。

合并:整个数组A[p..r]已经排序。

数组划分PARTITION

快速排序算法的关键是数组划分过程PARTITION,它对子数组A[p..r]进行就地重排:

[code lang=”java”]public static int partition(int[] A, int p, int r){ int x = A[r]; int i = p - 1; for(int j = p; j < r; j++){ if(A[j] <= x){ i++; int temp = A[j]; A[j] = A[i]; A[i] = temp; } } i++; A[r] = A[i]; A[i] = x; return i; }[/code]

PARTITION在子数组上的运行时间为O(n),n=r-p+1。

快速排序实现

[code lang=”java”]public static void quickSort(int[] A, int p, int r){ if(p < r){ int q = partition(A, p, r); quickSort(A, p, q - 1); quickSort(A, q + 1, r); return; } else{ return; } }[/code]

快速排序性能

快速排序的运行时间与划分是否对称有关。如果划分对称,快速排序从渐进意义上和合并算法一样快;如果划分不对称,快排和插入算法一样慢。

如果在算法的每一层递归上,划分都是最大程度不对称的,则运行时间是O(n^2);如果每一层划分是最平衡的,则运行时间是O(nlgn)。在平均情况下,运行时间是O(nlgn)。

快速排序的随机化版本

对快速排序中加入随机化成分,使得对于所有输入,它均能获得较好的平均情况性能。

采用随机取样的方法,在子数组A[p..r]中随机选择一个元素和A[r]交换,再选取A[r]作为主元素,这样主元素是随机选择的。期望在平均情况下,对输入数组的划分能够比较匀称。

测试代码:

[code lang=”java”]public class QuickSort{ public static void main(String[] args){ int[] array = {3, 2, 6, 1, 9, 7, 8, 5, 4}; for(int i : array){ System.out.print(i + ","); } System.out.print("\n"); quickSort(array, 0, array.length - 1); for(int i : array){ System.out.print(i + ","); } } } [/code]

Published: 28 Aug 2011

优先级队列

优先级队列(priority queue)是堆的一个常见应用。有两种队列:最大优先级队列和最小优先级队列。

优先级队列是一种用来维护由一组元素构成的集合S的数据结构,这一组元素中的每一个都有一个关键字key。 一个最大优先级队列 支持以下操作:

INSERT(S,x):把元素插入集合S;

MAXIMUM(S):返回S中具有最大关键字的元素;

EXTRACT-MAX(S):去掉并返回S中具有的最大关键字的元素;

INCREASE-KEY(S,x,k):将元素x的关键字的值增加到k,这里k值不能小于x的原关键字的值。

最大优先级队列的一个应用:分式计算机上进行作业调度。

最小优先级队列支持的操作包括:INSERT,MINIMUM,EXTRACT-MIN和DECREASE-KEY。

最小优先级队列的一个应用:用在基于事件驱动的模拟器中。

下面是最大优先级队列的具体操作:

MAXIMUM(S)

[code lang=”java”]public static int maximum(){ return A[0]; }[/code]

直接返回队列最大关键字,时间复杂度O(1)。

EXTRACT-MAX(S)

[code lang=”java”]public static int extractMax(){ if(heapSize < 0){ System.out.println("heap underflow"); } int max = A[0]; A[0] = A[heapSize - 1]; heapSize–; maxHeapify(0, heapSize); return max; }[/code]

除少量固定工作外,调用maxHeapify函数,时间复杂度为O(nlgn)。

INCREASE-KEY(S,x,k)

[code lang=”java”]public static void heapIncreaseKey(int i, int key){ if(key < A[i]){ System.out.println("new key is smaller than current key"); } A[i] = key; int parent = parent(i); while(i > 0 && A[parent] < A[i]){ int temp = A[i]; A[i] = A[parent]; A[parent] = temp; i = parent; parent = parent(i); } }[/code]

INCREASE-KEY过程将要更新的元素值更新为新值,然后将更新的节点不断向其父节点移动,直到满足最大堆性质。时间复杂度为O(lgn)。

INSERT(S,x)

[code lang=”java”]public static void insert(int key){ heapSize++; int[] B = new int[A.length + 1]; System.out.println(); for(int j = 0; j < A.length; j++){ B[j] = A[j]; } A = B; A[heapSize - 1] = Integer.MIN_VALUE; heapIncreaseKey(heapSize - 1, key); }[/code]

INSERT过程首先在堆尾增加一个关键字值为负无穷的叶节点,然后调用INCREASE-KEY将值改为正确值。时间复杂度为O(lgn)。

测试代码:

[code lang=”java”]public class PriorityQueue extends HeapSort{ private static int heapSize = A.length; public static void main(String[] args){ buildMaxHeap(); for(int i : A){ System.out.print(i + ","); } System.out.print("\n"); System.out.println("Max: " + maximum()); heapIncreaseKey(6, 8); System.out.println("Increase key: "); for(int i : A){ System.out.print(i + ","); } insert(12); System.out.println("Insert key: "); for(int i : A){ System.out.print(i + ","); } } }[/code]

Published: 28 Aug 2011

堆排序

堆排序(heapsort)兼有插入排序和合并排序的特点。类似于合并排序:它的运行时间是O(nlgn);类似于插入排序,它是一种原地排序算法:在任何时候,数组中只有常数个元素存储在输入数组意外。堆排序将插入排序和合并排序的优点结合起来。

堆数据结构是一种数组对象,可以被视为一棵完全二叉树。数的每一层都是填满的,最后一层可能除外。

表示堆的数组A是一个具有两个属性的对象:length[A]是数组中的元素个数,heap-size[A]是存放在A中的堆的元素个数。即A[heap-size[A]]之后的元素都不属于相应的堆,此处heap-size[A]<=length[A]。

数的根为A[1],给定某个节点下标i,父节点和左右儿子的关系为:

PARENT(i) = floor(i/2);

LEFT(i) = 2i;

RIGHT(i) = 2i + 1;

二叉堆有两种,最大堆:堆中某个结点的值之多和其父节点一样大;最小堆:堆中某个结点的值一定不小于父节点。堆排序算法中使用最大堆,最小堆通常在构造优先队列时使用。

堆结构上的基本操作和运行时间:

MAX-HEAPIFY:O(lgn),保持最大堆性质

BUILD-MAX-HEAP:以线性时间运行,在无序的输入数组基础上构造出最大堆

HEAPSORT:运行时间为O(nlgn),对一个数组进行原地排序

保持堆的性质MAX-HEAPIFY

对输入数组A和下标i,假定LEFT[i]和RIGHT[i]为根的两颗子树都是最大堆,但A[i]可能小于其子女,违反了最大堆性质。MAX-HEAPIFY用于调整A[i]的位置,使以i为根的子树成为最大堆。

MAX-HEAPIFY的基本方法是,从A[i],A[Left[i]]和A[Right[i]]中找出最大的,如果A[i]最大,则堆已经是最大堆;否则将i结点值和最大的子节点值交换,再对交换过的结点为根的子树递归调用MAX-HEAPIFY。

MAX-HEAPIFY的时间复杂度是O(lgn),即对一个高度为h的结点所需的运行时间为O(h)。

建堆BUILD-MAX_HEAP

建堆过程:自底向上地将一个数组A[1..n]变成一个最大堆。

子数组A[(floor(n/2)..n]都是叶子节点,BUILD-MAX_HEAP过程对堆中的非叶子节点有调用一次MAX-HEAPIFY。

BUILD-MAX_HEAP的时间复杂度是O(n)。

堆排序算法HEAPSORT

堆排序算法的过程:

1.用BUILD-MAX_HEAP将数组A[1..n]构造成一个最大堆;

2.交换数组中最大元素A[1]和A[n],并将堆中结点n去掉(减小heap-size[A]);

3.对A[1..n-1]调用MAX-HEAPIFY使其恢复为最大堆;

4.重复2-3步骤(此时n将为n-1)。

HEAPSORT过程的时间代价是O(nlgn)。

完整的java版堆排序代码如下:

[code lang=”java”]public class HeapSort{

private static int[] A = {3, 2, 6, 1, 9, 7, 8, 5, 4};

public static int left(int i){
	//数组下标从0开始,此处有调整
	return 2 * i + 1;
}

public static int right(int i){
	//数组下标从0开始,此处有调整
	return 2 * i + 2;
}

public static int parent(int i){
	return (int)Math.floor(i / 2 );
}

public static void maxHeapify(int i, int heapSize){
	int l = left(i);
	int r = right(i);
	int largest = 0;
	if(l &lt; heapSize &amp;&amp; A[l] &gt; A[i]){
		largest = l;
	}else{
		largest = i;
	}
	if(r &lt; heapSize &amp;&amp; A[r] &gt; A[largest]){
		largest = r;
	}
	if(largest != i){
		int temp = A[largest];
		A[largest] = A[i];
		A[i] = temp;
		maxHeapify(largest, heapSize);
	}else{
		return;
	}
}

public static void buildMaxHeap(){
	int heapSize = A.length;
	for(int i = (int)Math.floor(heapSize / 2) - 1; i &gt;= 0; i--){
		maxHeapify(i, heapSize);
	}
}

public static void heapSort(){
	buildMaxHeap();
	int heapSize = A.length;
	for(int i = A.length - 1; i &gt;0; i--){
		int temp = A[i];
		A[i] = A[0];
		A[0] = temp;
		heapSize--;
		maxHeapify(0, heapSize);
	}
}

public static void main(String[] args){
	for(int i : A){
		System.out.print(i + &quot;,&quot;);
	}
	System.out.print(&quot;\n&quot;);
	heapSort();
	for(int i : A){
		System.out.print(i + &quot;,&quot;);
	}
} }[/code]

Published: 24 Aug 2011