这是一个创建于 2294 天前的主题，其中的信息可能已经有所发展或是发生改变。
刚刚开刷红宝书，好奇测了一下发现 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  | 1 davie 2019-07-02 15:27:43 +08:00 via Android 数据量多大？ |
| 3 davie 2019-07-02 15:42:00 +08:00 via Android 随机性呢？ |
 | 4 yusuzhan OP @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; } } ``` |
 | 6 AmmeLid 2019-07-02 15:53:16 +08:00 用数组来做插入排序，还要考虑插入后数据移动的开销吧。 |
 | 7 wutiantong 2019-07-02 16:00:32 +08:00 很可能是 exch 引入了额外的开销 |
| 8 yusuzhan OP @wutiantong 真没啥，书里原文 ``` private static void exch(Comparable[] a, int i, int j) { swap++; final Comparable swap = a[i]; a[i] = a[j]; a[j] = swap; } ``` |
 | 9 xuwei0056 2019-07-02 16:07:19 +08:00 创建 Comparable 的开销大？ |
 | 10 jmc891205 2019-07-02 16:08:10 +08:00 你再测一下 less 和 exch 的速度好了 |
| 11 wutiantong 2019-07-02 16:14:53 +08:00 |
 | 12 lance6716 2019-07-02 16:19:54 +08:00 via Android 我咋记得插入排序不是这么写…一个一个往后移，而不是交换 |
| 13 yusuzhan OP |
| 14 yusuzhan OP @xuwei0056 用的 Integer 数组，创建的开销没算， 只统计的排序的速度。刚才看了一下， 确实是 exch 速度比 less 慢导致的。 |
 | 15 wizardoz 2019-07-02 17:24:27 +08:00 选择排序移动很少，插入排序有很多移动 算法书上的时间复杂度是以比较次数来计的。 |
 | 16 littlewing 2019-07-03 02:27:39 +08:00 via Android 复杂度低并不代表任何情况下速度就快，因为复杂度算得是极限 |
 | 17 capljf 2019-12-12 19:53:46 +08:00 我的 mac pro 上也是选择排序比插入排序快，100 ～ 10000 个 double 随机数，用 StdRandom.shuffle 打乱了。100 ～ 10000 次都试了，都是选择比插入快。搞得我检查了好几遍代码是不是写反了，但代码确实没问题。还得继续找原因 |
| 18 capljf 2019-12-12 19:58:26 +08:00 我猜是插入排序没有做优化，因为每次比较都做了 exch，exch 比较耗时，我去按书上的优化一下，将较大元素都往右移动而不是总是 exch。访问数组的次数能减少一半 |
| 19 capljf 2019-12-12 21:07:28 +08:00 为啥回复不了了，提示验证手机号 |
| 20 capljf 2019-12-12 21:10:17 +08:00 好像我的回复有些词被 block 了。简单说下，刚刚是我的代码写得有问题，插入是比选择快的，优化后的代码 swap 次数确实比优化前少一半左右 |
Select Language