给定 n 个字符串,请对 n 个字符串按照字典序排列。
数据范围: ,字符串长度满足
输入第一行为一个正整数n(1≤n≤1000),下面n行为n个字符串(字符串长度≤100),字符串中只含有大小写字母。
数据输出n行,输出结果为按照字典序排列的字符串。
9 cap to cat card two too up boat boot
boat boot cap card cat to too two up
#include<iostream> #include<string> #include<vector> using namespace std; int main(){ int n; while (cin>>n){ if (!n) continue; vector<string> v; for (int i = 0; i<n; ++i){ string temp; cin >> temp; int j = 0; for (; j < i && temp >= v[j]; ++j); v.insert(v.begin() + j, temp); } for (int i = 0; i < v.size(); ++i){ cout << v[i] << endl; } } return 0; }
#include<stdio.h> #include<string.h> //排序 void sort(int n, char str[1001][101]) { int flag = 0; //排序结束标志位 for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { char move[101]; if (strcmp(str[j], str[j + 1]) > 0) { strcpy(move, str[j]); strcpy(str[j], str[j + 1]); strcpy(str[j + 1], move); flag = 1; } } if (flag = 0) break; } } int main() { char str[1001][101] = {'\0'}; int n; while (~scanf("%d", &n)) { for (int i = 0; i < n; i++) { scanf("%s", str[i]); // printf("%s\n",str[i]); } sort(n, str); for (int j = 0; j < n; j++) printf("%s\n", str[j]); } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner sr=new Scanner(System.in); while(sr.hasNext()) { //int n=Integer.parseInt(sr.nextLine()); int n=sr.nextInt(); //使用这种输入编译会报数组越界错误,用上面方法输入就能编译通过,这是为什么啊? String[] str=new String[n]; for(int i=0;i<n;i++) str[i]=sr.nextLine(); Arrays.sort(str); for(int i=0;i<n;i++) System.out.println(str[i]); } } }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner scanner = new Scanner(System.in); ArrayList<String> in = new ArrayList<String>(); while(scanner.hasNext()){ in.add(scanner.nextLine()); } Collections.sort(in); for (int i = 1; i < in.size(); i++){ System.out.println(in.get(i)); } } }
#include<iostream> #include<vector> #include<algorithm> using namespace std; int main(){ string tmp; string str; int n; cin>>n; vector<string>res(n); res.clear(); while(cin>>tmp) res.emplace_back(tmp); sort(res.begin(),res.end(),[](string &a,string &b){ return a<b; }); for(int i=0;i<n;++i){ cout<<res[i]<<endl; } return 0; }
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; string s; map<string, int> map; for (int i = 0; i < n; i++) { cin >> s; map[s] += 1; } for (auto i : map) { for (int k = 0; k < i.second; k++) { cout << i.first << endl; } } return 0; }
lists = [] def cmp(s1, s2): l = len(s2) if s1 == s2: return True for i, c1 in enumerate(s1): if i >= l: return 1 c2 = s2[i] if c1 != c2: return ord(c1) - ord(c2) return len(s1) - len(s2) def fun2(s1, s2): l = len(s2) if s1 == s2: return True for i, c1 in enumerate(s1): if i >= l: return False c2 = s2[i] if c1 > c2: return False elif c1 < c2: return True return False def quick_sort(i, j): if i >= j: return lists low, high = i, j p = lists[i] while i<j: while i < j and cmp(lists[j], p) >= 0: j -= 1 lists[i] = lists[j] while i < j and cmp(lists[i], p) <= 0: i += 1 lists[j] = lists[i] lists[i] = p quick_sort(low, i-1) quick_sort(i+1, high) while True: try: n = int(input()) lists = [] for i in range(n): lists.append(input()) quick_sort(0, len(lists) - 1) for s in lists: print(s) except EOFError: break
不用直接交换字符串,可以设置一个指针数组指向每一个串的首地址,然后对这个指针数组进行排序即可。使用快速排序算法:
#include <stdio.h> #include <string.h> char ss[1000][101]; char* ps[1000]; void swap(int i, int j) { char* tmp = ps[i]; ps[i] = ps[j]; ps[j] = tmp; } int partition(int p, int r) { char* pivot = ps[r]; int i = p - 1, j; for (j = p; j <= r - 1; ++j) { if (strcmp(ps[j], pivot) <= 0) { ++i; if (i != j) swap(i, j); } } swap(i + 1, j); return i + 1; } void qsort(int p, int r) { if (p >= r) return; int q = partition(p, r); qsort(p, q - 1); qsort(q + 1, r); } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%s", ss[i]); ps[i] = ss[i]; } qsort(0, n - 1); for (int i = 0; i < n; ++i) printf("%s\n", ps[i]); return 0; }
#include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; int main() { int n; string s; vector<string> v; cin >> n; while(n-- && cin >> s) v.push_back(s); sort(v.begin(), v.end()); for(auto it=v.begin();it!=v.end();it++) cout<< *it << endl; return 0; }我承认不应该用泛型算法,但是sort()函数真香!
#include <stdlib.h> #include <stdio.h> #include <string.h> #define N_STRS 1000 #define STR_LEN 100 void str_quick_sort(char str[N_STRS][STR_LEN], int low, int high) { char *temp = (char *)malloc(sizeof(char) * STR_LEN); int i=low, j=high; if(low < high) { strcpy(temp, str[low]); while(i != j) { while(j>i && strcmp(str[j], temp)>0) --j; if(i<j) { strcpy(str[i],str[j]); ++i; } while(i<j && strcmp(str[i], temp)<0) ++i; if(i<j) { strcpy(str[j],str[i]); --j; } } strcpy(str[i],temp); str_quick_sort(str, low, i-1); str_quick_sort(str, i+1, high); } } int main() { char str[N_STRS][STR_LEN] = {'\0'}; int n; scanf("%d\n", &n); for(int i=0; i<n; i++) { scanf("%s\n", str[i]); } str_quick_sort(str, 0, n-1); for(int i=0; i<n; i++) { printf("%s\n", str[i]); } return 0; }
import sys n = int(sys.stdin.readline().strip()) a, result = [], [] for i in range(n): a.append(sys.stdin.readline().strip()) for n1 in range(n,1,-1): for i in range(n1-1): j = 1 pos1, pos2 = ord(a[i][0]), ord(a[i+1][0]) while pos1 == pos2 and j<min(len(a[i]),len(a[i+1])): pos1, pos2 = ord(a[i][j]), ord(a[i+1][j]) j += 1 if pos1 == pos2: pos1, pos2 = len(a[i]), len(a[i+1]) if pos1 > pos2: a[i:i+2] = [a[i+1],a[i]] for i in range(n): print(a[i])用C的思路写的python,然而实际python一个函数就能搞定
import java.util.*; public class Main{ public static void main(String[] args){ Scanner scanner = new Scanner(System.in); int num = scanner.nextInt(); List<String> result = new ArrayList<>(); for (int i = 0; i < num; i++){ result.add(scanner.next()); } Collections.sort(result); for (int j = 0; j < result.size(); j++){ System.out.println(result.get(j)); } } }