[cpp] /* 排序基礎：冒泡，起泡... 注意加等號的意義何在... */ #include<iostream> #include<cstdio> using namespace std; #define manx 5000 int x[manx]; void sort(int n){ //// 冒泡 for(int i=0;i<n;i++) for(int j=1;j<n-i;j++) if(x[j-1]>=x[j]) swap(x[j-1],x[j]); //////加等號 } void sort1(int n){ /// 起泡 for(int i=0;i<n;i++) for(int j=n-1;j>i;j--) if(x[j-1]>=x[j]) swap(x[j-1],x[j]); //////加等號 } int main(){ int n; while(cin>>n){ for(int i=0;i<n;i++) scanf("%d",&x[i]); sort1(n); for(int i=0;i<n;i++) printf("%d ",x[i]); printf("\n"); } } [cpp] /* 選擇排序：時間復雜度 n^2 ..注意模型，把模型翻譯成代碼，OK， 每次從 i+1 ~ n 中找出最小的值與 i 交換 */ #include<iostream> #include<cstdio> using namespace std; #define manx 5000 int x[manx]; void sort(int n){ for(int i=1;i<n;i++){ int temp = x[i]; int ans = i; //// 記錄位置 for(int j=i+1;j<=n;j++){ if(x[j]<temp) { temp = x[j]; ans = j; } } if(ans!=i) swap(x[i],x[ans]); } } int main(){ int n; while(cin>>n){ for(int i=1;i<=n;i++) scanf("%d",&x[i]); sort(n); for(int i=1;i<=n;i++) printf("%d ",x[i]); printf("\n"); } } [cpp] /* 歸並排序：我的程序有些缺陷，實現的時間復雜度是 2n*lgn（待優化） .. 開的數組可以使用動態開辟，從而節省空間.. 所以其他的也沒什麼的，不用寫的很復雜... */ #include<iostream> #include<cmath> using namespace std; #define manx 1000009 int x[manx]; void sort(int st,int ed){ if(st==ed) return ; int mid=(st+ed)>>1; sort(st,mid); sort(mid+1,ed); int flag = st; int *z = new int[manx]; for(int i=st,j=mid+1; i<=mid || j<=ed; ){ ///////// if( i>mid ) { ///////// z[flag++] = x[j]; j++; continue; } if( j>ed ) { ////////// z[flag++] = x[i]; i++; continue; } if(x[i]<=x[j]){ //// 注意等號的意義... z[flag++] = x[i]; i++; continue; } if(x[i]>x[j]){ z[flag++] = x[j]; j++; continue; } } for(int i=st;i<=ed;i++) x[i]=z[i]; ////蛋疼..這裡花多了一倍的時間..待優化 delete []z; return ; } int main(){ int n; while(cin>>n){ for(int i=1;i<=n;i++) scanf("%d",&x[i]); sort(1,n); for(int i=1;i<=n;i++) cout<<x[i]<<" "; cout<<endl; } }
