归并排序
时间复杂度是 O(nlogn),空间复杂度是O(n)
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <stdio.h> #include <stdlib.h> void printArray(int a[], int len) { for(int i=0; i<len; ++i) { if(0==i) printf("[%d,",a[i]); else if(i < len-1) printf("%d,",a[i]); else printf("%d]\n",a[i]); } } //将 有序的数组 a、b 合并为一个有序的数组c。数组c要预先分配好内存。 void Merge2(int a[], int left1, int right1, int b[], int left2, int right2, int c[]) { int i = left1, j = left2, k = 0; for(k = 0; i <= right1 && j <= right2; ++k){ if(a[i] <= b[j]) c[k] = a[i++]; else c[k] = b[j++]; } while(i <= right1) c[k++] = a[i++]; while(j <= right2) c[k++] = b[j++]; } //将分别有序的data[s..m] 和 data[m+1 .. n] 归并为有序的 data[s..n] void Merge(int data[], int s, int m, int n){ int i, start = s, k=0; int *temp = (int*) malloc((n-s+1)*sizeof(int)); for(i=m+1; s<=m && i<=n; ++k){ if( data[s] <= data[i] ) temp[k]=data[s++]; else temp[k] = data[i++]; } for(; s<=m; ++k) temp[k] = data[s++]; for(; i<=n; ++k) temp[k] = data[i++]; //拷贝 temp 到 data里 for(i=0; i<k; ++i){ data[start++] = temp[i]; } free(temp); } void MSort(int data[], int left, int right){ if(left < right){ int mid = left + (right-left)/2; MSort(data, left, mid); MSort(data, mid+1, right); Merge(data, left, mid, right); } } int main(){ //int a[] = {4,10,55,5,22,32,72,113}; //int len = sizeof(a)/sizeof(a[0]); //int m = 2; //printArray(a,len); //Merge(a,0,m,len-1); //printArray(a,len); // int a[] = {1,2,3,4,9,15,16,21,45}; // int b[] = {3,5,6,7,11,17,18,200}; // int aLen = sizeof(a)/sizeof(a[0]); // int bLen = sizeof(b)/sizeof(b[0]); // int len = aLen+bLen; // int *res = (int*) malloc(len*sizeof(int)); // Merge2(a,0,aLen-1,b,0,bLen-1, res); // printArray(res,len); // free(res); // int a[] = {4,10,55,5,22,32,72,113,200}; // int len = sizeof(a)/sizeof(a[0]); // int m = 2; // printArray(a,len); // int res[100] = {0}; // Merge2(a,0,m,a,m+1,len-1,res); // printArray(res,len); int a[]={3,7,9,2,1,0,15,10}; int len = sizeof(a)/sizeof(a[0]); printArray(a,len); MSort(a,0,len-1); printArray(a,len); return 0; }View Code
--
标签:归并,排序,int,复杂度,include,nlogn From: https://www.cnblogs.com/htj10/p/16992411.html