今天看算法导论,学习了归并排序原理,结合网上的示例自己理解后用python和c来实现
一、归并排序算法原理
其原理我简要用算法导论中的伪码表示，如下：
-
∞作为哨兵,预示不可能还有更小的数 MERGE(A,p,q,r) n1=q-p+1 n2=r-q LetL[1..n1+1] and R[1..n2+1] be new arrays for i=1 to n1 L[i]=A[p+i-1] for j=1 to n2 R[i]=A[q+j] L[n1+1]=∞ R[n2+1]=∞ i=1 j=1 for k=p to r if L[i]<=R[j] A[k]=L[i] i=i+1 else A[k]=R[j] j=j+1
二、Python实现
方法一;采取非临时数组的方式,在归并期间借助动态申请左边数据集和右边数据集对数组排序
marr=[1,4,5,7,2,5,9,3] def mergeSort(Arr,p,r): if p<r: m=(p+r)/2 mergeSort(Arr,p,m) mergeSort(Arr,m+1,r) merge(Arr,p,m,r) def merge(Arr,p,q,r): n1,n2=q-p+1,r-q LArr=Arr[p:q+1] RArr=Arr[q+1:r+1] i,j=0,0 k=p while i<n1 and j<n2: if LArr[i]<=RArr[j]: Arr[k]=LArr[i] i+=1 else: Arr[k]=RArr[j] j+=1 k+=1 while i<n1: Arr[k]=LArr[i] i+=1 k+=1 while j<n2: Arr[k]=RArr[j] j+=1 k+=1 mergeSort(marr,0,len(marr)-1)
方法二:借助临时数组排序
arr=[1,5,2,7,4,8,3] def merge(arr,p,q,r,tempArr): i,j=p,q+1 n1,n2=q,r k=p while i<=n1 and j<=n2: if arr[i]<=arr[j]: tempArr[k]=arr[i] i+=1 else: tempArr[k]=arr[j] j+=1 k+=1 while i<=n1: tempArr[k]=arr[i] i+=1 k+=1 while j<=n2: tempArr[k]=arr[j] j+=1 k+=1 while p<=r: arr[p]=tempArr[p] p+=1 def mergeSort(arr,p,r,tempArr): if p<r: mid=(p+r)/2 mergeSort(arr,p,mid,tempArr) mergeSort(arr,mid+1,r,tempArr) merge(arr,p,mid,r,tempArr) mergeSort(arr,0,len(arr)-1,tempArr)
方法二借助了一个临时数组tempArr对归并环节的数据保存，然后将归并排序号的数据集copy到原数组arr中，这样的好处是不用在归并环节动态申请数组空间，只需要一次申请一个和arr一样的数组即可，减少了gc的开销。
二、C实现
#include <stdio.h> #include <stdlib.h> #include <time.h> const int NUM=10; void mergeSort(int data[], int start, int end); void merge(int data[], int start, int mid, int end); void printArr(int arr[], int length); void merge2(int data[], int start, int mid, int end, int tempData[]); void mergeSort2(int data[], int start, int end, int tempData[]); void main(int argc, char *argv[]){ //第一种方式实现 int arr[NUM]; int i; srand((int)time(NULL)); for(i=0; i<NUM; i++){ arr[i] = (int)(30*rand()/(RAND_MAX+1.0)); } printArr(arr,NUM); mergeSort(arr, 0, NUM-1); printArr(arr, NUM); //第二种方式实现 int* tempArr = (int*)malloc(NUM*sizeof(int)); srand((int)time(NULL)); for(i=0; i<NUM; i++){ arr[i] = (int)(30*rand()/(RAND_MAX+1.0)); } printArr(arr,NUM); mergeSort2(arr, 0, NUM-1, tempArr); printArr(arr, NUM); free(tempArr); } void mergeSort(int data[], int start, int end){ int mid; if(start < end){ mid = (start+end)/2; mergeSort(data, start, mid); mergeSort(data, mid+1, end); merge(data, start, mid, end); } } void merge(int data[], int start, int mid, int end){ int leftLength, rightLength; int *temp; int tempStart = start; int tempEnd = mid+1; int tempkey = 0; leftLength = mid - start + 1; rightLength = end-start; temp = (int *)malloc(sizeof(int) * (end-start+1)); while(tempStart<=mid && tempEnd <= end){ if(data[tempStart] > data[tempEnd]){ temp[tempkey++] = data[tempEnd]; tempEnd++; }else{ temp[tempkey++] = data[tempStart]; tempStart++; } } while(tempStart <= mid){ temp[tempkey++] = data[tempStart++]; } while(tempEnd <= end){ temp[tempkey++] = data[tempEnd++]; } tempkey = 0; while(start+tempkey<=end){ data[start+tempkey] = temp[tempkey]; tempkey++; } free(temp); } void mergeSort2(int data[], int start, int end, int tempData[]){ if(start<end){ int mid=(start+end)/2; mergeSort2(data, start, mid, tempData); mergeSort2(data, mid+1, end, tempData); merge2(data, start, mid, end, tempData); } } void merge2(int data[], int start, int mid, int end, int tempData[]){ int i=start, k=start, j=mid+1; while(i<=mid && j<=end){ if(data[i]<=data[j]){ tempData[k++]=data[i++]; } else{ tempData[k++]=data[j++]; } } while(i<=mid){ tempData[k++]=data[i++]; } while(j<=end){ tempData[k++]=data[j++]; } for(i=start; i<=end; i++){ data[i]=tempData[i]; } } void printArr(int arr[], int length){ int i; for(i=0; i<length; i++){ printf("%d ", arr[i]); } }