为什么我的选择排序比插入排序快?

2019-07-02 15:24:14 +08:00
 yusuzhan

刚刚开刷红宝书,好奇测了一下发现 Java 实现的选择排序比插入排序速度快,个人推测是 JVM 上交换位置操作比对比操作消耗大。 当然还是担心是我自己粗心导致的,请大家帮忙看下, tldr 的可以直接看最后面的运行结果。

选择排序

public static void sort(Comparable[] a) {
        int min = 0;
        for (int i = 0; i < a.length; i++) {
            min = i;
            for (int j = i + 1; j < a.length; j++) {
                if (less(a[j], a[min])) {
                    min = j;
                }                
            }
            exch(a, i, min);
        }
    }

插入排序

public static void sort(Comparable[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = i + 1; j > 0; j--) {                
                if (less(a[j], a[j-1])) {                    
                    exch(a, j, j - 1);
                } else {
                    break; 
                }                                    
            }            
        }
    }

性能对比

public static void timeTest(int n, int repeat) {
        double selectionSortTime = 0;        
        long compareInSelection = 0;
        long swapInSelection = 0;

        double bubbleSortTime = 0;
        
        double insertionSortTime = 0;
        long compareInInsertion = 0;
        long swapInInsertion = 0;

        for (int i = 0; i < repeat; i++) {
            Integer[] arr0 = genRandomArray(n);        
            Integer[] arr1 = copyArray(arr0);
            Integer[] arr2 = copyArray(arr0);

            Stopwatch stopwatch0 = new Stopwatch();            
            SelectionSort.sort(arr0);
            selectionSortTime += stopwatch0.elapsedTime();
            compareInSelection += SelectionSort.compare;
            swapInSelection += SelectionSort.swap;

            Stopwatch stopwatch1 = new Stopwatch();            
            BubbleSort.sort(arr1);
            bubbleSortTime += stopwatch1.elapsedTime();

            Stopwatch stopwatch2 = new Stopwatch();            
            InsertionSort.sort(arr2);
            insertionSortTime += stopwatch2.elapsedTime();
            compareInInsertion += InsertionSort.compare;
            swapInInsertion += InsertionSort.swap;
        }
        StdOut.printf("algorithm        avg    compare    swap\n");
        StdOut.printf("SelectionSort    %f  %d  %d\n", selectionSortTime / repeat, compareInSelection / repeat, swapInSelection / repeat);
        StdOut.printf("BubbleSort       %f  \n", bubbleSortTime / repeat);
        StdOut.printf("InsertionSort    %f  %d  %d\n", insertionSortTime / repeat, compareInInsertion / repeat, swapInInsertion / repeat);
    }

打印结果

algorithm        avg    compare    swap
SelectionSort    0.001032  499500  1000
BubbleSort       0.001788  
InsertionSort    0.001293  250824  249831
3605 次点击
所在节点    程序员
20 条回复
davie
2019-07-02 15:27:43 +08:00
数据量多大?
yusuzhan
2019-07-02 15:28:58 +08:00
@davie 数组长度 1000,repeat 5000 次测平均值
davie
2019-07-02 15:42:00 +08:00
随机性呢?
yusuzhan
2019-07-02 15:50:58 +08:00
@davie 随机性用的红宝书里提供的库,描述是 uniformly

```
/**
* Rearranges the elements of the specified array in uniformly random order.
*
* @param a the array to shuffle
* @throws IllegalArgumentException if {@code a} is {@code null}
*/
public static void shuffle(Object[] a) {
validateNotNull(a);
int n = a.length;
for (int i = 0; i < n; i++) {
int r = i + uniform(n-i); // between i and n-1
Object temp = a[i];
a[i] = a[r];
a[r] = temp;
}
}
```
yusuzhan
2019-07-02 15:52:18 +08:00
@davie 在我的电脑上,临界点是 270,超过这个超度的数组,都是选择快
AmmeLid
2019-07-02 15:53:16 +08:00
用数组来做插入排序,还要考虑插入后数据移动的开销吧。
wutiantong
2019-07-02 16:00:32 +08:00
很可能是 exch 引入了额外的开销
yusuzhan
2019-07-02 16:03:55 +08:00
@wutiantong 真没啥,书里原文

```
private static void exch(Comparable[] a, int i, int j) {
swap++;
final Comparable swap = a[i];
a[i] = a[j];
a[j] = swap;
}
```
xuwei0056
2019-07-02 16:07:19 +08:00
创建 Comparable 的开销大?
jmc891205
2019-07-02 16:08:10 +08:00
你再测一下 less 和 exch 的速度好了
wutiantong
2019-07-02 16:14:53 +08:00
@yusuzhan 排序算法的性能评估只看比较操作(less)的次数,交换操作(exch)则应尽量降低影响。

你的这个 exch 恐怕比 less 还要慢一丢丢。
lance6716
2019-07-02 16:19:54 +08:00
我咋记得插入排序不是这么写…一个一个往后移,而不是交换
yusuzhan
2019-07-02 16:30:19 +08:00
@jmc891205 @wutiantong
测了一下,exch 速度确实慢很多

compareTime = 0.006
exchTime = 1.306
yusuzhan
2019-07-02 16:31:42 +08:00
@xuwei0056 用的 Integer 数组,创建的开销没算, 只统计的排序的速度。刚才看了一下, 确实是 exch 速度比 less 慢导致的。
wizardoz
2019-07-02 17:24:27 +08:00
选择排序移动很少,插入排序有很多移动
算法书上的时间复杂度是以比较次数来计的。
littlewing
2019-07-03 02:27:39 +08:00
复杂度低并不代表任何情况下速度就快,因为复杂度算得是极限
capljf
2019-12-12 19:53:46 +08:00
我的 mac pro 上也是选择排序比插入排序快,100 ~ 10000 个 double 随机数,用 StdRandom.shuffle 打乱了。100 ~ 10000 次都试了,都是选择比插入快。搞得我检查了好几遍代码是不是写反了,但代码确实没问题。还得继续找原因
capljf
2019-12-12 19:58:26 +08:00
我猜是插入排序没有做优化,因为每次比较都做了 exch,exch 比较耗时,我去按书上的优化一下,将较大元素都往右移动而不是总是 exch。访问数组的次数能减少一半
capljf
2019-12-12 21:07:28 +08:00
为啥回复不了了,提示验证手机号
capljf
2019-12-12 21:10:17 +08:00
好像我的回复有些词被 block 了。简单说下,刚刚是我的代码写得有问题,插入是比选择快的,优化后的代码 swap 次数确实比优化前少一半左右

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/579314

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX