java排序方法对比,其他排序展示

BSO 2020-09-09 09:09:20 java常见问答 6696

上次已经为大家介绍过java中插入、分治和快速排序的内容以及java中选择排序与归并排序的内容,今天再为大家对比一下java排序的方法,然后再补充一些排序的方法。

首先,我们来比较一下这几种排序的方法。

测试了一下几个排序的速度,代码如下:

public static void main(String[] args)
{
    int[] arr = new int[200000];
    int[] a = getRandomArr(arr);
    int[] b = a.clone();
    int[] c = b.clone();
    int[] d = b.clone();
    int[] e = b.clone();
    int[] f = b.clone();
    int[] g = b.clone();
    int[] h = b.clone();
    long s = Clock.systemDefaultZone()
        .millis();
    quickSort(a, 0, a.length - 1);
    System.out.println("quickSort耗时: " + (Clock.systemDefaultZone()
        .millis() - s) + " ms");
    s = Clock.systemDefaultZone()
        .millis();
    mergeSort(b, 0, b.length - 1);
    System.out.println("mergeSort: " + (Clock.systemDefaultZone()
        .millis() - s) + " ms");
    s = Clock.systemDefaultZone()
        .millis();
    listSort(c);
    System.out.println("listSort耗时: " + (Clock.systemDefaultZone()
        .millis() - s) + " ms");
    s = Clock.systemDefaultZone()
        .millis();
    arraysSort(d);
    System.out.println("arraysSort耗时: " + (Clock.systemDefaultZone()
        .millis() - s) + " ms");
    s = Clock.systemDefaultZone()
        .millis();
    maoPaoSort(e);
    System.out.println("maoPaoSort耗时: " + (Clock.systemDefaultZone()
        .millis() - s) + " ms");
    s = Clock.systemDefaultZone()
        .millis();
    maoPaoSortPlus(f);
    System.out.println("maoPaoSortPlus耗时: " + (Clock.systemDefaultZone()
        .millis() - s) + " ms");
    s = Clock.systemDefaultZone()
        .millis();
    insertSort(g);
    System.out.println("insertSort耗时: " + (Clock.systemDefaultZone()
        .millis() - s) + " ms");
    s = Clock.systemDefaultZone()
        .millis();
    selectSort(h);
    System.out.println("selectSort耗时: " + (Clock.systemDefaultZone()
        .millis() - s) + " ms");
}
/**
 * 获取一个打乱的数组
 * @param arr
 */
private static int[] getRandomArr(int[] arr)
{
    for (int i = 0; i < arr.length; i++)
    {
        arr[i] = new Random()
            .nextInt(arr.length);
    }
    return arr;
}

然后分别对1k,1w,10w,20w大小的随机数组排序,结果如下。

得到综合结果是:

然后是速度排名,从上到下一次是:

1.快速排序

2.归并排序

3.插入排序

4.选择排序

5.冒泡排序

代码如下:

//---1k---
quickSort耗时: 0 ms
mergeSort: 1 ms
listSort耗时: 7 ms
arraysSort耗时: 1 ms
maoPaoSort耗时: 3 ms
maoPaoSortPlus耗时: 4 ms
insertSort耗时: 2 ms
selectSort耗时: 3 ms
//---1w---
quickSort耗时: 2 ms
mergeSort: 3 ms
listSort耗时: 19 ms
arraysSort耗时: 4 ms
maoPaoSort耗时: 166 ms
maoPaoSortPlus耗时: 122 ms
insertSort耗时: 12 ms
selectSort耗时: 52 ms
//---10w---
quickSort耗时: 14 ms
mergeSort: 19 ms
listSort耗时: 65 ms
arraysSort耗时: 12 ms
maoPaoSort耗时: 15242 ms
maoPaoSortPlus耗时: 15044 ms
insertSort耗时: 797 ms
selectSort耗时: 4073 ms
//---20w---
quickSort耗时: 26 ms
mergeSort: 34 ms
listSort耗时: 102 ms
arraysSort耗时: 60 ms
maoPaoSort耗时: 60811 ms
maoPaoSortPlus耗时: 60378 ms
insertSort耗时: 3279 ms
selectSort耗时: 15762 ms

并且由上可知,选择排序和冒泡排序在数据量越来越大的情况下,耗时是呈指数型上涨,而不是倍数上涨,在50w的时候已经需要足足5分钟以上。

再补充一些其他排序的例子。

比如说,Arrays工具类提供的排序方法。它内部实现也是快速排序,代码展示如下:

private static void arraysSort(int[] a)
{
    Arrays.sort(a);
}

另外就是将数组转为list,使用集合的排序方法,但是这无异于兜圈子,因为集合底层也是数组,代码展示如下:

private static void listSort(int[] a)
{
    List < Integer > integers = Ints.asList(a);
    Collections.sort(integers);
    integers.toArray(new Integer[a.length]);
}

以上就是关于java排序方法对比,并且展示了一些其他的排序方式。如果你对java知识感兴趣,想要了解更多java经典例子,敬请关注奇Q工具网。

推荐阅读:

java中对象排序的概念是什么?实例代码展示

java集合排序该如何实现?

java中冒泡排序低级版与高级版对比,实例展示