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;
				}
			}
		}
	}

发表评论

电子邮件地址不会被公开。 必填项已用*标注