【Leetcode】一、排序

1、选择排序

给定数组arr，其长度为n。实现思路：

• 遍历数组，从0 ~ n - 1，找到最小的，找到后，和数组的第一个元素互换位置
• 继续新一轮遍历，从1 ~ n - 1，找到最小的，找到后，和数组的第二个元素互换位置
• 再来一轮遍历，从2 ~ n - 1，找到最小的，找到后，和数组的第三个元素互换位置
• ……
• 如此，遍历完数组，即可完成排序

核心思路：每次遍历，把剩下的里面最小的元素扔前面去，0到n-1的范围找最小的扔前面，再1到n-1的范围找最小的，以此类推。代码实现：

public class Sort {
    /**
     * 选择排序
     */
    public static void selectSort(int[] arr) {
        // 数组长度为1时，不用排序
        if (null == arr || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            // 最小值的索引，开始i=0
            int minValueIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                // 如果i的下一个元素比i小，则覆盖最小值索引
                minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
            }
            // 0 ~ n-1 的范围都比较完了，把最小值的和第一个元素互换
            int temp = arr[i];
            arr[i] = arr[minValueIndex];
            arr[minValueIndex] = temp;
            // 一轮循环结束，找到了第一小的元素，并放在了数组首位
            // 接下来开下一轮循环，找第二小的元素，放在数组的第二位
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2、冒泡排序

前面选择排序是，我找到最值后，手动给它放到数组首位。冒泡则是：第n个元素和第n+1个元素对比，交换，让大的那个放右边，接着n+1和n+2位置的元素对比，依旧大的放右边。如此，比较完一轮，就会让第一大的元素像一个气泡一样，一步步的走到了数组末尾的位置。再进行第二轮，第二大的元素也会像一个气泡一样，一步步的走到了数组倒数第二的位置。

代码实现：

public class Sort {

    /**
     * 冒泡排序
     */
    public static void bubbleSort(int[] arr) {
        // 数组长度为1时，不用排序
        if (null == arr || arr.length < 2) {
            return;
        }
        for (int end = arr.length - 1; end > 0; end--) {
            // 设arr.length = n
            // 外层出循环第一轮，end = n - 1, 先处理0 ~ n-1
            // 外层循环第二轮，end = n - 2, 先处理0 ~ n-2
            // 外层循环最后一轮，end = 1, 先处理0 ~ 1
            for (int i = 0; i < end; i++) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
        }

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

3、插入排序

插入排序，正如这个名字，就像打牌一样，整牌时，比如现在最大的放在左边，那抽到一张新牌后，从右往左看，一个个比较，然后把新进来的牌插入到合适的位置。插入排序也是这个思路。也就是说，实现步骤是：

• 先保证0 ~ 0 号元素有序（即保证第一张牌有序）
• 再保证0 ~ 1号元素有序（即保证前两张牌有序）
• 再保证0 ~ 2号元素有序（即保证前三张牌有序），但前两张已经有序，此时只需处理第三张牌即可
• ……
• 保证0 ~ n - 1号元素有序，但前n - 2张已有序，此时只需处理最后一张牌，一个个比，把它插入到合适的位置即可
  

到这儿，想到一点，算法，即解决问题的步骤，把生活中怎么解决同样问题的行为，翻译成代码，就是答案。此外，解一道题，应该先举一个简单具体的例子，分析清楚后，再逐步扩大数据量来分析。

public class Sort {

    /**
     * 插入排序
     */
    public static void insertSort(int[] arr) {
        // 数组长度为1时，不用排序
        if (null == arr || arr.length < 2) {
            return;
        }
        // 初始end = 1,先保证0~1有序，后面end+1,就是保证0~2有序
        // end控制末尾的边界
        for (int end = 1; end < arr.length; end++) {
            // end - 1 > 0，说明左边还有元素可以比较
            // arr[end - 1] < arr[end]不满足的话，说明有序，也不用交换
            int newNumIndex = end;
            while (newNumIndex - 1 >= 0 && arr[newNumIndex - 1] < arr[newNumIndex]) {
                int temp = arr[newNumIndex - 1];
                arr[newNumIndex - 1] = arr[newNumIndex];
                arr[newNumIndex] = temp;
                // 交换后，和新的左边的数继续比，直到越界或者遇到比它大的数字，停止比较和交换
                newNumIndex--;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

优化下：

public class Sort {

    /**
     * 插入排序2
     * 用for嵌套
     */
    public static void insertSort2(int[] arr) {
        if (null == arr || arr.length < 2) {
            return;
        }
        // 初始end = 1,先保证0~1有序，后面end+1,就是保证0~2有序
        // end控制末尾的边界
        for (int end = 1; end < arr.length; end++) {
            // pre为当前数的左侧方向的前一个数
            for (int pre = end - 1; pre >= 0 && arr[pre] < arr[pre + 1]; pre--) {
                int temp = arr[pre];
                arr[pre] = arr[pre + 1];
                arr[pre + 1] = temp;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23