14、字串的连接最长路径查找

题目描述

给定n个字符串，请对n个字符串按照字典序排列。

输入描述:

输入第一行为一个正整数n(1≤n≤1000),下面n行为n个字符串(字符串长度≤100),字符串中只含有大小写字母。

输出描述:

数据输出n行，输出结果为按照字典序排列的字符串。

---

c++ code： version 1

#include<iostream> #include <string> #define MAX 1000 using namespace std; int main(){ string str[MAX]; int n; string temp = ""; cin >> n; for (int i = 0; i < n;i++) { cin >> str[i]; } for (int i = 0; i < n-1;i++)//冒泡排序 { for (int j = i + 1; j < n; j++) { if (str[i] > str[j]) { temp = str[j]; str[j] = str[i]; str[i] = temp; } } } for (int i = 0; i < n;i++) { cout << str[i] << endl; } return 0; }

version 2

#include<iostream> #include <string> #include <algorithm> #define MAX 1000 using namespace std; int main(){ string str[MAX]; int n; cin >> n; for (int i = 0; i < n;i++) { cin >> str[i]; } sort(str,str+n); for (int i = 0; i < n;i++) { cout << str[i] << endl; } return 0; }

idea：

1、string是可以比较大小的，并且比较的大小就是字典原则。 2、version 1用的冒泡排序，这个时间复杂度 n*n 测试性能：时间3ms，内存369k version 2用的库里面的sort直接排序，这个时间复杂度 n·log n 测试性能：时间3ms，内存500k 再开一个分章节14.1，介绍时间复杂度的。