Java实现归并排序(MergeSort)

/**	归并排序Java实现
 *	MertSort using Java
 * 	by puladiao
 * 	http://blog.verypod.com
 */
class MergeSorter {
	private int nElems;
	private int[] theArray, workSpace;

	public MergeSorter(int[] theArray) {
		nElems = theArray.length;
		this.theArray = theArray;
	}

	public void MergeSort() {
		workSpace = new int[nElems];
		recMergeSort(0, nElems - 1);
	}

	private void recMergeSort(int lowerBound, int upperBound) {
		if (lowerBound == upperBound) {
			return;
		} else {
			int mid = (lowerBound + upperBound) / 2;
			recMergeSort(lowerBound, mid);
			recMergeSort(mid + 1, upperBound);
			merge(lowerBound, mid, upperBound);
		}
	}

	private void merge(int lowerBound, int mid, int upperBound) {
		int leftIndex, rightIndex, index;
		leftIndex = lowerBound;
		index = lowerBound;
		rightIndex = mid + 1;
		while (leftIndex <= mid && rightIndex <= upperBound) {
			if (theArray[leftIndex] < theArray[rightIndex]) {
				workSpace[index++] = theArray[leftIndex++];
			} else {
				workSpace[index++] = theArray[rightIndex++];
			}
		}
		while (leftIndex <= mid) {
			workSpace[index++] = theArray[leftIndex++];
		}
		while (rightIndex <= upperBound) {
			workSpace[index++] = theArray[rightIndex++];
		}
		for (int i = lowerBound; i <= upperBound; i++) {
			theArray[i] = workSpace[i];
		}
	}

	public void display() {
		for (int i = 0; i < nElems; i++) {
			System.out.print(theArray[i] + " ");
		}
		System.out.println("");
	}
}

public class MergeSortApp {
	public static void main(String[] args) {
		int[] arr = new int[] { 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		MergeSorter ms = new MergeSorter(arr);
		ms.display();
		ms.MergeSort();
		ms.display();
	}
}

Java数据结构和算法(第二版)第三章编程

/**	Java数据结构和算法(第二版)第三章 编程作业
/**	Programming Projects for Chapter 3 Simple Sorting, Data Structure & Algorithms in Java 2nd Edition
 * 	by puladiao
 * 	http://blog.verypod.com
 */
// 编程作业3.1
	public void bubbleSort() {
		int out_r, out_l, in;
		out_l = 0;

		for (out_r = nElems - 1; out_r > out_l; out_r--) {
			for (in = out_l; in < out_r; in++)
				if (a[in] > a[in + 1])
					swap(in, in + 1);
			for (in = out_r - 1; in > out_l; in--)
				if (a[in] < a[in - 1])
					swap(in - 1, in);
			out_l++;
			System.out.println(out_r + " " + out_l);
		}
	}
// 编程作业3.2
	public long median() {
		insertionSort();
		return a[(nElems - 1) / 2];
	}
// 编程作业3.3
	public void noDups() {
		insertionSort();
		int dupNum = 0;// 记录重复个数
		for (int i = 0; i < nElems; i++) {
			if (a[i] == a[i + dupNum + 1]) {
				dupNum++;
				nElems--;
			}
			if (dupNum>0){
				a[i + 1] = a[i + dupNum + 1];
			}
		}
	}
// 编程作业3.4
	public void oddEvenSort() {
		//待排序数组项目为奇数个或偶数个时分别对两个for循环进行控制,防止超出数组下标边界
		int factor1, factor2;
		if (nElems % 2 == 0) {
			factor1 = 0;
			factor2 = 1;
		} else {
			factor1 = 1;
			factor2 = 0;
		}
		boolean sorted = false;
		while (!sorted) {
			sorted = true;
			for (int i = 0; i < nElems - 1 - factor1; i += 2) {
				if (a[i] > a[i + 1]) {
					swap(i, i + 1);
					sorted = false;
				}
			}
			for (int i = 1; i < nElems - 1 - factor2; i += 2) {
				if (a[i] > a[i + 1]) {
					swap(i, i + 1);
					sorted = false;
				}
			}
		}
	}

Java实现冒泡排序、插入排序和选择排序

/**	冒泡排序、插入排序和选择排序的Java实现
 * 	Bubble Sort, Insertion Sort and Selection Sort using Java
 * 	by puladiao
 * 	http://blog.verypod.com
 */
import java.util.Random;

class ArrayBub {
	private int[] a;
	
	public ArrayBub(int num){
		a=new int[num];
		Random r=new Random();
		for (int i=0;i<a.length;i++){
			a[i]=r.nextInt(num);
		}
	}
	//冒泡排序
	public void bubbleSort() {
		int temp;
		for (int i = 0; i < a.length - 1; i++) {
			for (int j = 0; j < a.length - i - 1; j++) {
				if (a[j] > a[j + 1]) {
					temp = a[j + 1];
					a[j + 1] = a[j];
					a[j] = temp;
				}
			}
		}
	}
	//选择排序
	public void selectSort() {
		int temp;
		for (int i = 0; i < a.length - 1; i++) {
			int minIn = i;
			for (int j = i + 1; j < a.length; j++) {
				if (a[minIn] > a[j]) {
					minIn = j;
				}
			}
			temp = a[i];
			a[i] = a[minIn];
			a[minIn] = temp;
		}
	}
	//插入排序
	public void insertionSort() {
		for (int i = 1; i < a.length; i++) {
			int temp = a[i];
			int j = i;
			while (j > 0 && temp < a[j - 1]) {
				a[j] = a[j - 1];
				j--;
			}
			a[j] = temp;
		}
	}
	//输出当前的数组
	public void display()
	{
		for (int j = 0; j < a.length; j++)
			System.out.print(a[j] + " "); 
		System.out.println("");
	}
}

public class SortApp {
	public static void main(String[] args) {
		long start,end;
		//创建一个含有一万随即项的随机数组
		ArrayBub a = new ArrayBub(10000);
		start=System.currentTimeMillis();
		a.selectSort();
		//a.insertionSort();
		//a.bubbleSort();
		end=System.currentTimeMillis();
		//输出排序所用时间,单位为毫秒
		System.out.println(end-start);	
	}
}

可用于插入新元素的Binary Search

/**	Java数据结构和算法(第二版)第二章 编程作业
/**	Programming Projects for Chapter 2 Arrays, Data Structure & Algorithms in Java 2nd Edition
 * 	by puladiao
 * 	http://blog.verypod.com
 */
class OrdArray {
	private long[] a; // ref to array a
	private int nElems; // number of data items

	public OrdArray(int max) // constructor
	{
		a = new long[max]; // create array
		nElems = 0;
	}

	public int size() {
		return nElems;
	}

	public void insert(long value) // put element into array
	{
		int j = findIndex(value);
		display();
		for (int k = nElems; k > j; k--)
			// move bigger ones up
			a[k] = a[k - 1];
		a[j] = value; // insert it
		nElems++; // increment size
	}

	public int findIndex(long value) {
		int lowerBound = 0;
		int upperBound = nElems - 1;
		int currentIndex = 0;

		if (nElems == 0) {
			return 0;
		} else if (nElems == 1) {
			if (value > a[0])
				return 1;
			else
				return 0;
		}

		while (true) {
			currentIndex = (lowerBound + upperBound) / 2;
			if (a[currentIndex] == value) {
				return currentIndex;
			} else if (lowerBound == upperBound - 1 || lowerBound==upperBound) {
				if (value < a[lowerBound])
					return lowerBound;
				else
					return upperBound;
			} else if (a[currentIndex] < value) {
				lowerBound = currentIndex + 1;
			} else {
				upperBound = currentIndex - 1;
			}
		}
	}

	public boolean delete(long value) {
		int j = find(value);
		if (j == nElems) // can't find it
			return false;
		else // found it
		{
			for (int k = j; k < nElems; k++)
				// move bigger ones down
				a[k] = a[k + 1];
			nElems--; // decrement size
			return true;
		}
	}

	public void display() // displays array contents
	{
		for (int j = 0; j < nElems; j++)
			// for each element,
			System.out.print(a[j] + " "); // display it
		System.out.println("");
	}

} 

WordPress 博客文章内容取消自动转义

默认情况下,WordPress 博客对字符会自动转义,如文章里的教程中涉及到代码时,半角引号会变全角,如此要使用的博客复制代码添加到自己的博客后没有效果或者出现相关错误,因此大部分博主选择了代码高亮插件。但也可以通过非插件的方法取消WP字符自动转义的问题。

WordPress 取消字符自动转义:

  1. 登陆博客后台,点击“外观”选项卡下的“编辑”选项进入当前主题编辑界面
  2. 选择functions.php文件进行编辑操作
  3. 在<?php和?>之间添加以下代码
remove_filter('the_content', 'wptexturize');

ipc.Client: Retrying connect to server错误解决方案

运行Hadoop: The Definitive Guide 2nd Ediction第51页的例子里面的例子出现了如下错误:

  • 12/01/10 16:29:32 INFO ipc.Client: Retrying connect to server: localhost/127.0.0.1:9000. Already tried 0 time(s).
  • 12/01/10 16:29:33 INFO ipc.Client: Retrying connect to server: localhost/127.0.0.1:9000. Already tried 1 time(s).
  • 12/01/10 16:29:34 INFO ipc.Client: Retrying connect to server: localhost/127.0.0.1:9000. Already tried 2 time(s).
  • 12/01/10 16:29:35 INFO ipc.Client: Retrying connect to server: localhost/127.0.0.1:9000. Already tried 3 time(s).
  • 12/01/10 16:29:36 INFO ipc.Client: Retrying connect to server: localhost/127.0.0.1:9000. Already tried 4 time(s).
  • 12/01/10 16:29:37 INFO ipc.Client: Retrying connect to server: localhost/127.0.0.1:9000. Already tried 5 time(s).
  • 12/01/10 16:29:38 INFO ipc.Client: Retrying connect to server: localhost/127.0.0.1:9000. Already tried 6 time(s).
  • 12/01/10 16:29:39 INFO ipc.Client: Retrying connect to server: localhost/127.0.0.1:9000. Already tried 7 time(s).
  • 12/01/10 16:29:40 INFO ipc.Client: Retrying connect to server: localhost/127.0.0.1:9000. Already tried 8 time(s).
  • 12/01/10 16:29:41 INFO ipc.Client: Retrying connect to server: localhost/127.0.0.1:9000. Already tried 9 time(s).

解决方案:

在命令行使用ifconfig查看本机IP,然后进入conf/core-site.xml将hdfs://localhost:9000改为hdfs://你的IP地址:9000

<?xml version="1.0"?>
<?xml-stylesheet type="text/xsl" href="configuration.xsl"?>

<!-- Put site-specific property overrides in this file. -->

<configuration>
     <property>
         <name>fs.default.name</name>
         <value>hdfs://192.168.1.101:9000</value>
     </property>
</configuration>

编译Hadoop的WordCount例子错误解决方案

错误提示:

  • 无法访问 org.apache.commons.cli.Options
  • 未找到 org.apache.commons.cli.Options 的类文件
  •  String[] otherArgs = new GenericOptionsParser(conf, args).getRemainingArgs();

解决方案:

这是因为编译的时候缺少了lib/commons-cli-1.2.jar,所以只要添加这个jar就可以了,两个jar之间用冒号:,命令如下,其中playground/src/WordCount.java为你的WordCount.java的路径

javac -classpath hadoop-core-0.20.204.0.jar:lib/commons-cli-1.2.jar \
playground/src/WordCount.java -d playground/classes

启动Hadoop后没有Datanode

错误提示:

  • There are no datanodes in the cluster
  • Error Recovery for block null bad datanode[0] nodes == null….could only be replicated to 0nodes,instread of 1

系统类型:

  • Ubuntu 10.10

解决方法:

问题就在于ubuntu10.10每次开机后会在/etc/hosts自动生成一行代码:127.0.0.1 localhost localhost.local,而ubuntu10.04版本则不会。在hadoop中,由于127.0.0.1与主机绑定,导致datanode一直 试图链接namenode而连接不上,只要开机后把/etc/hosts 下的127.0.0.1 localhost localhost.local删除即可,如果找不到这一行,就删除写着Network Manager的那一行。
所以ubuntu10.10的hadoop用户注意了,有可能就是这个问题导致的启动hadoop后没有datanodes