資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
