数据结构之归并排序

一时失言乱红尘 2022-08-11 16:40 155阅读 0赞

package com.zhiru;
 
 /*
 * 归并排序在概念上较为简单
 * 它的排序思路就是
 * 将原序列不断的折半划分，直到划分为单个的元素。
 * 然后将划分的序列归并。
 */
 public class MergeSort {
 	// merge函数就是用来归并a序列中有序的左子序列和右子序列，
 	// 将它们归并到b中。
 	public static void merge(int[] a, int[] b, int left, int mid, int right) {
 		int i, t;
 		for (int k = 0; k < a.length; k++) {
 			b[k] = a[k];
 		}
 		int s1 = left;
 		int s2 = mid + 1;
 		t = left;
 		while(s1<=mid&&s2<=right){
 			if(b[s1]<=b[s2])a[t++]=b[s1++];//将小的元素放到前头
 			else
 				a[t++]=b[s2++];
 		}
 		while(s1<=mid)a[t++]=b[s1++];
 		while(s2<=right)a[t++]=b[s2++];
 		for(i=0;i<a.length;i++){
 			System.out.print(a[i]+" ");
 		}
 		System.out.print("\n");
 	}
 	public static void mergeSort(int[]a,int[]b,int left,int right){
 		if(left>=right)return;
 		int mid=(left+right)/2;
 		mergeSort(a,b,left,mid);
 		mergeSort(a,b,mid+1,right);
 		merge(a,b,left,mid,right);
 	}
 	public static void ms(int[]a){
 		int[]b=new int[a.length];
 		mergeSort(a,b,0,a.length-1);
 	}
 }

归并排序

划分过程

**归并过程**

**在归并过程中伴随着排序的进行。**

**当一个无序序列划分为一个个只含有一个元素的序列的时候【这个时候它们都可以看做是有序的】，开始归并操作。在归并函数中可以看到，**

**递归的将一个个元素归并为有序序列。**

21 25 49 25 16 8   
21 25 49 25 16 8   
21 25 49 16 25 8   
21 25 49 8 16 25   
8 16 21 25 25 49