算法梳理-基础排序算法

选择排序

概念：

遍历数组 每一轮都选取「未排定的部分」的最小元素，然后将它 交换 到「未排定的部分」的第 1 个位置。 当剩余一个元素时 即排序完成

选择排序的特点

交换的次数最少
如果一个排序任务交换的成本很高，可以考虑使用选择排序。

运行时间与输入无关
每一趟扫描，除了扫描的元素比上一轮少了一个以外，选择排序没有记住更多的信息。一个极端的例子是，已经是排好序的数组，选择排序还需要一次又一次地扫描。

插入排序

概念：

建一个数组插入有序数组，成为长度+1的有序数组

两种排序插入方式

1. 逐个交换到前面合适的位置
2. 先暂存当前变量，然后将前面的若干个元素逐个向后赋值

小技巧 哨兵》

在排序之前 先把最小的元素拿出来 放在第一位
后续就不用再讨论 二次循环中 j需不需要大于0了
只需要考虑是否岛屿拿出的元素就好
举例：

public class Solution {

    // 「力扣」第 912 题：排序数组

    public int[] sortArray(int[] nums) {
        int len = nums.length;

        // 先选出整个数组中最小的元素，将它交换到下标为 0 的位置
        int minIndex = 0;
        for (int i = 1; i < len; i++) {
            if (nums[i] < nums[minIndex]){
                minIndex = i;
            }
        }
        swap(nums, 0, minIndex);

        // 循环不变量：将 nums[i] 插入到区间 [0, i) 使之成为有序数组
        for (int i = 1; i < len; i++) {
            int temp = nums[i];
            int j = i;
            // 省去了 j > 0 这个判断
            while (nums[j - 1] > temp) {
                nums[j] = nums[j - 1];
                j--;
            }
            nums[j] = temp;
        }
        return nums;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

希尔排序

选择排序的一个变种
将数组不断氛围间隔为1/2数组长度的子序列
然后不断进行插入排序
（放大了插入排序优点：如果一个元素 跟他实际应该在的位置很近 则复杂度最小）

双指针算法

可以为单向双指针和双向双指针
具体可以理解为 用两个指针共同遍历数组 求得极值（通常事件复杂度为o1）
单向双指针例题：283. 移动零
双向双指针例题：11. 盛最多水的容器