面试官：手写一个归并排序，并对其改进-白红宇

面试官：手写一个归并排序，并对其改进

阅读量：4035 次

发布时间：2019-05-24

本文共 2808 字，大约阅读时间需要 9 分钟。

之前曾介绍过快排、冒泡、插入等排序算法，这篇文章介绍一下归并排序。也算是一个比较有名的排序算法。

一、排序原理

归并排序的思想很简单，如果有一组待排序列，先切分再重组。任何一篇教程也都会说采用的是分治法，意思就是这么个意思，再细致一点的理解就是：

将一组待排序，先分割成一个一个的元素，然后将这些元素先两两排序，再四四排序，八八排序，一直到排序完所有的元素。

也就是说归并排序其实就是将已有序的子序列合并，得到完全有序的序列。我们看一张动图来认识一下：

在这里插入图片描述

是不是有点理解了，动态图的作用其实就是为了方便你了解整个归并过程，不理解也没关系，我们再来看一张静态图，帮助你从细节上来理解。

在这里插入图片描述

上面的这张图基本上能把整个归并排序的流程了解清楚了。也就是文章开头提到的先切分再重组。下面我们使用代码来实现一下归并排序，并对其做一个改进：

二、代码实现

1、基本实现

基本实现的思想很简单，我们就是先切分成一个个元素，然后再合并就好了。

//data：表示待排序列//left：表示当前序列的左边界//right：表示当前序列的右边界public static void sort(int[] data, int left, int right) {
   		if (left >= right)			return;		// 找出中间索引		int center = (left + right) / 2;		// 对左边数组进行递归		sort(data, left, center);		// 对右边数组进行递归		sort(data, center + 1, right);		// 合并		merge(data, left, center, right);		print(data);}

然后我们看一下合并：

public static void merge(int[] data, int left, int center, int right) {
   	int[] tmpArr = new int[data.length];	int mid = center + 1;	int third = left;	int tmp = left;	while (left <= center && mid <= right) {
   		// 从两个数组中取出最小的放入临时数组		if (data[left] <= data[mid]) {
   			tmpArr[third++] = data[left++];		} else {
   			tmpArr[third++] = data[mid++];		}	}	// 剩余部分依次放入临时数组	while (mid <= right) {
   		tmpArr[third++] = data[mid++];	}	while (left <= center) {
   		tmpArr[third++] = data[left++];	}	// 将临时数组中的内容拷贝回原数组中	while (tmp <= right) {
   		data[tmp] = tmpArr[tmp++];	}}

是不是很简单，在合并的时候是左右两部分进行合并。不过这里我们会发现有很多问题，比如说两个子序列就算合并起来也已经有序了，但是在代码中还是要一个一个比较。而且我们的子数组比较小的时候，归并排序的速度并没有显著提高。因此我们可以做出一些改进。

2、改进算法

针对上面出现的问题：我们可以在以下几个方面：

（1）如果子数组较小，改用插入排序；

（2）两个子数组若已经有序，则直接复制进数组

（3）通过交换参数来避免每次都要复制到辅助数组。

OK，我们看一下代码：

private static void sort(Comparable[] a, Comparable[] aux,int low, int height){
   		int mid = low + (height -low) / 2;	        //改进1：若子序列比较短，则直接使用插入排序		if(height <= low + 7 - 1){
     			insertionSort(a, lo, hi);			return;		}				sort(aux,a,low,mid);     		sort(aux,a,mid+1,height);          //less函数比较a[mid+1]和a[mid]的大小        //改进2：如果数组已经有序则直接复制，不再merge		if(!less(a[mid+1],a[mid])){
    			System.arraycopy(aux, low, a, low, height-low+1);			return;		}		merge(a,aux,low,mid,height); 	}

还有一点改进是在merge函数中进行的，我们来看一下：

private void merge(Comparable[] a,Comparable[] aux, int lo, int mid, int hi){
       //左半部分    for(int k = low; k <= mid; k++)		aux[k] = a[k];    //右半部分    for(int k = mid+1; k <= height; k++)		aux[k] = a[height+mid+1-k];	int i = low, j = height;     //整个序列	for(int k=low;k<=height; k++ ){
   		if(less(aux[j],aux[i]))			a[k] = aux[j--];		else 			a[k] = aux[i++]; 	}			}

插入算法在这里就不再演示了。下面我们就分析一下归并排序。

三、算法分析

我们分析的时候只考虑第一种情况，也就是基本情况。

归并排序的总时间=分解时间+解决问题时间+合并时间。

（1）分解时间：把待排序序列分解，时间为o(1)。

（2）解决问题时间：处理一个序列时间为1，处理两个子序列的时间就是1/2。

（3）合并时间：时间为o（n）。

时候只考虑第一种情况，也就是基本情况。

归并排序的总时间=分解时间+解决问题时间+合并时间。

（1）分解时间：把待排序序列分解，时间为o(1)。

（2）解决问题时间：处理一个序列时间为1，处理两个子序列的时间就是1/2。

（3）合并时间：时间为o（n）。

所以总时间T(n)=2T(n/2)+o(n)=o(nlogn)。也就是说在最坏、最好、平均情况下时间复杂度均为o(nlogn)。

转载地址：http://snbdi.baihongyu.com/

你可能感兴趣的文章