归并排序

归并排序与其他简单排序的不同之处在于它用到了分治思想。即把一个大的问题分解为一个个小的问题。 通过求解小问题来解决大问题。在归并排序中,分治体现在它是先把一个个小的序列排好, 然后在将这些排好的小序列合并起来。归并的代码也用到了一个辅助辅助函数, 基本上高级的排序方法都会有自己的辅助函数。具体代码如下:

public static void MergeSort(List<Integer> list, int low, int high) {
	if (high <= low)
		return;
	int mid = (low + high) / 2;
	MergeSort(list, low, mid);
	MergeSort(list, mid+1, high);
	merge(list, low, mid, high);
}

public static void merge(List<Integer> list, int low, int mid, int high) {
	int[] aux = new int[list.size()];
	int i = low, j = mid + 1;
	for (int k = low; k <= high; k++) {
		aux[k] = list.get(k);
	}

	for (int k = low; k <= high; k++) {
		if (i > mid) {
			// 左边用完
			list.set(k, aux[j++]);
		} else if (j > high) {
			// 右边用完
			list.set(k, aux[i++]);
		} else if (aux[j] < aux[i]) {
			// j对应的较小,先放j,然后j后移
			list.set(k, aux[j++]);
		} else {
			list.set(k, aux[i++]);
		}
	}
}

首先需要注意等是在merge中,对list进行备份时,并不是全部备份,而是从low到high的一个局部备份。 然后在for循环里面,i和j都是累加,i是从low开始往mid走,j是从mid+1开始往high走, 它们的终止条件都是小于目的位置。然后每次放置完哪个,哪个就要向后移动。
还有就是递归的程序需要注意的一点就是退出条件,在归并排序中,就是MergeSort中的前两行代码。

快速排序

一个排序算法得有多快才能让它的名字就叫做快速排序呢? 可以参考这篇文章来看看快排为什么那样快。 快排也是分治的算法,与归并不同的是,快排是先分割,然后排序。而归并是先排序,然后归并,提现在代码上就是sort方法的位置:

public static void QuickSort(List<Integer> list, int low, int high) {
	if (low >= high)
		return;
	int mid = partition(list, low, high);
	QuickSort(list, low, mid - 1);
	QuickSort(list, mid + 1, high);
}

public static int partition(List<Integer> list, int low, int high) {
	int i = low, j = high + 1;
	int value = list.get(low);
	while (true) {
		while (list.get(++i) < value) {
			if (i == high)
				break;
		}
		while (list.get(--j) > value) {
			if (j == low)
				break;
		}
		if (i >= j)
			break;
		exchange(list, i, j);
	}
	exchange(list, low, j);
	return j;
}

快排需要注意有内层的两个while循环和进入partition之后的high + 1,这里之所以需要加一, 是因为在内层的两个循环之中,是先减一之后才进行的比较。 快排的重点是partition函数,在内部的两个while循环中,是分别从前往后找比value大的, 和从后往前找比value小的,然后交换他们。之前在数据结构课上,每一个while循环之后, 都要exchang,但是这种方法显然没有上面的代码的简洁且高效,因为它只有一次交换操作。 现在回过头来想,教科书里的两次交换真的没有意义多此一举。



blog comments powered by Disqus

Published

13 September 2015

Category

tech_world

Tags