归并排序的原理及时间复杂度

  • 归并排序的定义：
    归并排序算法采用的是分治算法,即先把要排序的数组分成两个(或两个以上)有序表，然后再合并成一个新的有序表,即把待排序的序列分成若干个子序列,每个子序列都是有序的,然后把有序子序列合并成整体有序序列,这个过程也称为2-路归并.注意:归并排序的一种稳定排序,即相等元素的顺序不会改变.

  • 归并排序的原理
    将待排序的数组分成前后两个部分，再递归的将前半部分数据和后半部分的数据各自归并排序，得到的两部分数据，然后使用merge合并算法（算法见代码）将两部分算法合并到一起。
    例如：如果N=1；那么只有一个数据要排序，N=2，只需要调用merge函数将前后合并，N=4，……….. 也就是将一个很多数据的数组分成前后两部分，然后不断递归归并排序，再合并，最后返回有序的数组。

  • 归并排序的时间复杂度
    归并排序的最好、最坏和平均时间复杂度都是O(nlogn)，而空间复杂度是O(n)，比较次数介于(nlogn)/2和(nlogn)-n+1，赋值操作的次数是(2nlogn)。因此可以看出，归并排序算法比较占用内存，但却是效率高且稳定的排序算法。

  • 代码：

    public class MergeSort {
    	private static void mergeSort(int[] array,int[] tmp,int left,int right){
    		if(left<right){
    			int center = ( left + right ) / 2;//取数组的中点
    			mergeSort(array,tmp,left,center);//归并排序数组的前半部分
    			mergeSort(array,tmp,center+1,right);//归并排序数组的后半部分
    			merge(array,tmp,left,center+1,right);//将数组的前后半部分合并
    		}
    	}
    	/*
    	 * 超简单的合并函数
    	 */
    	private static void merge(int[] array, int[] tmp, int leftPos, int rightPos, int rightEnd) {
    		// TODO Auto-generated method stub
    		int leftEnd = rightPos - 1;
    		int tmpPos = leftPos;
    		int numElements = rightEnd - leftPos + 1;
    		while(leftPos <= leftEnd && rightPos <= rightEnd){
    			if(array[leftPos]<=array[rightPos]){
    				tmp[tmpPos++] = array[leftPos++];
    			}else{
    				tmp[tmpPos++] = array[rightPos++];
    			}
    		}
    		while(leftPos <= leftEnd){
    			tmp[tmpPos++] = array[leftPos++];
    		}
    		while(rightPos <= rightEnd){
    			tmp[tmpPos++] = array[rightPos++];
    		}
    		for(int i=0;i<numElements;i++,rightEnd--){
    			array[rightEnd] = tmp[rightEnd];
    		}
    	}
    	public static void mergeSort(int[] array){
    		int[] tmp = new int[array.length];//声明一个用来合并的数组
    		mergeSort(array,tmp,0,array.length-1);//调用排序函数，传入数字的起点和终点
    	}
    }

往期精彩文章