• 算法分析与设计之分而治之篇（1）

    一、归并排序

    • 问题背景：杠铃增重问题，每位参赛运动员向组委会提交排好序得三次举重量，为了便于杠铃得拆卸，组委会需对所有试举重量递增排序。

    •  已学过的解决方案
      • 选择排序：从待排序元素中迭代选出最小值并排序
      • 插入排序：依次将每个元素插入到已排序序列中

    •  分析杠铃增重问题
      • 特点：局部有序
      • 快速合并：比较两个有序数组当前最小元素，将较小者逐一合入新数组
      • 后续策略：
        • 逐一合并
        • 两两合并
    • 杠铃增重问题代码实现
    1. package com.tiger.study;
    2.  
    3.  
    4. import java.util.ArrayList;
    5. import java.util.List;
    6.  
    7. public class MergeSort {
    8.     public static void main(String[] args) {
    9.         // 杠铃增重问题
    10.         int[] l1 = {4, 10, 19};
    11.         int[] l2 = {13, 16, 18};
    12.         int[] l3 = {5, 9, 12};
    13.         int[] l4 = {11, 15, 17};
    14.  
    15.         int[] mergeList = merge(merge(l1, l2), merge(l3, l4));
    16.         for (int i = 0; i < mergeList.length; i++) {
    17.             System.out.println(mergeList[i]);
    18.         }
    19.     }
    20.  
    21.     private static int[] merge(int[] a, int[] b) {
    22.         int[] tempList = new int[a.length + b.length];
    23.         int a_head = 0, b_head = 0;
    24.         int count = 0;
    25.         while (a_head < a.length && b_head < b.length) {
    26.             if (a[a_head] <= b[b_head]) {
    27.                 tempList[count] = a[a_head++];
    28.                 count++;
    29.             } else {
    30.                 tempList[count] = b[b_head++];
    31.                 count++;
    32.             }
    33.         }
    34.         if (a_head < a.length) {
    35.             for (int i = a_head; i < a.length; i++) {
    36.                 tempList[count] = a[i];
    37.                 count++;
    38.             }
    39.         } else if (b_head < a.length) {
    40.             for (int i = b_head; i < b.length; i++) {
    41.                 tempList[count] = b[i];
    42.                 count++;
    43.             }
    44.         }
    45.  
    46.         return tempList;
    47.     }
    48.  
    49.  
    50. }

    •  从杠铃增重问题转换为排序问题
      • 相较于杠铃增重问题而言，排序问题的问题输入有所改变，排序问题中以完整的数组输入，同时局部有序缺失。

    •  针对于问题输入的变化，我们可以将问题分解，当输入长度为1时，数组天然有序，这项可以处理局部有序确实的变化。

    • 通过两两合并构建有序数组

    • 归并排序算法流程：
      • 将数组A[1,n]排序问题分解为A[1,\left \lfloor \frac{n}{2} \right \rfloor]和A[\left \lfloor \frac{n}{2} \right \rfloor + 1,n]的排序问题
      • 递归解决子问题得到两个有序的子序列
      • 将两个有序的子数组合并为一个有序数组

    •  分而治之法的一般步骤

    •   归并排序代码实现
    1. package com.tiger.study;
    2.  
    3.  
    4. public class MergeSort {
    5.     public static void main(String[] args) {
    6.         // 归并排序
    7.         int[] arr = {24, 17, 40, 28, 13, 14, 22, 32, 40, 21, 48, 4, 47, 8, 37, 18};
    8.         int[] result = new int[arr.length];
    9.         mergeSort(arr, 0, arr.length - 1, result);
    10.         for (int i = 0; i < result.length; i++) {
    11.             System.out.println(result[i]);
    12.         }
    13.     }
    14.  
    15.     // 递归方法
    16.     private static void mergeSort(int[] arr, int left, int right, int[] result) {
    17.         // 递归结束条件
    18.         if (right == left) return;
    19.         int mid = (right + left) / 2;
    20.  
    21.         mergeSort(arr, left, mid, result);
    22.         mergeSort(arr, mid + 1, right, result);
    23.         merge(arr, left, right, result);
    24.     }
    25.  
    26.     // 合并有序的部分
    27.     private static void merge(int[] arr, int left, int right, int[] result) {
    28.         int mid = (right + left) / 2;
    29.         int left_head = left, right_head = mid + 1, result_index = left;
    30.         while (left_head <= mid && right_head <= right) {
    31.             if (arr[left_head] <= arr[right_head]) {
    32.                 result[result_index++] = arr[left_head++];
    33.             } else {
    34.                 result[result_index++] = arr[right_head++];
    35.             }
    36.         }
    37.  
    38.         if (left_head <= mid) {
    39.             for (int i = left_head; i <= mid; i++) {
    40.                 result[result_index++] = arr[i];
    41.             }
    42.         }
    43.  
    44.         if (right_head <= right) {
    45.             for (int i = right_head; i <= right; i++) {
    46.                 result[result_index++] = arr[i];
    47.             }
    48.         }
    49.  
    50.         for (int i = left; i <= right; i++) {
    51.             arr[i] = result[i];
    52.         }
    53.  
    54.     }
    55.  
    56.  
    57. }

    二、递归式求解

    • 递归树法：用树的形式表示抽象递归

    •  代入法：这种方法比较看直觉，要先猜一个，然后去证明
    • 主定理法：这个方法有一堆的推导，然后我们作题的话只要记住下面的形式就行了

    •  递归式分析方法比较

     三、最大子数组问题

    • 问题描述：数组X中有若干个子数组，每个子数组为X中的一段序列，寻找X中最大的非空子数组。
    1. package com.tiger.study;
    2.  
    3. // 最大子数组问题：数组X中有若干个子数组，每个子数组为X中的一段序列，寻找X中最大的非空子数组
    4.  
    5.  
    6. import java.util.ArrayList;
    7. import java.util.Arrays;
    8.  
    9. public class MaxSubArray {
    10.     public static void main(String[] args) {
    11.         int[] arr = {1, -2, 4, 5, -2, 8, 3, -2, 6, 3, 7, -1};
    12.  
    13.         // 暴力解法
    14.         ArrayList maxSubArray = new ArrayList<>();
    15.         int maxValue = Integer.MIN_VALUE;
    16.         for (int i = 0; i < arr.length; i++) {
    17.             int temp = 0;
    18.             for (int j = i; j < arr.length; j++) {
    19.                 temp += arr[j];
    20.                 if (temp >= maxValue) {
    21.                     maxValue = temp;
    22.                     maxSubArray.clear();
    23.                     for (int k = i; k <= j; k++) {
    24.                         maxSubArray.add(arr[k]);
    25.                     }
    26.                 }
    27.             }
    28.         }
    29.         for (int i = 0; i < maxSubArray.size(); i++) {
    30.             System.out.println(maxSubArray.get(i));
    31.         }
    32.  
    33.         // 分治策略
    34.         int[] maxSubArray1 = maxSubArray(arr, 0, arr.length - 1);
    35.         for (int i = 0; i < maxSubArray1.length; i++) {
    36.             System.out.println(maxSubArray1[i]);
    37.         }
    38.  
    39.     }
    40.  
    41.     private static int[]  maxSubArray(int[] arr, int low, int high) {
    42.         if (low == high) {
    43.             return new int[]{arr[low]};
    44.         } else {
    45.             int mid = (low + high) / 2;
    46.             int[] s1 = maxSubArray(arr, low, mid);
    47.             int[] s2 = maxSubArray(arr, mid + 1, high);
    48.             int[] s3 = crossingSubArray(arr, low, mid, high);
    49.             int[] sMax = max(s1, s2, s3);
    50.             return sMax;
    51.         }
    52.     }
    53.  
    54.     private static int[] crossingSubArray(int[] arr, int low, int mid, int high) {
    55.         int left_head = mid, right_head = mid + 1;
    56.         int temp = 0;
    57.         int max = Integer.MIN_VALUE;
    58.         for (int i = mid; i >= low; i--) {
    59.             temp += arr[i];
    60.             if (temp > max) {
    61.                 left_head = i;
    62.                 max = temp;
    63.             }
    64.         }
    65.         temp = 0;
    66.         max = Integer.MIN_VALUE;
    67.         for (int i = mid + 1; i <= high; i++) {
    68.             temp += arr[i];
    69.             if (temp > max) {
    70.                 right_head = i;
    71.                 max = temp;
    72.             }
    73.         }
    74.         int[] result = new int[right_head - left_head + 1];
    75.         for (int i = left_head, j = 0; i <= right_head && j < result.length; i++, j++) {
    76.             result[j] = arr[i];
    77.         }
    78.         return result;
    79.     }
    80.  
    81.     private static int[] max(int[] s1, int[] s2, int[] s3) {
    82.         int sum1 = Arrays.stream(s1).sum();
    83.         int sum2 = Arrays.stream(s2).sum();
    84.         int sum3 = Arrays.stream(s3).sum();
    85.         int max = Math.max(Math.max(sum1, sum2), sum3);
    86.         if (max == sum1) {
    87.             return s1;
    88.         } else if (max == sum2) {
    89.             return s2;
    90.         } else {
    91.             return s3;
    92.         }
    93.     }
    94. }

    四、逆序对计数问题

    • 问题描述：数组中存在下标小的值比下标大的值大的称为逆序对，求数组中一共有多少个逆序对？
    1. package com.tiger.study;
    2.  
    3. // 逆序对计数问题：数组中共有多少个逆序对
    4.  
    5.  
    6. public class CountingInversions {
    7.     public static void main(String[] args) {
    8.         int[] arr = {13, 8, 10, 6, 15, 18, 12, 20, 9, 14, 17, 19};
    9.         System.out.println(countingInversions(arr));
    10.  
    11.         System.out.println(countInver(arr, 0, 2));
    12.     }
    13.  
    14.     // 暴力方法
    15.     private static int countingInversions(int[] arr) {
    16.         int count = 0;
    17.         for (int i = 0; i < arr.length - 1; i++) {
    18.             for (int j = i + 1; j < arr.length; j++) {
    19.                 if (arr[i] > arr[j]) {
    20.                     count++;
    21.                 }
    22.             }
    23.         }
    24.         return count;
    25.     }
    26.  
    27.  
    28.     // 分治策略
    29.     private static int countInver(int[] arr, int left, int right) {
    30.         if (left == right) {
    31.             return 0;
    32.         }
    33.         int mid = (left + right) / 2;
    34.         int s1 = countInver(arr, left, mid);
    35.         int s2 = countInver(arr, mid + 1, right);
    36.         int s3 = mergeCount(arr, left, mid, right);
    37.         int s = s1 + s2 + s3;
    38.         return s;
    39.     }
    40.  
    41.     private static int mergeCount(int[] arr, int left, int mid, int right) {
    42.         int[] temp = new int[right - left + 1];
    43.         int tempIndex = 0;
    44.         int left_head = left, right_head = mid + 1;
    45.         int s3 = 0;
    46.         while (right_head <= right && left_head <= mid) {
    47.             if (arr[left_head] > arr[right_head]) {
    48.                 temp[tempIndex++] = arr[right_head++];
    49.             } else {
    50.                 temp[tempIndex++] = arr[left_head++];
    51.                 s3 += right_head - mid - 1;
    52.             }
    53.         }
    54.         if (left_head <= mid) {
    55.             for (int i = left_head; i <= mid; i++) {
    56.                 temp[tempIndex++] = arr[i];
    57.                 s3 += (right - mid);
    58.             }
    59.         }
    60.         if (right_head <= right) {
    61.             for (int i = right_head; i <= right; i++) {
    62.                 temp[tempIndex++] = arr[i];
    63.             }
    64.         }
    65.         for (int i = 0; i < temp.length; i++) {
    66.             arr[left + i] = temp[i];
    67.         }
    68.         return s3;
    69.     }
    70. }

  • 相关阅读:
    透视星环科技上市：基础工具、技术融合、场景应用三维击穿
    Rust语言从入门到入魔 （更新中）
    〔001〕虚幻 UE5 安装教程
    pandas notes 25
    Ambari-yarn-timeline 内置 HBase数据表清理
    固态硬盘接口类型介绍
    光说不练假把式，一起Kafka业务实战。
    在Springboot项目中使用Redis提供给Lua的脚本
    JavaScript项目1_猜数字（前导）
    针不戳 腾讯开源GitHub星标125K微服务架构进阶宝典
  • 原文地址：https://blog.csdn.net/qq_38689352/article/details/126505584