排序算法-java实现

核心思想：我更愿意称其为相邻排序，每次和相邻的后一位进行比较，如果比后一位大，则交换位置。即通过第一次排序将最大的排到最右边，那么第二次排序将第二大的排到右边第二位。以此类推，直至最后一位
边界问题：

为何 i < sort.length - 1 ? 这样可以吗？i < sort.length
当 i < sort.length - 1 时，i最大可以取到6，此时已经排序了六轮，后六位已经有序，只剩前两位乱序。此时 j = 0
j < 1,可以进行一次比较，将前两位进行排序。到此时，其实排序已经结束。
若i < sort.length，则i最大可以取到7，此时已经排序了七轮，后七位已经有序，则只剩第一位不用排序。

为何 j = 0; j < sort.length - i - 1？
因为每次排序都将最大的排到右边，则下一轮比较开始仍从第一位开始，则j=0.
j < sort.length - i - 1。-1是为了防止下标越界，因为要和j+1比较。- i 是因为已经比较了 i 轮，此时后 i 位已经有序，没有必要参与排序。

public class BubbleSort {

    public static void main(String[] args) {
        int[] sort = {24, 67, 99, 75, 661, 22, 8, 2};
        for (int i = 0; i < sort.length - 1; i++) {
            for (int j = 0; j < sort.length - i - 1; j++) {
                if (sort[j] > sort[j + 1]) {
                    int temp = sort[j];
                    sort[j] = sort[j + 1];
                    sort[j + 1] = temp;
                }
            }
        }
        for (int i = 0; i < sort.length; i++) {
            System.out.print(sort[i] + " ");
        }
    }
}

核心思想：我更愿意称其为间隔排序，每次排序，都会和其后所有元素进行比较，如果比其大，则交换位置。即通过第一次排序将最小的排到最左边，那么第二次排序将第二小的排到左边第二位。以此类推，直至最后一位

边界问题：
为何 i < sort.length - 1？
因为j 可以改为j < sort.length - 1？i 不行。因为如果j只能取到倒数第二位，则最后一位一直没有参与排序

优化：
使用一个标志位，记录比 i 的值，不用每次都交换位置，一轮排序结束，只交换一次位置。

public class SelectionSort {

//    public static void main(String[] args) {
//        int[] sort = {24, 67, 99, 75, 661, 22, 8, 2};
//        for (int i = 0; i < sort.length - 1; i++) {
//            for (int j = i + 1; j < sort.length; j++) {
//                if (sort[i] > sort[j]) {
//                    int temp = sort[i];
//                    sort[i] = sort[j];
//                    sort[j] = temp;
//                }
//            }
//        }
//        for (int i = 0; i < sort.length; i++) {
//            System.out.print(sort[i] + " ");
//        }
//    }

    public static void main(String[] args) {
        int[] sort = {24, 67, 99, 75, 661, 22, 8, 2};
        for (int i = 0; i < sort.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < sort.length; j++) {
                if (sort[minIndex] > sort[j]) {
                    minIndex = j;
                }
            }
            if (minIndex != i){
                int temp = sort[i];
                sort[i] = sort[minIndex];
                sort[minIndex] = temp;
            }
        }
        for (int i = 0; i < sort.length; i++) {
            System.out.print(sort[i] + " ");
        }
    }
}