a528 - 大數排序
題目描述
題目要求讀取一組數字（以字串形式表示），並按照從小到大的順序輸出這些數字。數字可能很大，超出一般整數型態的範圍，因此需要以字串形式處理。
解題思路
由於數字可能非常大，無法使用標準的整數排序方法。因此，將數字儲存為字串，然後使用自定義的比較函數進行排序。比較函數首先比較字串的長度，長度較短的字串較小。如果長度相同，則逐字比較字串的每個字符，直到找到不同的字符為止。對於負數，比較函數需要考慮負號，並按照數值大小進行比較。程式碼中，先讀取數字並儲存到字串陣列中，然後使用冒泡排序演算法對字串陣列進行排序。
複雜度分析
- 時間複雜度: O(n^2)，其中 n 是數字的個數。這是因為使用了冒泡排序演算法。
- 空間複雜度: O(n)，其中 n 是數字的個數。這是因為需要儲存字串陣列。
程式碼
#include <iostream>
#include <string>
using namespace std;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int a;
while(cin >> a){
string b[a],tem;
int c[a],tmp;
for(int i=0;i<a;i++){
cin >> b[i];
if(b[i][0]=='-'){
c[i]=-b[i].length();
}
else{
c[i]=b[i].length();
}
}
for(int i=0;i<a;i++){
for(int j=i+1;j<a;j++){
if(c[i]>c[j]){
tmp=c[i];
c[i]=c[j];
c[j]=tmp;
tem=b[i];
b[i]=b[j];
b[j]=tem;
}
else if(c[i]==c[j]&&c[i]>0){
for(int k=0;k<b[i].length();k++){
if(b[i][k]>b[j][k]){
tem=b[i];
b[i]=b[j];
b[j]=tem;
}
}
}
else if(c[i]==c[j]&&c[i]<0){
for(int k=0;k<b[i].length();k++){
if(b[i][k]<b[j][k]){
tem=b[i];
b[i]=b[j];
b[j]=tem;
}
}
}
}
}
for(int i=0;i<a;i++){
cout << b[i] << endl;
}
}
}