我看看几篇排序的算法的文章,大家都说效率一般都是:快速排序>归并排序>希尔排序
然后就用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
初始化...归并排序...完成53
初始化...快速排序...完成1411