Java 详细讲解分治算法如何实现归并排序

Java 详细讲解分治算法如何实现归并排序

目录1.什么是分治算法分治法基本思想2.分治算法的体现——归并排序归并排序基本思想3.代码实现

1.什么是分治算法

分治法

分治法，字面意思是“分而治之”，就是把一个复杂的1问题分成两个或多个相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并，这个思想是很多高效算法的基础，例如排序算法(快速排序，归并排序)，傅里叶变换(快速傅里叶变换)等。

基本思想

分治法的基本思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

2.分治算法的体现——归并排序

归并排序

归并排序（ MERGE － SORT ）是利用归并的思想实现的排序方法，该算法采用经典的分治（ divide - and - conquer )策略（分治法将问题分（ divide ）成一些小的问题然后递归求解，而治（ conquer ）的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之）。

基本思想

流程图（以对数组[8,4,5,7,1,3,6,2]排序为例）

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将

[4,5,7,8］和［1,2,3,6］两个已经有序的子序列，合并为最终序列［1,2,3,4,5,6,7,8]，来看下实现步骤。

3.代码实现

package Sort;

import java.util.Arrays;

/**

* 归并排序：

*

* 利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，

*

* 而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

* @author lenovo

*

*/

public class MergeSort {

public static void main(String[] args) {

int[] a= {5,8,6,3,9,8,7,1,4,21,-8,46};

int[] temp=new int[a.length];

mergeSort(a, 0, a.length-1, temp);

System.out.println(Arrays.toString(a));

}

public static void mergeSort(int[] arr,int left,int right,int[] temp) {

if(left

int mid=(left+right)/2;

mergeSort(arr, left, mid, temp);

mergeSort(arr, mid+1,right, temp);

merge(arr, left, mid, right, temp);

}

}

public static void merge(int[] arr,int left,int mid,int right,int[] temp) {

int l=left;//左边序列的起始位置

int r=mid+1;//右边序列的起始位置

int t=0;//中间数组的当前元素下标

while(l<=mid &&r<=right ) {//左边或右边没结束

//那边小就将那边的元素放入到临时数组中

if(arr[l]<=arr[r]) {

temp[t++]=arr[l++];

}else {

temp[t++]=arr[r++];

}

}

//while循环结束，说明有一边已经遍历完毕，将另一边剩余的元素放入到临时数组中

while(l<=mid) {

temp[t++]=arr[l++];

}

while(r<=right) {

temp[t++]=arr[r++];

}

//将临时数组中的有序序列copy到原数组中

t=0;

int templeft=left;

while(templeft<=right) {

arr[templeft++]=temp[t++];

}

}

}

int mid=(left+right)/2;

mergeSort(arr, left, mid, temp);

mergeSort(arr, mid+1,right, temp);

merge(arr, left, mid, right, temp);

}

}

public static void merge(int[] arr,int left,int mid,int right,int[] temp) {

int l=left;//左边序列的起始位置

int r=mid+1;//右边序列的起始位置

int t=0;//中间数组的当前元素下标

while(l<=mid &&r<=right ) {//左边或右边没结束

//那边小就将那边的元素放入到临时数组中

if(arr[l]<=arr[r]) {

temp[t++]=arr[l++];

}else {

temp[t++]=arr[r++];

}

}

//while循环结束，说明有一边已经遍历完毕，将另一边剩余的元素放入到临时数组中

while(l<=mid) {

temp[t++]=arr[l++];

}

while(r<=right) {

temp[t++]=arr[r++];

}

//将临时数组中的有序序列copy到原数组中

t=0;

int templeft=left;

while(templeft<=right) {

arr[templeft++]=temp[t++];

}

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。