选择排序

假设有一个数组nums，长度为n，想要将其从小到大排序，选择排序的思路是：

从1 ~ n数据中选择最小的，与nums[0]交换
从2 ~ n数据中选择最小的，与nums[1]交换
……

选择排序的实现核心是：双层for循环+暂存minIndex+交换

private static void selectSort(int[] nums) {
    int temp = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] < nums[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            temp = nums[minIndex];
            nums[minIndex] = nums[i];
            nums[i] = temp;
        }
    }
}

插入排序

假设有一个数组nums，长度为n，想要将其从小到大排序，插入排序的思路是：

比较nums[1]与它前面的元素，插入到第一个大于nums[1]的数据前面
比较nums[2]与它前面的元素，插入到第一个大于nums[2]的数据前面
……

插入排序的实现思路是：比较 + 向后移动，但实际上实现起来，与冒泡排序是差不多的，即多次比较和交换，而且插入排序的性能一定优于冒泡排序（因为只移动，不交换），因此一般不把冒泡排序单独拿出来看

private static void insertSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        for (int j = i -1; j >= 0; j--) {
            if (nums[j] > nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
}

可以看到，该实现其实本质上就是冒泡排序，如果想实现只移动，不交换的话，可以按如下改动；

private static void insertSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int temp = nums[i];
        int tempIndex = 0;
        for (int j = i -1; j >= 0; j--) {
            if (nums[j] > temp) {
                nums[j + 1] = nums[j];
            } else {
                tempIndex = j + 1;
                break;
            }
        }
        nums[tempIndex] = temp;
    }
}

这种写法构思不难，但是实现上有非常多的小逻辑需要注意，例如tempIndex要初始化为0，比如当if (nums[j] > temp) 条件为false时要按照tempIndex = j + 1赋值，同时要及时break，总得来说，不如冒泡的思路好实现

希尔排序

希尔排假设有一个数组nums，长度为n，想要将其从小到大排序，希尔排序的思路是：

以n/2作为起始跨度gap，比较并交换nums[1]、nums[0 + gap]、nums[0 + 2gap]...；比较并交换nums[1]、nums[1 + gap]、nums[1 + 2gap]...
以(n/2)/2作为跨度gap，比较nums[1]、nums[0 + gap]、nums[0 + 2gap]...；比较并交换nums[1]、nums[1 + gap]、nums[1 + 2gap]...
...
以1位跨度，比较nums[1]、nums[0 + gap]、nums[0 + 2gap]...；比较并交换nums[1]、nums[1 + gap]、nums[1 + 2gap]...

补链接图https://blog.csdn.net/m0_63033419/article/details/127524644#1_19

这个思路整体的逻辑就是把小的、大的分列两边，然后用更细的跨度继续把小的、大的分列两边

private static void shellSort(int[] nums) {
    for (int gap = nums.length / 2; gap > 0; gap /= 2) {
        for (int i = 0; i + gap < nums.length; i++) {
            int j = i + gap;
            while (j < nums.length) {
                if (nums[i] > nums[j]) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
                j += gap;
            }
        }
        Arrays.stream(nums).forEach(num -> System.out.print(num + " "));
        System.out.println();
    }
}

代码的核心是三层循环，第一层循环gap，第二层循环i，第三层循环i+gap

看似三层循环似乎复杂度比插入排序跟高了，但实际上希尔排序是插入排序的优化，因为希尔排序是先分组再交换，整体趋向于越来越有序，越到后面交换次数越少

归并排序

归并排序的本质是分治法，即将一个大任务拆解成小任务，最后进行merge

归并排序有两种思路：

自上到下先分解再合并
自下而上的处理-合并

处理分治法和处理线性规划类似，必须要找到初始状态，然后再分析如何合并

先分析合并的逻辑：假设有一个数组nums，其中leftLow ~ leftHighy与rightLow ~ rightHigh两段都是有序的，现在想对这两段进行排序，merge方法如下：

private static void merge(int[] nums, int leftLow, int leftHigh, int rightLow, int rightHigh) {
    int i = leftLow;
    int j = rightLow;
    int index = 0;
    int [] temp = new int[rightHigh - leftLow + 1];
    while (index < rightHigh - leftLow + 1) {
        if (i == leftHigh + 1) {
            temp[index] = nums[j];
            j += 1;
        } else if (j == rightHigh + 1) {
            temp[index] = nums[i];
            i += 1;
        } else if (nums[i] > nums[j]) {
            temp[index] = nums[j];
            j += 1;
        } else {
            temp[index] = nums[i];
            i += 1;
        }
        index += 1;
    }
    for (int k = 0; k < temp.length; k++) {
        nums[leftLow + k] = temp[k];
    }
}

然后分析大数组的分治场景

private static void mergeSort(int[] nums, int low, int high) {
    if (low == high) {
        return;
    } else if (low == high - 1) {
        if (nums[low] > nums[high]) {
            int temp = nums[low];
            nums[low] = nums[high];
            nums[high] = temp;
        }
        return;
    } else {
        int mid = (high + low) / 2;
        mergeSort(nums, low, mid);
        mergeSort(nums, mid + 1, high);
        merge(nums, low, mid, mid +1, high);
    }
}

初始场景：

nums长度为为1，不用交换直接返回
nums长度为2，比较两个值进行交换，返回

分析nums长度大于2的场景

nums长度大于2，取中值进行分治，这里取中值使用(high + low) / 2 ，而不是(low - hight + 1)/2，因为low有可能不是从0开始，例如找4 ~ 7的中值，为11/2取5
然后对两个分治结果进行合并

快速排序

快速排序的本质还是分治法，与归并排序不断分解的差异在于，快排通过不断交换将一个锚点的左右两边分别固定下来，让左边全都小于锚点，右边全都大于锚点

这个交换的过程是基于双指针的思路实现的，首先找到一个锚点，一般默认是第一条数据，思路如下：

移动右指针，直到找到一个数小于锚点，用其替换左指针指向的值
移动左指针，直到找到一个数大于锚点，用其替换右指针指向的值
重复1、2直到左右指针重合，用锚点值替换当前值

private static void quickExchange(int[] nums, int low, int high) {
    int temp = nums[low];
    int i = low;
    int j = high;
    for (; j > i; j--) {
        if (nums[j] < temp) {
            nums[i] = nums[j];
            for (; i < j; i++) {
                if (nums[i] > temp) {
                    nums[j] = nums[i];
                    break;
                }
            }
        }
    }
    nums[i] = temp;
}

或如下写法：

private static void quickExchange(int[] nums, int low, int high) {
    int temp = nums[low];
    int i = low;
    int j = high;
    while (j > i) {
        while (j > i && nums[j] >= temp) {
            j -= 1;
        }
        nums[i] = nums[j];
        while (j > i && nums[i] <= temp) {
            i += 1;
        }
        nums[j] = nums[i];
    }
    nums[i] = temp;
}

while写法中要注意j > 1的条件要出现在子while里面，否则i可能加到比j大，才能退出外层循环

然后写快排大逻辑：

private static void quickSort(int[] nums, int low, int high) {
    if (low >= high || high < 0 || low >= nums.length) {
        return;
    }

    int sorted = quickExchange(nums, low, high);
    quickSort(nums, low, sorted - 1);
    quickSort(nums, sorted + 1, high);
}

其中注意下初始条件low >= high || high < 0 || low >= nums.length即可

优先队列/堆排序

假设有一个优先队列，不考虑其中数据是不是有序的，但是每次都能按要求取出一个最大/最小的数据，同样是符合排序要求的

这种场景适用于一些例如处理优先级最高的任务等场景

实现优先队列有几种方案：

让队列本身就有序，即插入时移动最大/最小元素，使队列本身顺序
使用堆排序

堆是一种特殊的树：父节点一定大于孩子节点的大顶堆，和父节点一定小于孩子节点的小顶堆

与完全二叉树对应的是完全二叉堆，即左孩子没有时一定不会填充右孩子的二叉堆，完全二叉堆是适合实现堆排序的数据结构

以一个完全二叉小顶堆为例：

补链接图https://blog.csdn.net/weixin_51609435/article/details/122982075

将堆转换为数组即：

补链接图https://blog.csdn.net/weixin_51609435/article/details/122982075

即这个数组就是我们要的优先队列

那么这个队列的排序思想即：

首先将待排序的数组构造成一个小顶堆，此时，整个数组的最小值就是堆结构的顶端
将顶端的数与末尾的数交换，此时，末尾的数为最小值，剩余待排序数组个数为n-1，最后一位就定下来了
将剩余的n-1个数再构造成小顶堆，再将顶端数与n-1位置的数交换，如此反复执行，即实现了从大到小排序（从小到大则构造大顶堆即可）

构造大顶堆/小顶堆

构造大顶堆/小顶堆的思路为调整一个堆的根节点与其子节点，如果发生交换，则调整其子堆，具体思路如下：

从后往前，找到第一个非叶子节点，调整这个子堆
调整好后，倒着找下一个非叶子节节点

private static void genMinRootHeap(int[] nums, int end) {
    int first = (end + 1) / 2 - 1;
    // 首先从最大非叶子节点倒排，最大非叶子节点的找法就是length / 2 + 1
    for (int i = first; i >= 0; i--) {
        // 对一个堆构造大顶/小顶堆，即分别比较其左右孩子，然后递归构造其左右子堆
        genMinRootHeapNode(nums, i, end);
    }
}
private static void genMinRootHeapNode(int[] nums, int root, int end) {
    if (root < 0 || root > end) {
        return;
    }
    int leftChild = 2 *  root + 1;
    int rightChild = 2 *  root + 2;
    // 分别比较左右孩子和最大长度，如果左右孩子需要调换，则递归整理左右子堆
    if (leftChild <= end && nums[leftChild] < nums[root]) {
        int temp = nums[leftChild];
        nums[leftChild] = nums[root];
        nums[root] = temp;
        genMinRootHeapNode(nums, leftChild, end);
    }
    if (rightChild <= end && nums[rightChild] < nums[root]) {
        int temp = nums[rightChild];
        nums[rightChild] = nums[root];
        nums[root] = temp;
        genMinRootHeapNode(nums, rightChild, end);
    }
}

其实不需要这么多参数也能构造，例如genMinRootHeap方法，只需要nums即可，而genMinRootHeapNode方法只需要nums和root即可

那么为什么加了end参数呢？回看排序思想，其中每次将顶端元素和最后一位交换，都是定下来一个最终元素，不再调换，因此为了排序，传入一个end限制nums本次构造大顶堆/小顶堆的实际长度，即end后面就都不动了

因此比较左右孩子的时候，使用的是leftChild <= end和rightChild <= end

堆排序实现

private static void heapSort(int[] nums, int end) {
    genMinRootHeap(nums, end);
    if (end == 0) {
        return;
    }
    int temp = nums[0];
    nums[0] = nums[end];
    nums[end] = temp;
    heapSort(nums, end - 1);
}

有了构造大顶堆、小顶堆的思路，再来写堆排序的逻辑就很简单了

只需要每次排序时先规整这个堆，然后将头尾交换，再次堆剩余元素进行堆排序即可

排序规则的性能

N²排序规则：选择排序、插入排序（取决于元素排列情况）
NlogN排序规则：希尔排序、快速排序、归并排序、堆排序

一般来说，快速排序是最快的通用排序算法，因为其中的线性系数比其他排序规则小

目录CONTENT

排序