归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。 若将两个有序表合并成一个有序表,称为二路归并。
O ( n log n ) {\displaystyle O(n\log n)} (大O符号)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。 O ( n log n ) {\displaystyle O(n\log n)} (大O符号)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。
作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
设定两个指针,最初位置分别为两个已经排序序列的起始位置;
比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
重复步骤 3 直到某一指针达到序列尾;
将另一序列剩下的所有元素直接复制到合并序列尾。
nlogn+n,递归堆栈+数组
nlogn,归并的过程类型二叉树高度,所以时间复杂度就是树高
稳定
public static void MergeSort(int[] array1) { int low = 0, heigh = array1.Length - 1; Mergesort(array1, low, heigh); } private static void Mergesort(int[] array1,int low,int heigh) { if (low < heigh) { int mid = (low+heigh) / 2; Mergesort(array1,low,mid); Mergesort(array1, mid + 1, heigh); BinaryMerge(array1,low,mid,heigh); } } public static void BinaryMerge(int[] array, int low,int mid,int height) { int[] temparray = new int[array.Length]; int left, right,index; //复制数组 for (index = low; index <= height; index++) { temparray[index] = array[index]; } //二路归并 for ( index= left = low,right=mid+1;left<=mid&& right <= height && index <=height; index++) { if (temparray[left] <= temparray[right]) { array[index] = temparray[left++]; } else { array[index] = temparray[right++]; } } //检查那个部分没拷贝完成,将temparray剩余的部分拷贝到array数组中 while (left<=mid) array[index++] = temparray[left++]; while(right<=height) array[index++]=temparray[right++]; }