递归应用之归并排序

桃扇骨 2022-07-13 12:19 175阅读 0赞

算法分析  
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。  
基本思路：  
先递归的把数组划分为两个子数组，一直递归到数组中只有一个元素，然后再调用函数把两个子数组排好序，因为该函数在递归划分数组时会被压入栈，所以这个函数真正的作用是对两个有序的子数组进行排序；  
基本步骤：  
1、判断参数的有效性，也就是递归的出口；  
2、首先什么都不管，直接把数组平分成两个子数组；  
3、递归调用划分数组函数，最后划分到数组中只有一个元素，这也意味着数组是有序的了；  
4、然后调用排序函数，把两个有序的数组合并成一个有序的数组；

5、排序函数的步骤，让两个数组的元素进行比较，把大的/小的元素存放到临时数组中，如果有一个数组的元素被取光了，那就直接把另一数组的元素放到临时数组中，然后把临时数组中的元素都复制到实际的数组中；

示例代码：

public class GuibingSort {
    	//first数组初始索引值，mid数组分界点索引，last数组结束索引，temp[]临时数组
    	//以mid为界限，将a分为两个数组，对其进行归并排序
    	//将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，
    	//谁小就先取谁，取了后就在对应数列中取下一个数。然后再进行比较，
    	//如果有数列遍历完毕，那直接将另一个数列的数据依次取出即可。
    	void mergearray(int a[], int first, int mid, int last, int temp[])
    	{//两个有序数组的归并
    		int i = first,m = mid;//第一个数组的范围
    		int j = mid + 1,n = last;//第二个数组的范围
    		int k = 0;//temp的初始下标
    		
    		while (i <= m && j <= n)//分别从两个数组中取值
    		{
    			if (a[i] <= a[j])//取较小的数放到temp数组中
    				temp[k++] = a[i++];//先进行赋值运算，然后k，i自加1
    			//注意，这里j并没有变化，下一次比较仍然是上一次的j值，直到else发生
    			else
    				temp[k++] = a[j++];//j变化，i不变化
    		}
    		
    		while (i <= m)//如果数组中仍有元素，直接复制到temp后面即可
    			temp[k++] = a[i++];
    		
    		while (j <= n)
    			temp[k++] = a[j++];
    		
    		for (i = 0; i < k; i++)//将排好序的数组重新赋给a
    			a[first + i] = temp[i];
    	}
    	void mergesort(int a[], int first, int last, int temp[])
    	//a[]是需要排序的数组，first, last是索引范围
    	{
    		if (first < last)//当数组中只有一个元素时，first==last，递归结束
    		{
    			int mid = (first + last) / 2;
    			mergesort(a, first, mid, temp);    //左边递归，直到只剩一个元素
    			mergesort(a, mid + 1, last, temp); //右边递归，直到只剩一个元素
    			mergearray(a, first, mid, last, temp); //再将二个有序数列合并
    		}
    	}
    	public void sort(int[] a) {
    		int n=a.length;
    		int[] b=new int[n];
    		mergesort(a, 0, n-1, b);
    	}
    public static void main(String[] args) {
    	int[] a= {10,9,8,7,6,5,4,3};
    	GuibingSort guibingSort=new GuibingSort();
    	guibingSort.sort(a);
    	for (int i : a) {
    		System.out.println(i);
    	}
    }
    }

运行过程解释：

第一次归并10和9，排序结果9,10

第二次归并8和7，排序结果7,8

第三次归并9,10和7,8，,排序结果7,8,9,10

对于6,5,4,3排序过程与上述类似，排序结果为3,4,5,6

最后归并两大部分，得到最终结果。