做网站开票是多少个点的票,wordpress扫码提交数据库,质监站网址,代理浏览网站归并排序 归并排序(Merge Sort)算法#xff0c;使用的是分治思想。分治#xff0c;顾名思义#xff0c;就是分而治之#xff0c;将一个大问题分解成小的子问题来解决。小的子问题解决了#xff0c;大问题也就解决了。 核心源码: mergeSort(m-n) merge(mergeSort(m-使用的是分治思想。分治顾名思义就是分而治之将一个大问题分解成小的子问题来解决。小的子问题解决了大问题也就解决了。 核心源码: mergeSort(m-n) merge(mergeSort(m-k),mergeSort(k1-n)) 算法思路
如果要排序一个数组先把数组从中间分成前后两部分然后对前后两部分分别排序再将排好序的两部分合并在一起这样整个数组就都有序了。具体见下图 注意分治思想跟递归思想很相似。分治是一种解决问题的处理思想递归是一种编程技巧这两者并不冲突分治算法一般都是用递归来实现。 具体代码实现如下
import java.util.Arrays;
import org.junit.Test;/***
* ClassName: MergeSort
* author shaoyb
* date 2020年12月9日
* Description: 归并排序
* 归并排序思路
* 1、把长度为n的序列一分为二成两个子序列2、对这两个子序列分别采用归并排序3、将两个排序好的子序列合并成一个最终的排序序列。*/
public class MergeSort {/*** 归并排序算法实现* param arr 需要排序的数组* return 排序成功后新数组*/public int[] mergeSort(int[] arr){//1.确定递归终止条件if(arr.length 2) {return arr;}//2.拆解数组成左右两部分int mid arr.length/2;int[] left Arrays.copyOfRange(arr,0,mid);int[] right Arrays.copyOfRange(arr,mid,arr.length);//3.对拆解后两个数组进行合并return merge(mergeSort(left),mergeSort(right));}/*** 合并两个有序数组并返回合并后的新数组* param left* param right*/public int[] merge(int[] left,int[] right) {//1.定义好新数组int[] newArray new int[left.length right.length];//2.往新数组中逐个添加元素int lIndex 0;int rIndex 0;for(int i 0; i newArray.length; i) {if(lIndex left.length) {//左数组已经遍历完成newArray[i] right[rIndex];}else if(rIndex right.length) {//右数组已经遍历完成newArray[i] left[lIndex];}else if(left[lIndex] right[rIndex]) {//左数组当前元素值小于右数组newArray[i] left[lIndex];}else {//右数组当前元素值小于左数组newArray[i] right[rIndex];}}return newArray;}Testpublic void testMergeSort(){//1.定义数组int[] array new int[] {5,2,6,9,0,3};System.out.println(排序前 Arrays.toString(array));//2.归并排序array mergeSort(array);System.out.println(排序后 Arrays.toString(array));}
}
