力扣hot100道【贪心算法后续解题方法心得】（三）

十四、贪心算法

关键解题思路

理解贪心的本质是：选择每一阶段的局部最优，从而达到全局最优。

贪心算法一般分为如下四步：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

1、买卖股票的最佳时机

1）解题关键思路

• 在最低价格买入，最高利润卖出（思路是错误的) 如：[2,100,1,5]可能在最低价格1买入，然后5卖出吗，不可能。
• 总的来说应该是在遍历每一天中后续相邻天数的净利润相加，净利润<0舍弃重新开始得到最大值。

2）代码

 public int maxProfit(int[] prices) {
        int maxSum = 0;
        int sum = 0;
        for (int i = 0; i < prices.length; i++) {
            sum += prices[i];
            if (sum < 0) sum = 0;
            maxSum = Math.max(maxSum, sum);
        }
        return maxSum;
    }

3）分析

• 求每一天的净利润相加，得到的就是最大值，<0就直接舍弃从下一个元素开始继续重复上述操作。

2、跳跃游戏

1）解题思路与关键难点

• 就是跳到哪里进行覆盖，如果覆盖是数组长度索引最大，直接可以

关键难点
知道思路是什么，但却写不出代码，不知道应该怎么写代码
解答

• 每次移动只能在 cover 的范围内移动，每移动一个元素，cover 得到该元素数值（新的覆盖范围）的补充，让 i 继续移动下去。
• 贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
  1）解题关键思路
• coverRange覆盖达到nums.length-1
• 每次遍历最大遍历只能到达converRange
  2）代码

// 思路：求每个下标下的最大覆盖位置
    public boolean canJump(int[] nums) {
        if (nums.length ==1) return true;
        int coverRange = 0;
        // 为什么是相等？
        // 因为可以跳到该覆盖索引的下标下
        for (int i = 0; i <= coverRange; i++) {
            coverRange = Math.max(coverRange, i + nums[i]);
            if (coverRange >= nums.length -1) return true;
        }
        return false;
    }

3）分析

• 判断coverRange覆盖达到nums.length-1返回true
• 每次遍历最大遍历只能到达converRange，并在每次更新converRange的最大赋值。

3、跳跃游戏 | |

1）解题关键
要想清楚什么时候步数才一定要加一呢？
关键点：
所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数！

这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖
2）代码

// 尽可能的选择跳最远的
    public int jump(int[] nums) {
        if (nums.length == 1) return 0;

        int nextCoverRange = 0;
        int currentCover = 0;
        int res = 0;
        for (int i = 0; i <= nextCoverRange ; i++) {
            nextCoverRange = Math.max(nextCoverRange , i + nums[i]);
            if (nextCoverRange >= nums.length - 1) {
                res++;
                break;
            }
            // 在当前覆盖范围内寻找最大覆盖范围，
            // 如果走完当前覆盖范围计算下一步最大的覆盖范围还没有到达终点，
            // 再加一步进行移动
            if (i == currentCover) {
            // 开始跳跃，跳跃范围是nextCoverRange 
                res++;
                currentCover = nextCoverRange ;
            }
        }
        return res;
    }

3）分析

• 在当前覆盖索引寻找nextCoverRange 最大值是否覆盖nums.length - 1，如果覆盖直接+1退出，如果遍历结束还没有就进行跳转到下一个nextConverRange中的某个位置继续遍历。

4、划分字母区间

1）关键解题思路
题目要求同一个字母只能出现在一个片段里面，故而解题关键就是找出同一个字母出现的最远的索引即可。
2）代码

public List<Integer> partitionLabels(String s) {
        // 记录每个字母最后的索引位置
        int[] last = new int[26];
        char[] chars = s.toCharArray();
        // 获取每个字母最后的起始位置
        for (int i = 0; i < chars.length; i++) {
            last[chars[i] - 'a'] = i;
        }
        List<Integer> list = new ArrayList<>();
        int end = 0;
        int start = 0;
        for (int i = 0; i < chars.length; i++) {
            // 什么时候加入list？
            end = Math.max(end, last[i]);
            if (i == end) {
                list.add(end - start + 1);
                start = end + 1;
            }
        }
        return list;
    }

3）分析

• 最重要一步就是记录同一个字母的最后索引位置，然后遍历等到i == end时候收集一个区间的结果

十五、动态规划

什么是动态规划？

动态规划（Dynamic Programming，简称DP）是一种解决具有重叠子问题和最优子结构特性的问题的方法。其核心思想是将一个复杂的问题分解成一系列更小的子问题，并通过存储这些子问题的解来避免重复计算，从而提高算法效率，即为利用空间存储已经计算过的值，达到空间换时间。

关键解题思路和步骤

思路：
将一个复杂的问题分解成一系列更小的子问题，通过存储这些子问题的解进行后续问题的解，避免重复计算。

步骤：

1. 确定dp数组以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

为什么是先进行递推公式的确定再进行初始化呢？

因为一些情况是递推公式决定了dp数组要如何初始化！

1、打家劫舍

1）解题关键

1. 确定dp数组含义
2. 根据第i家偷还是不偷，确定递推公式，如果偷：dp[i] = dp[i-2] + num[i]，不偷就是：dp[i] = dp[i-1],因为是求最大，故而递推公式为：dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
3. 初始化，根据递推公式可知，dp[0] = 0,dp[1] = nums[0]必偷。
4. 确定遍历顺序，从0开始偷进行计算。
   2）代码

 public int rob(int[] nums) {
        int length = nums.length;
        if ( length == 0) return 0;
        int[] dp = new int[length + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i-1]);
        }
        return dp[length];
    }

3）分析同1）

2、01背包问题

1）解题关键
2）关键优化代码

  // 外层循环遍历每个类型的研究材料
        for (int i = 0; i < M; i++) {
            // 内层循环从 N 空间逐渐减少到当前研究材料所占空间
            for (int j = N; j >= costs[i]; j--) {
                // 考虑当前研究材料选择和不选择的情况，选择最大值
                dp[j] = Math.max(dp[j], dp[j - costs[i]] + values[i]);
            }
        }

3）分析

• 确定遍历顺序，背包遍历顺序为倒叙，防止同一个物品被添加多次。

3、完全平方式

1）解题关键

• 动态规划5个步骤，并类比完全背包和01背包解法。
• 无非就是1，4，9这些是物品重量，然后n是背包容量，可以重复添加，求最小次数加满背包。
• 遍历顺序就是先遍历物品再遍历背包
• 类比完全背包问题
  2）代码

 public int numSquares(int n) {
        // 把平方当作物品（无限使用），然后n代表背包容量
        // 刚好装满这个背包最少需要多少个物品
        // dp[i]表示装满容量为i的背包最少需要多少个物品
        int[] dp = new int[n + 1];
        // 因为求的是min，防止递推公式的值被初始值覆盖
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 1; i*i <= n; i++) { //遍历物品
            for (int j = i*i; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }

3）分析

• 完全背包问题，无非就是一个物品可以重复添加达到背包被装满为止的最大值。

4、零钱兑换

解法同上面一样

5、单词拆分

1）关键解题思路

dp[i]：表示i长度的字符串能否被若干个单词组成。故而推导公式 dp[j] && wordDictSet.contains(s.substring(j, i))
-> dp[i] = true

2）代码

 // 典型背包问题 把wordDict当作物品即可
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        int sLength = s.length();
        // 代表容量背包的最大值
        boolean[] dp = new boolean[sLength + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                }
            }

        }
        return dp[sLength];
    }

6、最长递增子序列

1）关键解题步骤
dp[i]:含义代表的是对应的索引下标的最长递增子序列。
2）代码

 public int lengthOfLIS(int[] nums) {
        // 以nums[i]为结尾的最长递增子序列
        int[] dp = new int[nums.length];
        // 最低要求都是1
        Arrays.fill(dp, 1);
        int res = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        // 结果不一定是对应的结尾可能是之前的
        return res;
    }

3）分析
如果nums[i] > nums[j]，代表有一个索引下标符合条件，不断遍历寻找最大值。有点类似单词拆分题目的解法

7、乘积最大子序列

1）解题关键
定义两个变量 iMax 和 iMin分别用于记录[0,i)为止的最大乘积和最小乘积。这是因为负数乘以最大值可能会变成最小值，而负数乘以最小值可能会变成最大值。同时，还需要一个变量 max来记录全局的最大乘积。
2）代码

 public int maxProduct(int[] nums) {
        // 设置最大值为初始值
        int max = Integer.MIN_VALUE,imax = 1, imin = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) {
                int temp = imax;
                imax = imin;
                imin = temp;
            }
            imax = Math.max(imax * nums[i], nums[i]);
            imin = Math.min(imin * nums[i], nums[i]);
            max = Math.max(imax, max);
        }
        return max;
    }

8、分割等和子集

1）关键解题思路

• 求相同的等和，故而进行累加sum，判断sum % 2 != 0 。
• target = sum / 2，此时可以看作是背包容量，数组里面的元素就是物品，无非就是从添加物品能否填满背包。
  2）代码

 public boolean canPartition(int[] nums) {
        int sum = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        int[] dp = new int[target + 1];
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = target; j >=nums[i]  ; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return target == dp[target];
    }

十六、多为动态规划

1、不同路径

1）解题思路
某一个网格的路径 = 左边网格右走一步 + 上边网格下走一步。
定义 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
2）代码

//2.空间优化
    public int uniquePaths(int m, int n) {
        // dp[i][j]表示到达(i,j)的路径数
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // dp[j]的表示当前这一行 的dp[j]  dp[j-1]表示上一行的dp[j]
                dp[j] = dp[j] + dp[j - 1];
            }
        }
        return dp[n - 1];
        // 初始化第一列}
    }

2、最小路径和

1）关键解题思路
某网格最小值无非就是公式： // grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j] ；
通过累加改变每个网格的值，此时网格的值代表所有路径下最小的和，也就是直接在grid[i][j] 上面直接修改。
2）代码

   public int minPathSum(int[][] grid) {
        // grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j] ；
        // 原 grid 矩阵元素中被覆盖为 dp 元素后（都处于当前遍历点的左上方），不会再被使用到
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (i == 0 && j == 0) continue;
                else if (i == 0) grid[i][j] += grid[i][j - 1];
                else if ((j == 0)) grid[i][j] += grid[i - 1][j];
                else grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }

        }
        return grid[grid.length - 1][grid[0].length - 1];
    }

3、最长回文子串

1）解题关键思路
解题关键方法：中心扩散法

如何理解中心扩散法？
它的基本思想是从每一个可能的“中心”开始，向两边扩展，直到不能再扩展为止。
即为从每一个位置出发，向两边扩散。遇到不是回文时候就直接结束。
例如：“babad”
第二个b位置：2，出发最长回文子串为多少。怎么找？

1. 先往左寻找与当期位置相同的字符，直到不相等。
2. 往右寻找与当前位置相同的字符，直到不相等
3. 最后就进行左右双向扩散，直到左和右不相等。

如图所示

每个位置向两边扩散都会出现一个窗口大小（len）。如果 len>maxLen(用来表示最长回文串的长度）。则更新 maxLen 的值。
因为我们最后要返回的是具体子串，而不是长度，因此，还需要记录一下 maxLen 时的起始位置（maxStart），即此时还要 maxStart=len。

2）代码

 public String longestPalindrome(String s) {
        int length = s.length();
        if (length == 1) return s;
        // 定义中心扩散中心的左右边界
        int left = 0;
        int right = 0;
        // 当前中心点的回文字串最大长度
        int len = 1;
        // 某结果中心点的最大回文字串的起始索引
        int maxStart = 0;
        // 该结果最大的回文字串长度
        int maxLen = 0;
        for (int i = 0; i < length; i++) {
            // 先进行左右扩散
            left = i-1;
            right = i+1;
            // 左扩散
            while (left >= 0 && s.charAt(left) == s.charAt(i)) {
                left--;
                len++;
            }
            // 右扩散
            while (right < length && s.charAt(right) == s.charAt(i)) {
                right++;
                len++;
            }
            // 左右扩散
            while (right < length && left >= 0 && s.charAt(right) == s.charAt(left)) {
                left--;
                right++;
                len += 2;
            }
            // 最终得到以该i位置为中心的回文字串长度
            if (len > maxLen) {
                maxLen = len;
                // 记录起始位置
                maxStart = left+1;
            }
            // 重置len 为下一个准备
            len = 1;
        }
        return s.substring(maxStart, maxStart + maxLen);
    }

3）分析

• 最为关键的一点就是 ： left = i-1;right = i+1;先提前扩散好，为后续左，右，左右扩散s.charAt(left) == s.charAt(i)等比较做好准备。
• 因为提前左右扩散，所以最终的left是不符合的，而left+1才是回文子串的起始位置。

4、最长公共子序列

1）解题关键

• 求公共最长子序列，就是利用dp数组存放之前已经计算过的值依次计算到text1，text2结尾得出结果。
• 利用二维数组dp[i][j] 表示【0 - t1-1】区间和【0 - t2-1】区间的最长公共子序列，依次存储计算过的值，最终得到结果：dp[t1][t2];

2）代码

 public int longestCommonSubsequence(String text1, String text2) {
        int t1 = text1.length();
        int t2 = text2.length();
        // 代表0 - t1-1和0 - t2-1的最长公共子序列
        int[][] dp = new int[t1 + 1][t2 + 1];
        for (int i = 1; i <= t1; i++) {
            for (int j = 1; j <= t2; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
               else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[t1][t2];
    }

3）分析

• 当两个text1.charAt(i - 1) == text2.charAt(j - 1)代表的是最后一个字母相等，此时+1，当不相等时候，等于text1-1和text2或者text1和text2-1比较得到结果。

5、编辑距离

1）解题关键
本题咋一看完全没有思路，其实解决本题的思路主要就是定义二维的动态dp，并理解dp[i][j]：[0，i-1] [0，j-1]区间的最少操作数，思路其实和上一题最长公共子序列长度差不多，无非就是相等时候不用操作，不相等时候进行增删改。
2）代码

  public int minDistance(String word1, String word2) {
        int w1 = word1.length();
        int w2 = word2.length();
        char[] W1 = word1.toCharArray();
        char[] W2 = word2.toCharArray();
        // dp[i][j]：word1[0..i-1]和word2[0..j-1]的最小编辑距离
        int[][] dp = new int[w1 + 1][w2 + 1];
        // 初始化
          // 初始化
        for (int i = 0; i <= w1; i++) {
            dp[i][0] = i;
        }  for (int j = 0; j <= w2; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= w1; i++) {
            for (int j = 1; j <= w2; j++) {
                // 相等 等于之前
                if (W1[i - 1] == W2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // dp[i - 1][j]：word1删除一个元素，那么就是以下标i - 2为结尾的word1与j-1为结尾的word2的最近编辑距离 再加上一个操作。
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]) ) + 1;
                }
            }
        }
        return dp[w1][w2];
    }

3）分析
无非就是理解递推公式，相等时候：不需要操作直接得出结果dp[i][j] = dp[i - 1][j - 1];
不相等时候： dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]) ) + 1;对i索引-1操作或者j-1索引操作，最后替换 i-1,j-1操作，求三个操作最小值。

十七、技巧

十八、排序算法

概述

1、冒泡排序（Bubble Sort）

冒泡排序（Bubble Sort）：通过重复遍历要排序的列表，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
1）关键解题思路
2）代码

/* 冒泡排序 */
    void bubbleSort(int[] nums) {
        int length = nums.length;
        if(length<2) return;
        // 只需要遍历length -1遍即可
        for (int i = length -1 ; i >0 ; i--) {
            boolean flag = false;
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j + 1] = temp;
                    // 每次交换都表示有
                    flag = true;
                }
            }
            // 说明没有进行交换 已经达到有序直接退出
            if (!flag) break;
        }
    }

3）分析
1、时间复杂度
最好情况o（n），最坏情况o（n*n）
2、空间复杂度
o（1）

2、选择排序（Selection Sort）

选择排序（Selection Sort）：在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
1）关键解题思路
2）代码

/* 选择排序 */
    void selectionSort(int[] nums) {
        int length = nums.length;
        if(length<2) return;
        // 只需要遍历length -1遍即可
        for (int i = 0; i < length-1; i++) {
            int minIndex = i;
            for (int j = i; j < length; j++) {
                if (nums[minIndex] > nums[j]) {
                    // 如果直接这样是无法记录最小值所在的索引位置的
                    minIndex = j;
                }
            }
            int temp = nums[i];
            nums[i] = nums[minIndex];
            nums[minIndex] = temp;
        }
            // 说明没有进行交换 已经达到有序直接退出
    }

3）分析
1、时间复杂度
o（n*n）
2、空间复杂度
o（1）

3、插入排序

插入排序（Insertion Sort）：在已有的有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
1）关键解题思路
2）代码

 /* 插入排序 */
    void insertionSort(int[] nums) {
        int length = nums.length;
        if(length<2) return;
        // 为什么从索引1开始，类似打牌一样，摸到的第一张牌不需要进行排序
        for (int i = 1; i < length; i++) {
            // 待排序元素
            int base = nums[i];
            // 待排序的有序最后的区间
            int j = i - 1;
            // 内循环：将 temp从后向前扫描插入到已排序区间 [0, i-1] 中的正确位置
            while (j >= 0 && base < nums[j]) {
                // 将元素向后面移动
                nums[j + 1] = nums[j];
                j--;
            }
            // 退出循环，此时j是刚好比bse小的 找到插入的索引位置，将其插入
            nums[j + 1] = base;
        }
    }

3）分析
1、时间复杂度

• 最佳情况为o（n）最坏情况o（n*n）
  2、空间复杂度
  o（1）
  3、理解关键解题思路
  在已排序序列中从后向前扫描，找到相应位置并插入。

4、快速排序（Quick Sort）！！！

快速排序（Quick Sort）：也是基于分治法的排序算法，通过一个“基准数”（pivot）将数组分成两部分，左边部分的所有元素都小于基准数，右边部分的所有元素都大于基准数，然后递归地对这两部分进行排序。
1）解题关键思路
选定一个基准数，大于基准数的就排在右边，小于基准数的就排在左边，重复操作
2）代码

 /* 快速排序 */
    void quickSort(int[] nums, int left, int right) {
        if (left >= right) return;
        int baseIndex = partition(nums, left, right);
        quickSort(nums,left,baseIndex-1);
        quickSort(nums,baseIndex+1,right);
    }
    int partition(int[] nums, int left, int right) {
        // 选取第一个元素作为基准
        int base = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= base) {
                right--;
            }
            // 进行左右交换
            // 将较小的元素放到左边
            nums[left] = nums[right];
            while (left < right && nums[left] <= base) {
                left++;
            }
            // 将较大的元素放到右边
            nums[right] = nums[left];
        }
        // 最后将基准元素放到正确的位置
        nums[left] = base;
        return left;
    }

3）分析

• 选取一个以左边为基准的元素，然后right来移动寻找小于base的数字，然后放到左边 ：nums[left] = nums[right];
• 接下来就是同理可得
  1、时间复杂度为 （nlogn）
  2、空间复杂度为o（n）

5、归并排序（Merge Sort）

归并排序（Merge Sort）：采用分治法的一个典型应用，将已经有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
1）关键解题思路

• 划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。
• 合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束。

2）代码

  /* 归并排序 */
    void mergeSort(int[] nums, int left, int right) {
        // 终止条件
        if (left >= right) return;
        // 递归进行划分阶段
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        // 合并左右子数组
        // 左子数组区间为 [left, mid],
        // 右子数组区间为 [mid+1, right]
        merge(nums, left, mid, right);
    }

    private void merge(int[] nums, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        // 左数组起始索引
        int i = left;
        // 右数组起始索引
        int j = mid + 1;
        int k = 0;
        // 开始进行左右子数组排序
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i];
            }else{
                temp[k++] = nums[j];
            }
        }
        // 最后将剩余的元素复制到临时数组中
        while (i<=mid){
            temp[k++] = nums[i++];
        }while (j<=right){
            temp[k++] = nums[j++];
        }
        // 将临时数组temp元素复制回来到原来区间
        for (int l = 0; k < temp.length; l++) {
            nums[left + l] = temp[l];
        }
    }

3）分析

• 主要就是对数组进行不断mid分为左右子数组，然后再进行合并
• 合并阶段主要就是对左右子数组进行合并。
  1、时间复杂度
  o(nlogn)
  2、空间复杂度
  o(n)

6、堆排序（Heap Sort）

堆排序（Heap Sort）：利用堆这种数据结构设计的一种排序算法，首先将待排序的数组构建成大顶堆或小顶堆，然后将堆顶元素与末尾元素交换，再重新调整堆，直到排序完成。

1）解题关键
2）代码

/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
void siftDown(int[] nums, int n, int i) {
    while (true) {
        // 判断节点 i, l, r 中值最大的节点，记为 ma
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma])
            ma = l;
        if (r < n && nums[r] > nums[ma])
            ma = r;
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if (ma == i)
            break;
        // 交换两节点
        int temp = nums[i];
        nums[i] = nums[ma];
        nums[ma] = temp;
        // 循环向下堆化
        i = ma;
    }
}

/* 堆排序 */
void heapSort(int[] nums) {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for (int i = nums.length / 2 - 1; i >= 0; i--) {
    // 进行节点调整
        siftDown(nums, nums.length, i);
    }
    // 从堆中提取最大元素，循环 n-1 轮
    for (int i = nums.length - 1; i > 0; i--) {
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        int tmp = nums[0];
        nums[0] = nums[i];
        nums[i] = tmp;
        // 以根节点为起点 调整剩余部分重新形成大顶堆
        // siftDown 操作的目的是调整堆中某个节点，使其成为一个有效的堆 
        // 以为0的值改变了，所以进行0节点调整成堆
        siftDown(nums, i, 0);
    }
}

7、希尔排序（Shell Sort）

希尔排序（Shell Sort）：是插入排序的一种更高效的改进版本，也称缩小增量排序，通过将原始列表分割成多个子列表分别进行插入排序来提高效率。
1）关键解题思路
理解分组的含义，以及插入排序的关键解题
2）代码

 public static void shellSort(int[] nums) {
        int length = nums.length;
        if(length<2) return;
        // 进行分组
        for (int gap = length / 2; gap >= 1; gap /= 2) {
            // 对每个分组后的子序列进行插入排序
            for (int i = gap ; i < length; i++) {
                int temp = nums[i];
                int j = i - gap;
                while (j >= 0 && nums[j] > temp) {
                    nums[j + gap] = nums[j];
                    j -= gap;
                }
                nums[j + gap] = temp;
            }
        }
    }

3）分析
1、时间复杂度

• 最佳情况为：O(n log n) 最坏情况O(n^(3/2))
  2、空间复杂度
  o（1）
  3、理解关键解题思路
  在已排序序列中从后向前扫描，找到相应位置并插入。

8、桶排序（Bucket Sort）

桶排序（Bucket Sort）：工作原理是将数组分到有限数量的桶里。每个桶再分别排序（有可能再使用别的排序算法或是递归使用桶排序）。
1）关键解题思路

将对应的元素放到对应的桶上面去，然后进行在每个桶进行排序。
2）代码

 /* 桶排序 */
    void bucketSort(float[] nums) {
       // 初始化 k = n/2个桶，预期向每个桶分配2个元素
        int k = nums.length / 2;
        List<List<Float>> buckets = new ArrayList<>();
        // 初始化桶
        for (int i = 0; i < k; i++) {
            buckets.add(new ArrayList<>());
        }
        for (float num : nums) {
            // 将元素映射到每一个桶去
            int bucketIndex = (int) (num * k);
            buckets.get(bucketIndex).add(num);
        }
        // 对桶里面的每个元素排序
        for (List<Float> bucket : buckets) {
            Collections.sort(bucket);
        }
        // 合并每个排序好的桶元素
        int index = 0;
        for (List<Float> bucket : buckets) {
            for (Float aFloat : bucket) {
                nums[index++] = aFloat;
            }
        }
    }

9、基数排序（Radix Sort）

基数排序（Radix Sort）：根据键值的每位数字来分配桶，从最低有效位开始排序，然后收集；再从次低位开始排序…以此类推，直到最高有效位。

其他相关内容

1. 哈希-矩阵解题心得（一）：https://blog.csdn.net/a147775/article/details/143558612

2. 链表-堆解题心得（二）：https://blog.csdn.net/a147775/article/details/144218993