算法 - 冒泡/选择/插入排序(n方排序)

• 冒泡排序: 效率最低,因为每次都要进行交换,交换比较耗时.
• 选择排序: 因为有两次遍历,且不能提前结束内层遍历,所以还是比较耗时.
• 插入排序: 效率是很高的,其一是可以提前结束内层遍历,其二是在基本已经有序的数组中,交换次数会很少,效果可以超越 nlog(n) 的排序.

因为这三种排序都比较简单,所以在性能允许的情况下还是比较常用的.
优点:简单

1. 冒泡排序

相邻的两个数,比较大小,前面的数大了就交换

/**
 * 冒泡排序
 */
public class BubbleSort {

    public static void main(String[] args) {

        int[] arr = new int[10000];
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(arr.length * 2);
        }
        System.out.println(Arrays.toString(arr));
        long startTime = System.currentTimeMillis();

        bubbleSort(arr);

        long endTime = System.currentTimeMillis();
        System.out.println((endTime - startTime) / 1000.0 + " s"); // 0.248 s

        System.out.println(Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr) {
        int temp;
        // 提前结束的 flag
        // 对于已经基本有序的有作用,对于基本无序的反而会消耗更多时间
        boolean flag = false;
        int size = arr.length;
        for (int i = 0; i < size && !flag; i++) {
            flag = true;
            for (int j = 0; j < size - 1 - i; j++) {
                // 后面的数比前面的大 交接
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = false;
                }
            }
        }
    }
}

2. 选择排序

先是遍历一遍

1. 遍历剩下的数组
2. 找出最小的数的位置
3. 交换到第一的位置(如果是第二轮则放在第二,以此类推)

一句话:每次取出最小的数,放到前面的位置.

public class SelectSort {

    public static void main(String[] args) {

        int[] arr = new int[10000];
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(arr.length * 2);
        }
        System.out.println(Arrays.toString(arr));
        long startTime = System.currentTimeMillis();

        selectSort(arr);

        long endTime = System.currentTimeMillis();
        System.out.println((endTime - startTime) / 1000.0 + " s"); // 0.248 s

        System.out.println(Arrays.toString(arr));
    }

    public static void selectSort(int[] arr) {

        int index;
        int temp;
        for (int i = 0; i < arr.length; i++) {
            index = i;

            for (int j = i; j < arr.length; j++) {
                if (arr[index] > arr[j]) {
                    index = j;
                }
            }
            temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;

        }
    }
}

3. 插入排序

遍历>如果当前数小于前一个数,则继续向前找,也就在从小到大的数组中,把当前数插入到合适的位置.
注意: 不要在第二层for循环里直接做交换操作,一次交换需要三次赋值.

public class InsertSort {

    public static void main(String[] args) {

        int[] arr = new int[10000];
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(arr.length * 2);
        }
        System.out.println(Arrays.toString(arr));
        long startTime = System.currentTimeMillis();

        insertSort(arr);

        long endTime = System.currentTimeMillis();
        System.out.println((endTime - startTime) / 1000.0 + " s"); // 0.248 s

        System.out.println(Arrays.toString(arr));
    }

    public static void insertSort(int[] arr) {

        int index;
        int cur;
        for (int i = 1; i < arr.length; i++) {
            index = i;
            cur = arr[i];
            for (int j = i; j > 0 && cur > arr[j - 1]; j--) {
                arr[j] = arr[j - 1];
                index = j - 1;
            }
            arr[index] = cur;
        }
    }
}