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

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

然后就用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

 

 

3个回答

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

因为你的数据量太大40万条,当数据量很大时快速排序就不是最快的了。而且排序应该用一个数组

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

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

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

shell排序为o(n^1.25)

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

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

bits00
bits00 问题有2点 1. 我只是在"归并排序"方法里new了数组,"快速排序"方法里并没有new数组,测试结果中,shell排序与归并运行时间差多,而快速排序的效率明显太低,所以new数组不是根本原因. 2. new数组是在堆空间创建的,当排序的数据量过大时,产生的异常 是: StackOverflowError 而不是OutOfMemoryError.所以导致异常的根本原因是递归层次太多.
8 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐