时间复杂度(最好 最坏 平均) 空间复杂度 稳定性 

冒泡  n    n^2  n^2  原地排序  稳定
选择  n^2  n^2  n^2  原地排序  非稳定
插入  n    n^2  n^2  原地排序  稳定

虽然3者 平均时间复杂度都是 n^2 ,不过这个 忽略了系数、常数和低阶参数
jdk 数组排序 元素个数少于某个阈值时 使用 插入排序

private static final int INSERTION_SORT_THRESHOLD = 47;
If the length of an array to be sorted is less than this constant, 
insertion sort is used in preference to Quicksort.

本机测试 1000个元素 100次 

insertSortTime=169
selectSortTime=449
bubbleSortTime=1135

insertSortTime=167
selectSortTime=449
bubbleSortTime=1131

insertSortTime=170
selectSortTime=444
bubbleSortTime=1119




测试代码

https://gitee.com/dyyx/hellocode/tree/master/src/algo/sort/BubbleSelectInsertSort.java



import java.time.LocalDateTime;
import java.util.Random;

public class BubbleSelectInsertSort {

    public static void bubbleSort(int[] arr) {
        int len = arr.length;
        if (len <= 1) {
            return;
        }
        for (int i = 0; i < len; ++i) {
            // 退出冒泡的标志
            boolean flag = false;
            for (int j = 0; j < len - i - 1; ++j) {
                if (arr[j] > arr[j + 1]) {
                    // 交换
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    // 表示有数据交换
                    flag = true;
                }
            }
            // 没有数据交换，提前退出
            if (!flag)
                break;
        }
    }

    public static void selectSort(int[] arr) {
        int len = arr.length;
        if (len <= 1) {
            return;
        }
        for (int i = 0; i < len; i++) {
            int index = i;
            for (int j = i; j < len; j++) {
                // 找出每一轮的最小值
                if (arr[j] < arr[index]) {
                    index = j;
                }
            }
            if (index == i) {
                continue;
            }
            // 和已排序部分的后一个位置进行交换
            int temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }

    }

    public static void insertSort(int[] arr) {
        int len = arr.length;
        if (len <= 1) {
            return;
        }
        for (int i = 0; i < len; i++) {
            int temp = arr[i];
            // 从有序数组的最后一个元素开始往前找
            int j = i - 1;
            while (j >= 0) {
                if (arr[j] > temp) {
                    // 如果当前元素大于temp，则后移
                    arr[j + 1] = arr[j];
                    j--;
                } else {
                    break;
                }
            }
            // 插入
            arr[j + 1] = temp;
        }
    }
    
    
    private static final Random RAND = new Random();
    
    private static int[] getTestArr() {
        int[] arr = {3,2,1,9,7,8,7,5,6};
        return arr;
    }
    
    private static int[] genTestArr(int count,int bound) {
        if(count<=0) {
            count = 100;
        }
        if(bound<=0) {
            bound = 100;
        }
        int[] arr = new int[count];
        for(int i=0;i<count;i++) {
            arr[i] = RAND.nextInt(bound);
        }
        return arr;
    }
    
    private static void printArr(int[] arr) {
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<arr.length;i++) {
            sb.append(arr[i]).append(" ");
        }
        System.out.println(sb.toString());
    }
    
    public static  void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void shuffle(int[] arr) {
        int length = arr.length;
        for ( int i = length; i > 0; i-- ){
            int randInd = RAND.nextInt(i);
            swap(arr, randInd, i - 1);
        }
    }
    
    private static void runTest(int[] arr,int count) {
        long start = System.currentTimeMillis();
        for(int i=0;i<count;i++) {
            shuffle(arr);
            bubbleSort(arr);
        }
        long end = System.currentTimeMillis();
        long bubbleSortTime = end - start;
        
        start = System.currentTimeMillis();
        for(int i=0;i<count;i++) {
            shuffle(arr);
            selectSort(arr);
        }
        end = System.currentTimeMillis();
        long selectSortTime = end - start;
        
        
        start = System.currentTimeMillis();
        for(int i=0;i<count;i++) {
            shuffle(arr);
            insertSort(arr);
        }
        end = System.currentTimeMillis();
        long insertSortTime = end - start;
        
        System.out.println("insertSortTime="+insertSortTime);
        System.out.println("selectSortTime="+selectSortTime);
        System.out.println("bubbleSortTime="+bubbleSortTime);

    }
    

    public static void main(String[] args) throws Exception {
        int[] arr = getTestArr();
        printArr(arr);
        
        bubbleSort(arr);
        printArr(arr);
        arr = getTestArr();
        selectSort(arr);
        printArr(arr);
        
        arr = getTestArr();
        insertSort(arr);
        printArr(arr);
        
        //
        arr = genTestArr(20,10);
        printArr(arr);
        insertSort(arr);
        printArr(arr);

        shuffle(arr);
        printArr(arr);


        System.out.println("start test \n\n");
        
        final int COUNT1 = 999;
        final int COUNT2 = 1000;
        arr = genTestArr(1000,100);
        
        for(int i=0;i<COUNT1;i++) {
            runTest(arr,COUNT2);
            System.out.println(LocalDateTime.now()+","+i+"\n");
        }

    }

}