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

[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

[davie]

数据量多大？

[yusuzhan]

@davie 数组长度 1000，repeat 5000 次测平均值

[davie]

随机性呢？

[yusuzhan]

@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]

@davie 在我的电脑上，临界点是 270，超过这个超度的数组，都是选择快

[AmmeLid]

用数组来做插入排序，还要考虑插入后数据移动的开销吧。

[wutiantong]

很可能是 exch 引入了额外的开销

[yusuzhan]

@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]

创建 Comparable 的开销大？

[jmc891205]

你再测一下 less 和 exch 的速度好了

[wutiantong]

@yusuzhan 排序算法的性能评估只看比较操作(less)的次数，交换操作(exch)则应尽量降低影响。

你的这个 exch 恐怕比 less 还要慢一丢丢。

[lance6716]

我咋记得插入排序不是这么写…一个一个往后移，而不是交换

[yusuzhan]

@jmc891205 @wutiantong
测了一下，exch 速度确实慢很多

compareTime = 0.006
exchTime = 1.306

[yusuzhan]

@xuwei0056 用的 Integer 数组，创建的开销没算， 只统计的排序的速度。刚才看了一下， 确实是 exch 速度比 less 慢导致的。

[wizardoz]

选择排序移动很少，插入排序有很多移动
算法书上的时间复杂度是以比较次数来计的。

[littlewing]

复杂度低并不代表任何情况下速度就快，因为复杂度算得是极限

[capljf]

我的 mac pro 上也是选择排序比插入排序快，100 ～ 10000 个 double 随机数，用 StdRandom.shuffle 打乱了。100 ～ 10000 次都试了，都是选择比插入快。搞得我检查了好几遍代码是不是写反了，但代码确实没问题。还得继续找原因

[capljf]

我猜是插入排序没有做优化，因为每次比较都做了 exch，exch 比较耗时，我去按书上的优化一下，将较大元素都往右移动而不是总是 exch。访问数组的次数能减少一半

[capljf]

为啥回复不了了，提示验证手机号

[capljf]

好像我的回复有些词被 block 了。简单说下，刚刚是我的代码写得有问题，插入是比选择快的，优化后的代码 swap 次数确实比优化前少一半左右