public class Sort {
    public static void bubbleSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        // 优化，用来记录某一轮遍历是否没有任何元素交换位置，如果是说明已经排好了，不再需要遍历后序。
        boolean isSorted = false;
        // 外层循环用来控制一共要遍历几次，因为相邻两个依次比较，所以一共需要比较 n - 1 次
        for(int i = 0; i < array.length - 1; i++) {
            isSorted = true;
            // 每次遍历都从头开始比较，直到比较到上一次排序好的元素为止。
            // 因为外层循环每一次遍历都会排序好一个，所以第 i 轮只需要比较前 n - 1 - i 个
            for(int j = 0; j < array.length - 1 - i; j++) {
                if(array[j] > array[j + 1]) {
                    isSorted = false;
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
            // 如果某一轮遍历时，两两比较没有任何一个元素发生交换，说明已经排好了，则不需要继续遍历。
            if (isSorted) {
                return;
            }
        }
    }
}

public class Sort {
    public static void selectSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        // 每一次都把当前需要排序的最小元素下标指向 i，并且初始让当前轮次最小数下标 minIndex 指向 i
        for (int i = 0, minIndex = i; i < array.length - 1; i++) {
            // 从当前第 i 个数开始，找出最小的数的下标，存为 minIndex
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            // 查找完毕后，如果 minIndex != i，说明第 minIndex 的数小于当前轮次的第 i 个数，则交换位置，使得前 i 个数有序。
            if (i != minIndex) {
                int temp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = temp;
            }
        }
    }
}

public class Sort {
    public static void insertionSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        // 第一个元素不需要排序，所以从第二个元素开始
        for (int i = 1; i < array.length; i++) {
            // 每一次排下一个元素，都相当于从这个元素开始往前做一轮冒泡
            for (int j = i; j >= 1; j--) {
                if (array[j] > array[j - 1]) {
                    break;
                }
                int temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
            }
        }
    }
}

public class Sort {
    public static void quickSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        doSort(array, 0, array.length - 1);
    }

    private static void doSort(int[] array, int left, int right) {
        if (left > right || left < 0 || right > array.length) {
            return;
        }
        int temp;
        // 分割元素的下标
        int splitIndex = right;
        // 下一个用来存放【小于分割元素的元素】的下标，也就是查找到下一个比分割元素小的元素后，需要将这个目标元素与哪一位的元素交换
        int nextLessIndex = left;
        // 遍历整个范围内的数组，将所有比分割元素小的元素依次从数组的开头开始交换，交换完成后，n 个比分割元素小的元素就位于数组的开头 n 位
        for (int i = left; i < right; i++) {
            // 从数组第 1 位开始判断，如果小于分割元素，就交换到 nextLessIndex 的位置。
            // 如果是第 1 位元素则不需要交换，所以添加了 i != nextLessIndex 的判断条件
            if (array[i] <= array[splitIndex] && i != nextLessIndex) {
                temp = array[i];
                array[i] = array[nextLessIndex];
                array[nextLessIndex] = temp;
                nextLessIndex++;
            }
        }
        // 遍历完后，所有比 split 对应元素小的都在 nextLessIndex 左侧，所以可以直接把 split 对应元素与 nextLessIndex 对应元素交换。
        temp = array[nextLessIndex];
        array[nextLessIndex] = array[split];
        array[split] = temp;
        // 交换后，也更新 split 索引值，变成了原来的 nextLessIndex
        split = nextLessIndex;
        // 对 split 左侧段递归
        doSort(array, left, split - 1);
        // 对 split 右侧段递归
        doSort(array, split, right);
    }
}