归并排序算法是典型的分治算法,对于规模较大的问题,可以分解成若干容易求解的简单的问题,最后把解合并构成初始问题的解。不存在跳跃比较,所以归并排序是一种稳定的排序算法。比较占用内存,效率高且稳定。
基本思想:假设初始序列有n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到[n/2](上括号,不小于它的最小整数)个长度为2或1的有序子序列;再两两归并,……,如此重复,直至得到一个长度为n的有序序列为止,称为2路归并排序。
C++实现
法一:
/**********************************/ /***********归并排序***************/ /**********************************/ void Merge(ElemType SR[], ElemType TR[], int low, int mid, int high) { /* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] 算法10.12 */ int j,k,l; for(j=mid+1, k=low ; low<=mid&&j<=high;++k) /* 将SR中记录由小到大地并入TR */ if (SR[low] < SR[j]) TR[k] = SR[low++]; else TR[k] = SR[j++]; if(low <= mid) for(l=0 ; l<=mid-low ; l++) TR[k+l] = SR[low+l]; /* 将剩余的SR[i..m]复制到TR */ if(j<=high) for(l=0;l<=high-j;l++) TR[k+l]=SR[j+l]; /* 将剩余的SR[j..n]复制到TR */ } void MSort(ElemType SR[],ElemType TR1[],int low, int high) { /* 将SR[s..t]归并排序为TR1[s..t]。算法10.13 */ ElemType TR2[MAXSIZE+1]; if(low == high) TR1[low]=SR[low]; else { int mid = (low+high)/2; /* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */ MSort(SR, TR2, low, mid); /* 递归地将SR[s..m]归并为有序的TR2[s..m] */ MSort(SR, TR2, mid+1, high); /* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */ Merge(TR2, TR1, low, mid, high); /* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */ } } void MergeSort(int Arr[], int n) { /* 对顺序表L作归并排序。算法10.14 */ MSort(Arr, Arr, 0, n-1); }
法二:
/**********************************/ /***********归并排序***************/ /**********************************/ void Merge(ElemType a[],int begin,int mid,int end) { int index1 = begin,index2 = mid+1; ElemType temp[10]={0};//临时 for(int i = 0;i < 10;i++) temp[i] = a[i]; int cur = begin; //index1指向低段,index2指向高段,cur指向赋值给temp的位置 while(index1 <= mid && index2 <= end) { if(temp[index1] < temp[index2]) a[cur] = temp[index1++]; else a[cur] = temp[index2++]; cur++; } if(index1 <= mid) for(int i = 0;i <= mid-index1;i++) a[cur + i] = temp[index1 + i]; //复制剩余的start至mid到a[] if(index2 <= end) for(int i = 0;i <= end-index2;i++) a[cur + i] = temp[index2 + i]; //复制剩余的j至end到a[] } void MSort(ElemType a[],int low,int high) { if(low < high) { int mid = (low + high)/2; //平分 MSort(a,low,mid); //递归将[low..mid]归并为有序 MSort(a,mid+1,high); //递归将[mid+1..high]归并为有序 Merge(a,low,mid,high); //合并 } } void MergeSort(ElemType a[],int n) { MSort(a,0,n-1); }
python实现
#-------=------# #--Merge sort--# #--------------# def merge(arr,low,mid,high): index1 = low index2 = mid + 1 temparr = [] cur = low while index1 <= mid and index2 <= high : if arr[index1] < arr[index2]: temparr.append(arr[index1]) index1 += 1 else : temparr.append(arr[index2]) index2 += 1 cur += 1 if index1 <= mid: for i in range(0,mid - index1 + 1): arr[cur + i] = arr[index1 + i] #for i in range(index1, mid + 1): #arr[cur + i - index1] = arr[i] if index2 <= high: for i in range(0,high - index2 + 1): arr[cur + i] = arr[index2 + i] #for i in range(index2, high + 1): #arr[cur + i - index2] = arr[i] for i in range(0, cur - low): arr[low + i] = temparr[i] def MSort(arr,low,high): if low < high: mid = (low + high)/2 MSort(arr,low,mid) MSort(arr,mid + 1,high) merge(arr,low,mid,high) def merge_sort(arr): arrlen = len(arr) MSort(arr,0,arrlen-1) #arrlen-1
归并排序复杂度分析:
时间复杂度为o(nlogn)。归并算法中最好、最坏、平均的时间性能。
空间复杂度为o(n+logn)。需要与原始记录序列同样数量的存储空间存放归并结果以及递归时深度为logn的栈空间。
非递归的归并排序:
void Merge(ElemType SR[], ElemType TR[], int low, int mid, int high) { /* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] 算法10.12 */ int j,k,l; for(j=mid+1, k=low ; low<=mid&&j<=high;++k) /* 将SR中记录由小到大地并入TR */ if (SR[low] < SR[j]) TR[k] = SR[low++]; else TR[k] = SR[j++]; if(low <= mid) for(l=0 ; l<=mid-low ; l++) TR[k+l] = SR[low+l]; /* 将剩余的SR[i..m]复制到TR */ if(j<=high) for(l=0;l<=high-j;l++) TR[k+l]=SR[j+l]; /* 将剩余的SR[j..n]复制到TR */ } void Mergepass(ElemType SR[],ElemType TR[],int s,int n) { int i =0; int j; while(i < n-2*s+1) { Merge(SR,TR,i,i+s-1,i+2*s-1); i = i+2*s; } if(i < n-s) Merge(SR,TR,i,i+s-1,n-1); else for(j = i;j < n;j++) TR[j] = SR[j]; } void MergeSort2(ElemType a[],int n) { ElemType* TR = (int*)malloc(n*sizeof(ElemType)); int k = 1; while(k < n) { Mergepass(a,TR,k,n); k = 2*k; Mergepass(TR,a,k,n); k = 2*k; } }
空间复杂度减少为o(n)。