排序算法大合集
课后习题正好可以直接测试一遍各个排序算法,以前写代码只会熟练的写冒泡排序,经常在OJ上过不了说是时间复杂度太大,今天趁这个题,练练手,可能还有待优化的代码,望多多指教呀~
1.冒泡排序
**经典的教科书算法,时间复杂度 空间复杂度O(1)**
#include <iostream> using namespace std; int main() { int num; while(cin>>num) { int *p=new int [num]; int i,flag; for(i=0;i<num;i++) cin>>p[i]; cin>>flag; for(i=0;i<num;i++) { for(int j=i;j<num;j++) { int temp; if(flag==1 && p[i]<p[j]) { temp=p[i]; p[i]=p[j]; p[j]=temp; } if(flag==0 && p[i]>p[j]) { temp=p[i]; p[i]=p[j]; p[j]=temp; } } } for(i=0;i<num;i++) cout<<p[i]<<' '; cout<<endl; } }
选择排序
时间复杂度O(n^2) 空间复杂度O(1)
从小到大。
#include "iostream" using namespace std; int main() { int n,i=0; cin >> n; int *p=new int[n]; for (i = 0; i < n; i++) cin >> p[i]; for (i=0; i < n; i++) { int minindex = i; for (int j = i; j < n; j++) { if (p[j] < p[minindex]) { minindex = j; } } int tep = p[minindex]; p[minindex] = p[i]; p[i] = tep; } for (i = 0; i < n; i++) cout << p[i] << " "; delete[]p; return 0; }
归并排序:
#include <iostream> using namespace std; void merge(int *p,int left,int mid,int right); void process(int *p,int left,int right); int main() { int num; while(cin>>num) { int *p=new int [num]; int i,flag; for(i=0;i<num;i++) cin>>p[i]; cin>>flag; //mergeSort过程 process(p,0,num-1); //按照flag进行输出: if(flag==0) { for(i=0;i<num;i++) cout<<p[i]<<' '; } if(flag==1) { for(i=num-1;i>=0;i--) cout<<p[i]<<' '; } cout<<endl; } } void merge(int *p,int left,int mid,int right) { int w1=left,w2=mid+1,i=0; int *help=new int[right-left+1]; while(w1<=mid && w2<=right) //按照从小到大进行merge { if(p[w1]<=p[w2]) { help[i]=p[w1]; i++; } else { help[i]=p[2]; i++; } } while(w1<=mid) { help[i]=p[w1]; i++; } while(w2<=right) { help[i]=p[w1]; i++; } for(i=0;i<right-left;i++) { p[i]=help[i]; } } void process(int *p,int left,int right) { if(left==right) { return; } int mid=left+(left+right)/2; process(p,left,mid); process(p,mid+1,right); merge(p,left,mid,right); }