复试算法练习Day12

文章目录

• 复试算法练习Day12
• • 题目描述
  • 输入描述：
  • 输出描述：
  • 示例1
  • 思路
  • 具体实现
  • 时间复杂度
  • 小结

题目描述

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

数据范围： 1 \le n \le 1000 \1≤n≤1000 ，字符串长度满足 1 \le len \le 100 \1≤len≤100

输入描述：

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

输出描述：

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

示例1

输入：

9
cap
to
cat
card
two
too
up
boat
boot

复制

输出：

boat
boot
cap
card
cat
to
too
two
up

思路

可以采用冒泡排序的方法，利用简单冒泡排序，在一开始给出字符串的长度初始化之后，构造一个最大数组字符串输出函数

具体实现

//利用冒泡排序写C语言情况下的字符串排序
//按照字典序排列
#include
#include
#include
#define StringMax 100//定义每个字符串的最大长度//构建最大字符串输出函数
void ShowArr(char arr[][StringMax],int n){	for(int i=0;iprintf("%s\n",arr[i]);}}//构建字符串比较，冒泡排序算法函数
void StringSortTest(char str[][StringMax],int n){char tmp[100];int i;//利用简单冒泡排序对于每个字符串按照字典编码要求排序for(i = 0; i < n - 1; i++)for(int j = 0; j < n - i - 1; j++){//利用排在前面的字符串减去排在后面的字符串,//利用strcmp函数来实现字符串的上下变换if(strcmp(str[j], str[j + 1]) > 0) {//如果前一个字符串的首字母排序的时候位置//大于后一个字符串的首字母,//利用strcmp函数进行交换位置strcpy(tmp, str[j]);    strcpy(str[j], str[j + 1]);strcpy(str[j + 1],tmp);}}
}void main(){//输入测试数据，并通过运行函数给出最终结果char TestStr[5][StringMax]={"tofa","nasdck","yfewzb","sjasd","jdwz"};ShowArr(TestStr,5);StringSortTest(TestStr,5);printf("冒泡排序后输出的字符串结果为:\n");ShowArr(TestStr,5);
}

##利用Python实现字符串排序
#利用sorted()函数对所有可迭代类型进行排序。
#这样不改变原始序列，最后返回排序后的新序列。
#输出即可得到结果#通过input()函数输入任意字符串后强制转换为int类型
num = int(input())
#构建数组列表
temp = []
#利用range()函数输出指定范围的所有值
for i in range(num):#在数组列表后面添加元素类型确保可以迭代temp.append(input())#对于列表可迭代元素进行排序，后输出结果
for j in sorted(temp):print(j)

时间复杂度

采用冒泡排序时间复杂度为O(n),采用Python利用数组列表多次迭代遍历排序，也进行了n次运算，时间复杂度也为O(n)

小结

在C语言中采用构建数组，利用冒泡函数比较数组中字母的排序情况，利用strcmp函数来实现字符串的上下变换，经过n次的比较最后可以给出所输入字符串按字典排序的结果。

利用Python中的range函数以及sorted函数，在构建好数组列表的情况下，利用range给出输出范围的所有值，添加可迭代元素后，利用sorted函数进行迭代排序，最后即可输出需要的结果，利用Python中自带函数需考虑强制转换以及数组输出之后转换回字符串的结果，确保输出情况满足要求。