排序算法的比较

无聊的时候就想测测java中排序算法的性能。

 

当然，性能也和实现有关系。所以不能绝对的看结果。同样的排序算法，很多牛人写的性能就要更好些，我的就差很多。

 

这里我比较了两种排序算法：插入排序和分治排序

 

首先先看插入排序算法。实现如下：

 

描述：假设i元素之前的元素已经是有序的，现在用i和之前的元素比较，找到适当的位置插入，将i之前的其他元素后移。

 

	public static int[] insertSorter(int[] values) {
		for (int i = 1; i < values.length; i++) {
			int tmp = values[i];
			int j;
			for (j = i; j > 0 && values[j - 1] > tmp; j--) {
				values[j] = values[j - 1];
			}
			values[j] = tmp;
		}
		return values;
	}

 

然后看看分治排序。分两种方式：递归和非递归。

 

递归描述：把递归的把待排序数组分成两组，分别排序，然后再按序组合。

	//分治法，递归
                public static int[] recursionDimSorter(int[] values) {
		return recursionDimSorter(values, 0, values.length);
	}
                
	private static int[] recursionDimSorter(int[] values, int startIndex,
			int endIndex) {
		if (endIndex - startIndex == 1) {
			return values;
		}
		int middle = startIndex + (endIndex - startIndex) / 2;
		recursionDimSorter(values, startIndex, middle);
		recursionDimSorter(values, middle, endIndex);
		return mergeArrays(values, startIndex, endIndex, middle);
	}

                //合并已经排序的前后两组
	private static int[] mergeArrays(int[] values, int startIndex,
			int endIndex, int middleIndex) {
		// check index
		if (middleIndex < startIndex || middleIndex > endIndex
				|| values.length <= startIndex || values.length < endIndex
				|| startIndex < 0 || endIndex < 0 || middleIndex < 0) {
			throw new ArrayIndexOutOfBoundsException();
		}

		//merge
		int[] first = new int[middleIndex - startIndex];
		int[] second = new int[endIndex - middleIndex];
		System.arraycopy(values, startIndex, first, 0, first.length);
		System.arraycopy(values, middleIndex, second, 0, second.length);

		for (int i = startIndex, j = 0, k = 0; i < endIndex; i++) {
			if (k == second.length) {
				System.arraycopy(first, j, values, i, first.length - j);
				break;
			} else if (j == first.length) {
				System.arraycopy(second, k, values, i, second.length - k);
				break;
			}
			values[i] = first[j] > second[k] ? second[k++] : first[j++];
		}
		return values;
	}

 

 

非递归描述：递归的反思路：先两两一组比较，再四四一组比较，以此向上。

 

	public static int[] unrecursionDimSorter(int[] values) {
		int step = 1;
		while (step < values.length) {
			step *= 2;
			for (int i = 0; i < values.length; i += step) {
				int endIndex = i + step >= values.length ? values.length : i
						+ step;
				int middleIndex = i + step / 2 >= values.length ? values.length - 1
						: i + step / 2;
				values = mergeArrays(values, i, endIndex, middleIndex);
			}
		}
		return values;
	}

 这里使用step去描述步调。一开始是一一比，然后合成二；然后二二比合成四；。。。；以此类推。

 

最后我们看一下对比结果（这里数组都是通过随机数产生的）：

 

先看一个小数组，数量级只有100：

 

start recursion
    unsorted:2079873
    sorted:    175162
start unrecursion
    unsorted:930565
    sorted:    46096
start insert
    unsorted:91353
    sorted:    345575

 这里我都只运行了一次，所以可能结果不太能说明问题。不过总体上来说此时无序和有序，插件排序表现都很好；递归分治在两种情况下表现都较差。

 

再看一个大数组，数组级为10万：

 

start recursion
         unsored:234316652
         sorted:   157530357
start unrecursion
         unsored:214810541
         sorted:   158534674
start insert
         unsored:152853701518
         sorted:   3797131

 

可以看到，分治法表现比较好，很快就完成了运算，而插件法去慢得多，从结果看，多出了三个数量级。不过在有序的情况下刚表现最为出色。