用java写归并排序
主要思想：先分再合，使用分治的方法
1，第一步，先说如何分
假设有数组8个数字，先分为4，在分为2，再分为1
这边使用递归，详情见图片
这样的话就将所有的数据递归，即将所有的数据给分开，再来组合
2，合
两两组合，在组合时并且比较大小
3，代码
package sanguigu.sort; import java.util.Arrays; /** * 快速排序，使用分治的方法 * @author:zhenghuisheng */ public class Kuaipai { public static void main(String Args[]){ int b[] = {3,1,4,2,5,7,9,8}; int temp[] = new int[b.length]; merge_sort(b,0,b.length-1,temp); System.out.println(Arrays.toString(b)); } //分 public static void merge_sort(int a[],int left,int right,int temp[]){ if(left < right){ int mid = (left + right) / 2; //中间索引 //向左递归分解 merge_sort(a,left,mid,temp); //向右递归 merge_sort(a,mid+1,right,temp); //在这进行递归时可以发现，在只有两个数据时，可以发现left=0，mid=(0+1)/2=0,所有数组a有至少两个数据 merge(a,left,mid,right,temp); } } /** * 合 * @param ：数组 * @param left：左边的数 * @param mid：中间的数 * @param right：左边的数 * @param temp：临时数组 * */ public static void merge(int a[],int left,int mid,int right,int temp[]){ System.out.println("====="); int i = left; //左边的初始数据 int j = mid +1; //中间的数据 int t = 0; //临时变量数组的下标，在下标存入数据后，下标后移 //开始递归 while(i <= mid && j <= right){ //直接进行比较，如果值小的就将数据加入到临时数组中 if(a[i] >= a[j]){ temp[t] = a[j];t++;j++; } else {temp[t] = a[i];t++;i++;} } //如果还有剩余值 while(i <= mid){//即左边还有数据没有全部加入到临时数组中 temp[t] = a[i]; t = t+1; i = i+1; } while(j <= right){//即右边还有数据没有全部加入到临时数组中 temp[t] = a[j]; t = t+1; j = j+1; } //优化，并不是每次临时数组的值返回给原来的数组，而是将最后一次的数据值返回给临时数组 t= 0; int templeft = left; while(templeft <= right){ a[templeft] = temp[t]; t = t+1; templeft = templeft +1; } System.out.println(Arrays.toString(temp)); System.out.println(Arrays.toString(a)); } }
