基础排序算法

冒泡排序

1. 排序原理：每次循环将末尾的最小的数往上冒，如果没有交换则跳出循环
2. 跳出循环条件：如果一次循环没有交换说明后面的顺序是正确的，则不需要再排序可以跳出

public int[] sort1(int[] a) {
    for (int i = 1; i < a.length; i++) {
        boolean b = false;
        for (int j = a.length - 1; j >= i; j--) {
            if (a[j] < a[j - 1]) {
                int c = a[j];
                a[j] = a[j - 1];
                a[j - 1] = c;
                b = true;
            }
        }
        if (!b)
            break;

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

    return a;
}

插入排序

1. 排序原理：从第二个数开始，循环比较前一个数，直到最后一个数排序完成
2. 内层循环中如果一次比较没有交换，则可以跳出内层循环，因为之前的都是排好的

public int[] sort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        for (int j = i; j > 0; j--) {
            if (a[j] < a[j - 1]) {
                int c = a[j];
                a[j] = a[j - 1];
                a[j - 1] = c;
            } else {
                break;
            }
        }
        System.out.println(Arrays.toString(a));
    }

    return a;
}

二分法

二分法不是排序算法，但是是常用的基础算法

注意：传入的数组要求必须是排序后的

private int getIndex(int i, int[] a) {
    int index = -1;
    int low = 0, hight = a.length - 1;

    while (low <= hight) {

        int mid = (low + hight) / 2;
        if (a[mid] > i) {
            hight = mid - 1;
        } else if (a[mid] < i) {
            low = mid + 1;
        } else {
            return mid;
        }

    }

    return index;
}