冒泡排序、插入排序、选择排序性能对比

冒泡排序、插入排序和选择排序三种排序的时间复杂度都是O(n^2)，我们来对比一下它们之间的性能差异。

我们随机生成10w的随机整数，分别用三种排序方法，查看消耗时间。

代码：

import java.util.Arrays;
import java.util.Random;

public class SortTest {

    public static void main(String[] args) {
        int limit = 100000;
        int[] array1 = new Random().ints(limit, 1, 10000000).toArray();
        long startBubble = System.currentTimeMillis();
        BubbleSort.sortTest(array1);
        long endBubble = System.currentTimeMillis();
        System.out.println("冒泡排序时间消耗:"+ (endBubble-startBubble));

        int[] array2 = Arrays.copyOf(array1, limit);
        long startInsertion = System.currentTimeMillis();
        InsertionSort.sortTest(array2);
        long endInsertion = System.currentTimeMillis();
        System.out.println("插入排序时间消耗:"+ (endInsertion-startInsertion));

        int[] array3 = Arrays.copyOf(array1, limit);
        long startSelection = System.currentTimeMillis();
        SelectionSort.sortTest(array3);
        long endSelection = System.currentTimeMillis();
        System.out.println("选择排序时间消耗:"+ (endSelection-startSelection));

    }
}

输出：

冒泡排序时间消耗:12420
插入排序时间消耗:2
选择排序时间消耗:684

结果插入排序性能非常好，其次是选择排序，冒泡排序的时间用了12s之多。

我们把数据量降低到1W个随机整数，时间如下：

冒泡排序时间消耗:61
插入排序时间消耗:0
选择排序时间消耗:11

我们把数据量降低到100个随机整数，时间如下：

冒泡排序时间消耗:0
插入排序时间消耗:1
选择排序时间消耗:0

这里可以看出之前性能最好的插入排序，反而变慢了，所以性能快慢，取决于不同的数据规模，不同的数据规模，选择对应的排序算法。