数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究按字典序排序字符串数组
在这个问题中，我们将按字典序对字符串数组进行排序。
有多种排序算法可以对字符串数组进行排序。在本教程中，我们将使用内置的 sort() 方法对字符串进行排序。此外，我们还将使用归并排序算法，这是对字符串数组进行排序的有效方法之一。
问题陈述 − 我们给定一个包含 N 个字符串的 str[] 数组。我们需要按字典序对所有字符串进行排序。
示例
输入
str[] = {"tutorials", "point", "save", "java", "c++"}
输出
c++, java, point, save, tutorials
解释 − 我们按字典序对字符串进行了排序。
输入
str[] = {"aad", "aab", "aaa", "aac", "cpp"};
输出
aaa, aab, aac, aad, cpp
输入
str[] = {"ztbq", "ytrc", "ppp", "ppp", "ppp"};
输出
ppp, ppp, ppp, ytrc, ztbq
方法 1
在这种方法中，使用 C++ 的 sort() 方法对字符串数组进行排序。
示例
在下面的示例中，我们将“str”字符串作为 sort() 方法的第一个参数，并将 str + len 作为 sort() 方法的第二个参数。它以起始和结束索引的引用作为参数。
之后，我们打印数组中的所有字符串。在输出中，我们可以观察到排序后的字符串数组。
#include <bits/stdc++.h>
using namespace std;
void sortElements(int len, string str[]) {
// Sort strings
sort(str, str + len);
for (int p = 0; p < len; p++) {
cout << str[p] << endl;
}
}
int main() {
string str[] = {"tutorials", "point", "save", "java", "c++"};
int len = sizeof(str) / sizeof(str[0]);
sortElements(len, str);
return 0;
}
输出
c++ java point save tutorials
时间复杂度 − O(NlogN)
空间复杂度 − 由于快速排序的递归调用，为 O(logN)。
方法 2
在这种方法中，我们将使用归并排序算法按字典序对字符串数组进行排序。归并排序基于分治策略。我们递归地将数组分成两部分，并对这两部分进行排序，同时将其合并到实际数组中。
算法
步骤 1 − 如果“left”小于“right”，则执行以下步骤。我们将“left”和“right”作为参数。
步骤 2 − 获取中间索引。
步骤 3 − 分别对左右部分调用 sortStrings() 函数。
步骤 4 − 最后，执行 mergeArray() 函数以在排序后合并左右部分。
步骤 4.1 − 在 mergeArray() 函数中，将“leftLen”初始化为左部分的长度，将“rightLen”初始化为数组右部分的长度。此外，定义长度为“leftLen”的“leftArr”和长度为“rightLen”的“rightArr”。
步骤 4.2 − 使用原始数组的元素初始化 leftArr 和 rightArr。
步骤 4.3 − 将 p、q 初始化为 0，并将 K 初始化为 left。
步骤 4.4 − 在 p 小于 leftLen 且 q 小于 right Len 时进行迭代。
步骤 4.5 − 如果 leftArr[p] 小于 rightArr[q]，则使用 leftArr[p] 更新 str[k]，并将 p 加 1。否则，使用 rightArr[q] 更新 str[k]，并将 q 加 1。此外，递增 k 值。
步骤 4.6 − 将 leftArr[] 的剩余元素添加到 str[] 数组中。此外，将 rightArr[] 的剩余元素添加到 str[] 数组中。
示例
#include <bits/stdc++.h>
using namespace std;
void mergeArray(string str[], int left, int mid, int right) {
int leftLen = mid - left + 1;
int rightLen = right - mid;
string leftArr[leftLen], rightArr[rightLen];
// Store string in temmporary array
for (int p = 0; p < leftLen; p++)
leftArr[p] = str[left + p];
for (int q = 0; q < rightLen; q++)
rightArr[q] = str[mid + 1 + q];
int p = 0;
int q = 0;
int k = left;
// sort and merge
while (p < leftLen && q < rightLen) {
// Update str array with sorted elements
if (leftArr[p] <= rightArr[q]) {
str[k] = leftArr[p];
p++;
} else {
str[k] = rightArr[q];
q++;
}
k++;
}
// Append remaining elements of leftArr[]
while (p < leftLen) {
str[k] = leftArr[p];
p++;
k++;
}
// Append remaining elements of rightArr[]
while (q < rightLen) {
str[k] = rightArr[q];
q++;
k++;
}
}
void sortStrings(string str[], int left, int right) {
if (left < right) {
// Get middle index
int mid = left + (right - left) / 2;
// Sort the left half
sortStrings(str, left, mid);
// Sort the right half
sortStrings(str, mid + 1, right);
// Merge both halves
mergeArray(str, left, mid, right);
}
}
int main() {
string str[] = {"tutorials", "point", "save", "java", "c++"};
int arrLen = sizeof(str) / sizeof(str[0]);
sortStrings(str, 0, arrLen - 1);
cout << "\nSorted array is - ";
for (int p = 0; p < arrLen; p++)
cout << str[p] << " ";
return 0;
}
输出
Sorted array is − c++ java point save tutorials
时间复杂度 − 对数组的每个部分进行排序，时间复杂度为 O(NlogN)。
空间复杂度 − 在临时数组中存储元素，空间复杂度为 O(N)。
我们使用了 sort() 方法和归并排序算法对字符串数组进行排序。sort() 方法结合了堆排序、快速排序和插入排序，使排序算法更快。但是，程序员可以使用冒泡排序或选择排序来对字符串数组进行排序。
842 次查看
