数据结构与算法|【优选算法 & 分治】深入理解分治算法：分治算法入门小专题详解

快速排序算法

(1) 快速排序法

(2) 快排前后指针

(3) 快排挖坑法

颜色分类

题目解析

算法原理

算法原理和移动零非常相似

简述移动零的算法原理

cur 在从前往后扫描的过程中，如果扫描的数符合 f 性质，就把这个数放到 dest 之前的区域；
符合 g 性质则不管，知道 cur 遍历到最后，dest 指针就可以把数组划分成两个部分；

解法：三指针

当 i 遍历结束数组后，整个数组就被排好序了，并且数组以 left，right 两个指针为分界线分成三个部分；

在遍历的过程中，整个数组会被划分成四个部分：

对遍历到的 nums[ i ] 的不同元素的分类处理

nums[ i ] = 0

对于上面这种情况，我们只需要 swap( nums[ left + 1] , nums [ i ] ) left++，i ++ 即可，要注意nums[left+1]=1 ；

但是有一种极端情况，就是如果 i = left + 1，并且也符合 nums[ i ] = 0 的情况，我们依旧要执行 swap( nums[ left + 1] , nums [ i ] )；

虽然这种极端情况是变成自己和自己交换，但是处理方法不变：交换完成后，left ++ , i ++；

nums[ i ] = 1

此时我们令 i ++ 即可；

nums[ i ] = 2

对于这种情况，我们可以 swap( nums[ i ] , nums[ right - 1 ] ) ，然后 right-- ;

此时需要特别注意，swap( nums[ i ] , nums[ right - 1 ] ) 后，i 是不可以 ++ 的，因为 [ i ,right-1 ] 是待扫描区域，交换后，nums[ i ] 依旧是待扫描元素，所以 i 如果是和 right -1交换的情况，i 是一定不可以++的

处理细节问题

循环终止条件

当待扫描区域已经没有元素，说明此时数组所有元素已经全部被扫描并且分好类了，结束循环即可，所以循环终止条件是 i != right；

指针初始化

根据我们上面的算法原理，为了保证 left 指向 0 区域的最右边， right 区域指向 2 区域的最左边，我们交换元素是不会让 nums[ left ] ，nums[ right ] 亲自和 nums[ i ] 进行交换的：

所以我们的指针初始化的值如下：

这样的操作是为了避免漏掉对 nums[ 0 ] ，nums [ n - 1 ] 的扫描；

编写代码

报错原因

交换元素的方法不对；
并且初始化 left，和 right 的操作没有处理好，会漏掉对 nums[ 0 ] ，nums [ n - 1 ] 的扫描

使用快速排序来排序数组

题目解析

算法原理

解法：原始快速排序

原始快速排序

而原始快速排序的方法最核心的步骤，就在于根据基准元素进行数据划分的过程，这个步骤的名字是 partation；

但是，如果使用快速排序的数组有重复元素，那么快排的时间复杂度就会退化：

解法：用" 数组分三块 " 的思想实现快速排序

这是基于原始快速排序的优化策略，用于应对快速排序的数组有大量重复元素的情况，从对数组分成两块划分为分成三块：

在数组出现大量重复元素时，通过把数组分成三段，可以把时间复杂度从 O(N^2) 降到 O(N)；

分类讨论

我们通过递归不断对划分的小区域排序，最终得到排好序的数组；

优化：用随机的方式选择基准元素

如果要想让快排的时间复杂度趋于 O(N* logN) ，就需要随机地选择基准元素；

随机选择基准元素，就是给我们一个数组，我们要等概率地返回区间上的任意一个数；

如何随机地选择一个基准元素呢？

编写代码

准备工作

传入要排序的左区间和右区间：

如果 L >= R，则说明排序的区间要么只有一个，要么这个区间没有元素，说明整个数组已经排序完毕；

随机生成基准元素 & 初始化下标

要记一下如何生成随机数下标，以及要特别注意这里的初始化 left != -1 ，right != nums.length：

把数组分三块

[ left + 1 , right - 1 ] 这块区域用于存与生成的随机基准元素值相同的元素，并且以这块区域为基准，把其他数组元素分到这三块区域对应的区域；

可以记一下这个 partation 的过程，这是快排的核心逻辑；

[ L , left ] & [ right , R ] 进行排序

根据 nums[ i ] 与 key 的大小关系，把所有元素放到 [ left + 1 , right - 1 ] 的两边（两边还是乱序的），再对两边区域进行递归排序即可；

快速选择算法

数组中的第K个最大元素

题目解析

算法原理

解法：基于快排实现快速选择算法

快速排序 Partation

本题是要找出数组中第 K 大的元素 KthLarges，那么我们可以根据基准元素，来判断 KthLarges 是落在上面三个区域的哪一个区域，然后对这个区域进行继续进行 Partation，继续找 KthLarges;

根据 K 的值分情况讨论，确定 KthLarges 的区间位置

我们先分别设三个区间的元素个数：

处理细节问题

我们解释一下这种情况：

编写代码

先根据快排 partation 原理，把数组分三块

根据 k 的值来决定递归三块中的哪一块区域

最小的k个数

题目解析

算法原理

解法一：直接排序

时间复杂度 O( N * logN)

解法二：使用大根堆( 求最小的前K个数)

时间复杂度 O( N * logK )

解法三：快速选择算法

时间复杂度趋于 O( N ) ，因为是随机选择基准元素，步骤如下：

对 K 的值分类讨论

(1) a > k

(2) b >= k

这种情况我们直接返回前面两个区域的前 k 个小的元素即可，不用关心 [ L , right ] 区间的顺序；

(3) k > b+c

通过这三种情况，我们就能明显的感受到快速选择排序是最优的解法;

比如第三种情况，此时[ L ，right ] 区间是没有排序的，但是我们依旧已经找到了最小的 k 个元素的一部分；而其他两种情况都是要对数组的每一个元素进行排序；

编写代码

我们是对 nums 的前 k个元素进行排序，把然后把 nums 的前 k 个元素赋值个 ret，然后返回；

报错原因：粗心导致 left & right 指针的初始值写错了

归并排序

当数组块被分成每一块都只有一个元素，分块结束；
用双指针合并两个有序数组；
归并排序的决策树非常像二叉树的后续遍历( 左右根 )，而快排则类似前序遍历(先对数组整体粗糙分一遍，再去两边区域细分)；

使用归并排序来排序数组

题目解析

编写代码

优化：辅助数组设置为全局变量

把 tmp 设置为全局，就不用在每次递归时，创建一个新的 tmp ，减少时间开销；


    int[] nums, tmp ;
 
    public int[] sortArray(int[] _nums) {
        nums = _nums;
        tmp = new int[nums.length]; 
        mergeSort(0, nums.length - 1);
        return nums;
    }
 
    public void mergeSort(int left ,int right){
        if(left >= right) return;
 
        int mid = (left + right) / 2;
 
        mergeSort(left , mid);
        mergeSort(mid + 1 , right);
 
        int cur1 = left; 
        int cur2 = mid + 1; 
        int i = 0 ; 
 
        while(cur1 <= mid && cur2 <= right){
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++] ; 
        }
 
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];
 
        for(int j = left ; j <= right ; j++ ) 
            nums[j] = tmp[j - left]; 
    }

数组中的逆序对

题目解析

算法原理

解法一：暴力枚举

固定其中一个数，在这个数后面区间找比这个数小的数，来构成一个逆序对；使用两层 for 循环即可，但是会超时；

解法二：归并排序

算法原理

(1) 左半部分 + 右半部分 + 一左一右

本质还是暴力枚举，逆序对个数 = a + b + c

(2) 左半部分 + 左排序 + 右半部分 + 右排序 + 一左一右 + 排序

对左右两边排好序，再一左一右挑数组成逆序对，并不影响结果：

本题为什么可以利用归并排序解决问题？

并且通过这步操作，我们得出本题最终的解法，就是需要通过归并排序求逆序对个数；

我们在找出左右两边的逆序对个数时，先对两边排序再一左一右，会非常快：

一左一右查找逆序对策略优化

我们在之前找左右两边区域的所有逆序对时，就刻意地对左右两边进行排序，找完左右两边的逆序对时，nums 的两边区域的顺序已经被排序成升序，此时我们需要一左一右寻找逆序对；

策略一 : 判断 nums[cur1]>nums[cur2] + 升序

统计一左一右逆序对的固定策略

固定 cur2, 只要 cur1 一移动到 nums[cur1]>nums[cur2]位置，就统计符合要求的区间的元素个数，cur2++；

假设我们固定 cur2，要在左边找有多少个比 nums[ cur2 ] 大的元素

令 cur1 在左边区域中从左到右扫描，找出第一个 nums[ cur1 ] > nums[ cur2 ] 的 cur1

(1) nums[ cur1 ] <= nums[ cur2 ]

我们直接让 cur1++ ，并且为了让数组有序，我们要把 nums[cur1] 放入辅助数组中，方便后续排序，继续往后找即可：

(2) nums[ cur1 ] > nums[ cur2 ]

出现这种情况，对于两边升序区域，当 nums[ cur1 ] > nums[ cur2 ] ，说明此时 cur1 指向的元素，是左边区域第一个比 nums[ cur2 ] 大的元素；cur1 后面所有元素都比 nums[ cur2 ] 大

也因为是升序排序，在 cur1 一走到第一个合法位置时， ret += mid - cur1 + 1即可；

本轮 cur2 的所有能拿到的逆序对就已经统计好了，此时 cur2++ 即可；

如果策略一使用降序排列会出现的问题

对于降序排序，我们依旧是需要固定 cur2；

我们依旧需要采取【只要 cur1 一移动到 nums[cur1]>nums[cur2] 的位置，就统计符合这个要求的区间的元素个数】的策略

如下图的情况：

因为是降序排序的，所以 cur2 不能因为 nums[cur1]>nums[cur2] 就马上++ ，还必须看下一个 cur1 能否满足 nums[cur1]>nums[cur2] :

因为采取了【只要 cur1 一移动到 nums[cur1]>nums[cur2] 的位置，就统计符合这个要求的区间的元素个数】的策略，因此就会造成大量的重复计算；

cur1 一移动，判断是否大于 cur2，如果判断成立，马上就让 ret += cur1 - left +1，所以会出现多次重复计算；

所以使用策略一，在排序数组时不能用降序，避免大量重复计数，所以只能用升序；

策略二 : nums[cur1]

统计一左一右逆序对的固定策略

固定 cur2, 只要 cur1 一移动到 nums[cur1]位置，就统计符合要求的区间的元素个数，cur2++；

编写代码

策略一 + 升序

准备工作

主逻辑

策略二 + 降序

计算右侧小于当前元素的个数

题目解析

算法原理

这道题的本质，还是类似于求逆序对的个数；

解法：归并排序（左半部分 + 左排序 + 右半部分 + 右排序 + 一左一右 + 排序）

一左一右策略：nums[ cur1 ] < nums[ cur2 ] + 降序（上一题策略二）

nums[ cur1] <= nums[ cur2 ] ，cur2++；修改对应的辅助数组；
nums[ cur1 ] > nums[ cur2 ]，把 nums[ cur1 ] 对应 ret[ ] 下标的元素加上 right - cur2 + 1；修改对应的辅助数组；

处理细节问题

我们要找到 nums[ cur1 ] 对应 ret[ ] 的对应下标，因为我们排序的时候，下标已经乱了；

如果我们使用哈希表来设置 < nums 元素 , ret 下标 > 的映射，如果 nums有重复元素，哈希表无法存储重复元素，就无法解决下标混乱的问题；

所以我们设置与 nums 同等规模的数组 index[ ]，表示 nums 未排序时元素的原始下标，

不管 nums 因为排序，里面的元素怎么移动，index 对应的元素绑定移动：

那如何让 nums[] 和 index[] 绑定移动呢？我们需要创建两个辅助数组 tmp，来让它们同步移动；

最后，让 ret [ index[ i ] ] +=  right - cur2 + 1 即可；

编写代码

准备工作

核心逻辑

报错原因：对于降序排序的一左一右操作不熟练，判断条件写错了；

翻转对

拓展

直接插入排序

选择排序

冒泡排序

快速选择算法

拓展

评论记录：