测试排序的效率,为什么:希尔排序>归并排序>快速排序?

0 0

测试排序的效率,为什么:希尔排序>归并排序>快速排序?20

我看看几篇排序的算法的文章,大家都说效率一般都是:快速排序>归并排序>希尔排序

然后就用java自己动手测了一下,测试结果却是:希尔排序>归并排序>快速排序

而且当数据量过大时,归并排序和快速排序会出现栈溢出.

以下是我写的源代码,请帮我分析一下是什么原因?

package com.test;

import java.util.Arrays;
import java.util.Random;

public class Sort {
	public static void main(String[] args) {
		int[] arr = new int[400000];
		Random r = new Random();

		long start, end;

		init(arr, r);
		System.out.print("希尔排序...");
		start = System.currentTimeMillis();
		sort1(arr);
		end = System.currentTimeMillis();
		System.out.println("完成" + (end - start));
		//System.out.println(Arrays.toString(arr));

		init(arr, r);
		System.out.print("归并排序...");
		start = System.currentTimeMillis();
		arr = sort2(arr, 0, arr.length - 1);
		end = System.currentTimeMillis();
		System.out.println("完成" + (end - start));
		//System.out.println(Arrays.toString(arr));

		init(arr, r);
		System.out.print("快速排序...");
		start = System.currentTimeMillis();
		sort3(arr, 0, arr.length - 1);
		end = System.currentTimeMillis();
		System.out.println("完成" + (end - start));
		//System.out.println(Arrays.toString(arr));

	}

	/**
	 * 初始化
	 */
	private static void init(int[] arr, Random r) {
		System.out.print("\n初始化...");
		for (int i = 0; i < arr.length; i++) {
			arr[i] = r.nextInt(100);
		}
		//System.out.println("\n" + Arrays.toString(arr));
	}

	/**
	 * 希尔排序
	 */
	private static void sort1(int[] a) {
		int i, j, temp, increment;
		// increment增量缩短，当增量为1时，即把整个数组进行插入排序
		for (increment = a.length / 3; increment > 0; increment /= 3) {
			for (i = increment; i < a.length; i++) {
				temp = a[i];
				for (j = i - increment; j >= 0 && temp < a[j]; j -= increment) {
					a[j + increment] = a[j];
				}
				a[j + increment] = temp;
			}

		}
	}

	/**
	 * 归并排序
	 * left,right参数表示:把a数组中fist--right之间的元素排序
	 * 排序结果以新数组返回.
	 */
	private static int[] sort2(int[] a, int left, int right) {
			//判断递归结束条件
			if (right <= left) return new int[] { a[left] };
			
			//从数组中间切成左右两部分,mid为右边部分的起始下标
			int mid = (left + right + 1) / 2;
			//第一步:用递归把数组左边排序
			int[] a1 = sort2(a, left, mid - 1);
			//第二步:用递归把数组右边排序
			int[] a2 = sort2(a, mid, right);
			
			//第三步:归并操作,把左右两边序列合并到新的数组
			int[] result = new int[right - left + 1];
			int i = 0, j = 0, k = 0;
			while (i < a1.length && j < a2.length) {
				if (a1[i] < a2[j])
					result[k++] = a1[i++];
				else
					result[k++] = a2[j++];
			}
			while (j < a2.length) {
				result[k++] = a2[j++];
			}
			while (i < a1.length) {
				result[k++] = a1[i++];
			}
			return result;
	}

	/**
	 * 快速排序
	 * left,right参数表示:把a数组中left--right之间的元素排序
	 */
	private static void sort3(int[] a, int left, int right) {
		// 第四步:判断结束递归的条件
		if(left>=right) return;
		
		// 第一步:以left为基数,把a分成左右两部分,使左边部分小于右边部分
		int i = left;//最终i==j;
		for (int b=1,j=right; i < j;) {// 最初b=1,表示以left为基数
			if (a[i] > a[j]) {//交换位置
				int temp = a[i];
				a[i] = a[j];
				a[j] = temp;
				if (b==1) i++; else j--;//应基数位置不同,处理也不同
				b = -b;//交换位置后,基数位置变化,b=1,表示以left为基数
			} else {
				if (b==1) j--; else i++;//应基数位置不同,处理也不同
			}
		}
		// 第二步:递归排序左部分(left到i-1)
		sort3(a,left,i-1);
		// 第三步:递归排序右部分(i+1到right)
		sort3(a,i+1,right);
	}
}

运行结果如下:

初始化...希尔排序...完成40

初始化...归并排序...完成53

初始化...快速排序...完成1411

Java 排序

2012年5月26日 15:14

bits00
14
0 0 1

3个答案按时间排序按投票排序

0 0

采纳的答案

排序效率根本就不能单纯的说哪种比哪种高吧，建议看看算法导论

2012年5月31日 18:05

lee1177
57
0 0 4

添加评论

0 0

网上的文章有很多都是抄袭的，靠不住
看算法的性能通过两方面，时间复杂度、稳定性

比如说快速排序的时间复杂度平均为O(nlogn) 快排不稳定

归并的时间复杂度为O(nlogn) jdk里面用的就是归并，稳定

shell排序为o（n^1.25）

你这里主要是在方法里new 了太多的数组，在递归的时候导致OOM

具体的你可以通过维基百科上面看

2012年5月28日 12:50