文章目录
稳定性
稳定性：保持相对位置不变
冒泡排序，归并排序，直接插入排序的具有稳定性，在排序的时候不会改变数据的相对位置
快速排序，希尔排序，选择排序都不具有稳定性
综合比较之下快速排序的效率最高，在大多面试时候也多以快速排序，堆排序，归并排序为主
归并排序
递归版
#include<stdio.h> #include<stdlib.h> void _mergesort(int *a,int left,int right,int *tmp) { //1个就不用分了 if(left>=right) { return; } int mid=(left+right)/2; //[left,mid]有序[mid+1,right],有序就可以进行归并了 //左边和右边都有序了就可以进行归并了 _mergesort(a,left,mid,tmp); _mergesort(a,mid+1,right,tmp); //后序 //开始归并了 int begin1=left,end1=mid; int begin2=mid+1,end2=right; int i=left;//i不是0而是left，这样返回原数组就可以 while(begin1<=end1&&begin2<=end2)//有一个结束了就可以把另一个全部都接起来 { if(a[begin1]<a[begin2]) { tmp[i++]=a[begin1]; begin1++; } else { tmp[i++]=a[begin2]; begin2++; } } //不知道谁结束了 while(begin1<=end1) { tmp[i++]=a[begin1]; begin1++; } while(begin2<=end2) { tmp[i++]=a[begin2]; begin2++; } //tmp还要拷贝回a，这样才可以回去进行归并 for(int j=left;j<=right;j++) { a[j]=tmp[j]; } } void mergesort(int *a,int n) { int *tmp=(int *)malloc(sizeof(int)*n); if(tmp==NULL) { printf("malloc fail"); return; } _mergesort(a,0,n-1,tmp);//在这里容易递归，子函数 free(tmp); tmp=NULL; } ```c 在这里插入代码片
非递归版本
版本1
//归并非递归循环写法 void mergesortnonr(int *a,int n)//n为个数 { int *tmp=(int *)malloc(sizeof(int)*n); if(tmp==NULL) { printf("malloc fail"); return; } int gap=1;//一个一个归，gap作为归并的间距 while(gap<n) { for(int i=0;i<n;i+=2*gap) { //这个循环里面就变成归并 //[i,i+gap-1],[i+gap,i+2*gap-1] //[0, 0 ],[1 , 1 ] int index=i;//tmp数组的起始位置是i相当于递归里面的left int begin1=i,end1=i+gap-1; int begin2=i+gap,end2=i+gap*2-1; //如果个数为奇数的话 //第一组越界,end1越界，【begin2,end2】不存在 if(end1>=n)//等于n就已经越界了//先end1 { end1=n-1;//进行修正 } //第2组不存在,begin2,end2不存在，再被begin2 if(begin2>=n) { //让这个区间不存在，就不用对这个区间进行操作了 begin2=n; end2=n-1; } if(end2>=n)//begin2存在，区间存在就修正为n-1 { end2=n-1;//再修正一下 } //如果begin1=end1=begin2=end2=n-1的话，tmp就会越界，重复的index++，后free多的未开辟的空间，index越界，进取一次出来又一次+ //将其进行归并 while(begin1<=end1&&begin2<=end2) { if(a[begin1]<a[begin2]) { tmp[index++]=a[begin1++]; } else { tmp[index++]=a[begin2++]; } } while(begin1<=end1) { tmp[index++]=a[begin1++]; } while(begin2<=end2) { tmp[index++]=a[begin2++]; } } //把归并数组拷贝回原数组 //整段拷贝回去 for(int i=0;i<n;i++) { a[i]=tmp[i]; } gap*=2; } free(tmp);//解决了tmp的溢出问题 tmp=NULL; }
版本2
void mergesortnonr2(int *a,int n)//n为个数 { int *tmp=(int *)malloc(sizeof(int)*n); if(tmp==NULL) { printf("malloc fail"); return; } int gap=1;//一个一个归 while(gap<n) { for(int i=0;i<n;i+=2*gap) { //这个循环里面就变成归并 //[i,i+gap-1],[i+gap,i+2*gap-1] //[0, 0 ],[1 , 1 ] int index=i;//tmp数组的起始位置是i相当于递归里面的left int begin1=i,end1=i+gap-1; int begin2=i+gap,end2=i+gap*2-1; //end1越界 或者 begin2都不需要处理归并， if(end1>=n||begin2>=n) { break;//进行修正 } //end2越界就需要归，就修正end2就可以 if(end2>=n) { end2=n-1;//再修正一下 } //如果begin1=end1=begin2=end2=n-1的话，tmp就会越界，重复的index++，后free多的未开辟的空间，index越界，进取一次出来又一次+ //将其进行归并 while(begin1<=end1&&begin2<=end2) { if(a[begin1]<a[begin2]) { tmp[index++]=a[begin1++]; } else { tmp[index++]=a[begin2++]; } } while(begin1<=end1) { tmp[index++]=a[begin1++]; } while(begin2<=end2) { tmp[index++]=a[begin2++]; } for(int j=begin1;j<=end1;j++) { a[j]=tmp[j]; } } //把归并数组拷贝回原数组 //整段拷贝回去 gap*=2; } free(tmp); tmp=NULL; }
void print(int *a,int n) { int i=0; for(i=0;i<n;i++) { printf("%d ",a[i]); } } int main() { //归并排序 int arr[10]={10,6,7,1,3,4,2,0,11,12}; //mergesort(arr,sizeof(arr)/sizeof(int)); // mergesortnonr(arr,sizeof(arr)/sizeof(int)); mergesortnonr2(arr,sizeof(arr)/sizeof(int)); print(arr,sizeof(arr)/sizeof(int)); return 0; }
