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

Question

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

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

 运行结果如下:

 

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

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

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

Answer 1

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

Answer 2

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