//我竟不会写伪码… 1.<插入排序>//稳定 时间复杂度：最好情况：原本有序，只用比较n次。最坏情况：原本逆序，比较n(n-1)/2次。平均复杂度为O（n2） 空间复杂度：需要一个辅助空间记录将插入的值，空间复杂度O（1）
void insert(int* a,int n){ for(int i=1;i<n;++i){ int end=i,key=a[i]; while(end&&a[i]<a[i-1]){ a[end]=a[end-1]; --end; } a[end]=key; } } 2.<希尔排序>//不稳定 时间复杂度：平均复杂度为O（n（1.3~2）） 空间复杂度：同插入排序所以也为O（1） void shellsort(int* a,int n){ int gap=n; while(gap>1){ gap=gap/3+1; for(int i=gap;i<n;++i){ int end=i,key=a[i]; while(end&&a[end]<a[end-gap]){ a[end]=a[end-gap]; end-=gap; } a[end]=key; } } } 3.<选择排序>//不稳定 时间复杂度：不论怎么选都要比较n(n-1)/2次，最好、最坏、平均复杂度都为O（n2） 空间复杂度：O（1） void selectsort(int* a,int n){ int begin=0,end=n-1; while(begin<end){ int min=begin,max=end; for(int i=begin-1;i<end;++i){ if(a[i]<a[min]) min=i; if(a[i]>a[max]) max=i; swap(a[min],a[begin]); if(max==begin){ max=min; } swap(a[max],a[end]); } } }4.<冒泡排序>//稳定 时间复杂度：不论怎么选都要比较n(n-1)/2次，最好、最坏、平均复杂度都为O（n2）//优化的情况例外 空间复杂度：O（1）
void bubblesort(int* a,int n){ for(int i=n;i>1;--i){ int tmp=0; for(int j=0;j<i-1;++j){ if(a[j]>a[j+1]){ swap(a[j],a[j+1]); tmp=1; } if(tmp==0) break; } }5.<堆排序>//不稳定 时间复杂度：时间复杂度为建堆时间复杂度O(n)，重新建堆的时间复杂度为O（nlogn） 空间复杂度：O(1)
//堆排主要需要初始化堆，升序建大堆，降序建小堆 void adjustdown(int* a,int n,int root){ int parent=root; int child=parent*2+1; while(child<n){ if(child+1<n&&a[child]<a[child+1]){ ++child; }//降序找孩子中较大的孩子，如果父节点比其小则交换，否则已经调整结束 if(a[parent]<a[child]){ swap(a[parent],a[child]); parent=child; child=parent*2+1; } else{ break; } } } void heapsort(int* a,int n){ for(int i=(n-2)/2;i>=0;--i){ adjustdown(a,n,i);//遍历数组时间复杂度为O(n) } for(int i=n-1;i>0;--i){ swap(a[0],a[i]); adjustdown(a,i,0);//重新建堆调用n次adjustdown，每次深度为n，所以时间复杂度为O（nlogn） } }6.<快排>//不稳定 时间复杂度：最好O(nlog2n)、最坏O(n2)、平均O(nlog2n) 空间复杂度：O（log2n）/O（n）
//方法1 int quicksort(int* a,int begin,int end){ int mid=三数取中法(a,begin,end); swap(a[mid],a[begin]); int key=a[begin]; int start=begin; while(begin<end){ while(begin<end&&a[end]>=key) --end; while(begin<end&&a[begin]<=key) ++begin; swap(a[begin],a[end]); } swap(a[begin],a[start]);//begin位置的值必定小于start,将start做分界线 return begin; } //挖坑（2） int quicksort(int *a,int begin,int end){ int key=a[begin]; while(begin<end){ while(begin<end&&a[end]>=key) --end; a[begin]=a[end]; while(begin<end&&a[begin]<=key) ++begin; a[end]=a[begin]; } a[begin]=key; return begin; } //前后指针（3） int quicksort(int *a,int begin,int end){ int key=a[begin]; int prev=begin; int cur=begin+1; while(cur<=end){ if(a[cur]<=key&&++prev!=cur){ swap(a[cur],a[prev]); } ++cur; } swap(a[begin],a[prev]); return prev; } //递归 void qsort(int* a,int left,int right){ if(left>=right){ return; } int mid=quicksort(a,0,right); qsort(a,0,mid-1); qsort(a,mid+1,right); } //非递归,用栈模拟递归 void qsort(int* a,int n){ std::stack<int> k; if(n>1){ k.push(0); k.push(n-1); } while(!k.empty()){ int right=k.top(); k.pop(); int left=k.top(); k.pop(); int mid=auicksort(a,left,right); if(mid-1>left){ k.pushback(left); k.pushback(mid-1); } if(mid+1<right){ k.pushback(mid+1); k.pushback(right); } } }7.<归并排序>//不稳定 时间复杂度： 空间复杂度：O（n）
void merge(int* a,int left,int right,int* tmp){ if(left>=right){ return 0; } int mid=left+(right-left)>>1; merge(a,left,mid,tmp); merge(a,mid+1,right,tmp); int begin1=left,end1=mid; int begin2=mid+1,end2=right; int index=left; while(begin1<=end1&&begin2<=end2){ if(a[begin1]<a[begin2]){ tmp[index++]=a[begin1++]; } else tmp[index++]=a[begin++]; } while(begin1<=end1){ tmp[index++]=a[begin1++]; } while(begin2<=end2){ tmp[index++]=a[begin2++]; } memcpy(a+left,tmp+left,sizeof(int)*(right-left+1)); } void mergesort(int* a,int n){ int *tmp=(int*)malloc(sizeof(int)*n); merge(a,0,n-1,tmp); free(tmp); }