如何建立网站赚钱,互动平台网站建设,网站建设空间主机的选择,网站语言切换前端可以做么不爱生姜不吃醋⭐️⭐️⭐️ 如果本文有什么错误的话欢迎在评论区中指正 与其明天开始#xff0c;不如现在行动#xff01; 文章目录 #x1f334;前言#x1f334;一.归并排序1.概念2.时间复杂度3.代码实现 #x1f334;二、小和问题1.概念2.举例3.代码实现 #x1f334… 不爱生姜不吃醋⭐️⭐️⭐️ 如果本文有什么错误的话欢迎在评论区中指正 与其明天开始不如现在行动 文章目录 前言一.归并排序1.概念2.时间复杂度3.代码实现 二、小和问题1.概念2.举例3.代码实现 三、逆序对问题1. 概念2. 举例3.代码实现 总结 前言 归并排序是建立在归并操作上的一种有效稳定的排序算法该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 速度仅次于快速排序为稳定排序算法一般用于对总体无序但是各子项相对有序的数列。 一.归并排序
1.概念 申请空间使其大小为两个已经排序序列之和该空间用来存放合并后的序列 第二步设定两个指针最初位置分别为两个已经排序序列的起始位置 第三步比较两个指针所指向的元素选择相对小的元素放入到合并空间并移动指针到下一位置 重复步骤3直到某一指针超出序列尾 将另一序列剩下的所有元素直接复制到合并序列尾 2.时间复杂度 O(n log n) 3.代码实现
public class Example1 {public static void main(String[] args) {int[] arr {1, 5, 9, 3, 4, 6, 2, 7, 99, 2, 3, 7, 9, 5, 4,76};process(arr, 0, arr.length - 1);System.out.println(Arrays.toString(arr));}private static void process(int[] arr, int L, int R) {if (L R) {return;}int mid L ((R - L) 1);process(arr, L, mid);process(arr, mid 1, R);merge(arr, L, mid, R);}private static void merge(int[] arr, int L, int M, int R) {int[] temp new int[R - L 1];int i 0;int p1 L;int p2 M 1;while (p1 M p2 R) {temp[i] arr[p1] arr[p2] ? arr[p1] : arr[p2];}while (p1 M){temp[i]arr[p1];}while (p2 R){temp[i] arr[p2];}for (int j 0; j temp.length; j) {arr[Lj] temp[j];}}
} 二、小和问题
1.概念 在一个数组中每一个数左边比当前数小的数累加起来叫做这个数组的小和。 2.举例 数组【13425】中 1左边比1小的数没有 3左边比3小的数1 4左边比4小的数1、3 2左边比2小的数1 5左边比5小的数1、3、4、2 所以小和为1131134216 3.代码实现
public class Example2 {public static void main(String[] args) {int[] arr {1, 3, 4, 2, 5};System.out.println(process(arr, 0, arr.length - 1));}private static int process(int[] arr, int l, int r) {if (l r) {return 0;}int mid l ((r - l) 1);int leftSum process(arr, l, mid);int rightSum process(arr, mid 1, r);return leftSum rightSum merge(arr, l, mid, r);}private static int merge(int[] arr, int l, int mid, int r) {int[] temp new int[r - l 1];int i 0;int p1 l;int p2 mid 1;int sum 0;while (p1 mid p2 r) {sum arr[p1] arr[p2] ? (r - p2 1) * arr[p1] : 0;temp[i] arr[p1] arr[p2] ? arr[p1] : arr[p2];}while (p1 mid) {temp[i] arr[p1];}while (p2 r) {temp[i] arr[p2];}for (int j 0; j temp.length; j) {arr[l j] temp[j];}return sum;}
}三、逆序对问题
1. 概念 在一个数组中左边的数如果比右边的数大则这两个数构成一个逆序对。 2. 举例 在数组【32450】中 比3小的2、0 比2小的0 比4小的0 比5小的0 比0小的没有 所以该数组的逆序对共有5个 3.代码实现
public class Example3 {public static void main(String[] args) {int[] arr {3, 2, 4, 5, 0};System.out.println(process(arr, 0, arr.length - 1));}private static int process(int[] arr, int l, int r) {if (l r) {return 0;}int mid l ((r - l) 1);int leftR process(arr, l, mid);int rightR process(arr, mid 1, r);return leftR rightR merge(arr, l, mid, r);}private static int merge(int[] arr, int l, int mid, int r) {int[] temp new int[r - l 1];int i 0;int p1 l;int p2 mid 1;int sum 0;while (p1 mid p2 r){sum arr[p1] arr[p2] ? (mid - p1 1) : 0;temp[i] arr[p1] arr[p2] ? arr[p2] : arr[p1];}while (p1 mid){temp[i] arr[p1];}while (p2 r){temp[i] arr[p2];}for (int j 0; j temp.length; j) {arr[l j] temp[j];}return sum;}
}总结 文章中代码的编写使用的都是Java基础知识多加练习熟能生巧。 本文中若是有出现的错误请在评论区或者私信指出我再进行改正优化如果文章对你有所帮助请给博主一个宝贵的三连感谢大家
