问题描述
我看看几篇排序的算法的文章,大家都说效率一般都是:快速排序>归并排序>希尔排序然后就用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++];elseresult[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
解决方案
排序效率根本就不能单纯的说哪种比哪种高吧，建议看看算法导论
解决方案二：
网上的文章有很多都是抄袭的，靠不住看算法的性能 通过两方面，时间复杂度、稳定性比如说快速排序的时间复杂度平均为O(nlogn) 快排不稳定归并的时间复杂度 为O(nlogn) jdk里面用的就是归并，稳定shell排序为o（n^1.25）你这里主要是在方法里new 了太多的数组，在递归的时候导致OOM具体的你可以通过维基百科上面看
解决方案三：
因为你的数据量太大40万条，当数据量很大时快速排序就不是最快的了。而且排序应该用一个数组
