本文概述
给定一个由n个字符串组成的数组。任务是按排序顺序打印字符串。该方法应确保在排序过程中不应将任何字符串复制到另一个字符串。
例子:
Input : {"geeks", "for", "geeks", "quiz")
Output : for geeks geeks quiz
Input : {"ball", "pen", "apple", "kite"}
Output : apple ball kite pen
推荐:请尝试使用{IDE}首先, 在继续解决方案之前。
方法:它具有以下步骤:
- 维护另一个阵列indexed_arr存储/维护每个字符串的索引。
- 我们可以对此应用任何排序技术indexed_arr.
插图:
--> str[] = {"world", "hello"}
--> corresponding index array will be
indexed_arr = {0, 1}
--> Now, how the strings are compared and
accordingly values in indexed_arr are changed.
--> Comparison process:
if (str[index[0]].compare(str[index[1]] > 0
temp = index[0]
index[0] = index[1]
index[1] = temp
// after sorting values of
// indexed_arr = {1, 0}
--> for i=0 to 1
print str[index[i]]
This is how the strings are compared and their
corresponding indexes in the indexed_arr
are being manipulated/swapped so that after the sorting process
is completed, the order of indexes in the indexed_arr
gives us the sorted order of the strings.
C ++
// C++ implementation to print array of strings in sorted
// order without copying one string into another
#include <bits/stdc++.h>
using namespace std;
// function to print strings in sorted order
void printInSortedOrder(string arr[], int n)
{
int index[n];
int i, j, min;
// Initially the index of the strings
// are assigned to the 'index[]'
for (i=0; i<n; i++)
index[i] = i;
// selection sort technique is applied
for (i=0; i<n-1; i++)
{
min = i;
for (j=i+1; j<n; j++)
{
// with the help of 'index[]'
// strings are being compared
if (arr[index[min]].compare(arr[index[j]]) > 0)
min = j;
}
// index of the smallest string is placed
// at the ith index of 'index[]'
if (min != i)
{
int temp = index[min];
index[min] = index[i];
index[i] = temp;
}
}
// printing strings in sorted order
for (i=0; i<n; i++)
cout << arr[index[i]] << " " ;
}
// Driver program to test above
int main()
{
string arr[] = { "geeks" , "quiz" , "geeks" , "for" };
int n = 4;
printInSortedOrder(arr, n);
return 0;
}
Java
//Java implementation to print array of strings in sorted
// order without copying one string into another
class GFG {
// function to print strings in sorted order
static void printInSortedOrder(String arr[], int n) {
int index[] = new int [n];
int i, j, min;
// Initially the index of the strings
// are assigned to the 'index[]'
for (i = 0 ; i < n; i++) {
index[i] = i;
}
// selection sort technique is applied
for (i = 0 ; i < n - 1 ; i++) {
min = i;
for (j = i + 1 ; j < n; j++) {
// with the help of 'index[]'
// strings are being compared
if (arr[index[min]].compareTo(arr[index[j]]) > 0 ) {
min = j;
}
}
// index of the smallest string is placed
// at the ith index of 'index[]'
if (min != i) {
int temp = index[min];
index[min] = index[i];
index[i] = temp;
}
}
// printing strings in sorted order
for (i = 0 ; i < n; i++) {
System.out.print(arr[index[i]] + " " );
}
}
// Driver program to test above
static public void main(String[] args) {
String arr[] = { "geeks" , "quiz" , "geeks" , "for" };
int n = 4 ;
printInSortedOrder(arr, n);
}
}
// This code is contributed by 29AjayKumar
Python 3
# Python 3 implementation to print array
# of strings in sorted order without
# copying one string into another
# function to print strings in sorted order
def printInSortedOrder(arr, n):
index = [ 0 ] * n
# Initially the index of the strings
# are assigned to the 'index[]'
for i in range (n):
index[i] = i
# selection sort technique is applied
for i in range (n - 1 ):
min = i
for j in range (i + 1 , n):
# with the help of 'index[]'
# strings are being compared
if (arr[index[ min ]] > arr[index[j]]):
min = j
# index of the smallest string is placed
# at the ith index of 'index[]'
if ( min ! = i):
index[ min ], index[i] = index[i], index[ min ]
# printing strings in sorted order
for i in range (n):
print (arr[index[i]], end = " " )
# Driver Code
if __name__ = = "__main__" :
arr = [ "geeks" , "quiz" , "geeks" , "for" ]
n = 4
printInSortedOrder(arr, n)
# This code is contributed by ita_c
C#
//C# implementation to print an array of strings in sorted
// order without copying one string into another
using System;
public class GFG {
// function to print strings in sorted order
static void printInSortedOrder(String []arr, int n) {
int []index = new int [n];
int i, j, min;
// Initially the index of the strings
// are assigned to the 'index[]'
for (i = 0; i < n; i++) {
index[i] = i;
}
// selection sort technique is applied
for (i = 0; i < n - 1; i++) {
min = i;
for (j = i + 1; j < n; j++) {
// with the help of 'index[]'
// strings are being compared
if (arr[index[min]].CompareTo(arr[index[j]]) > 0) {
min = j;
}
}
// index of the smallest string is placed
// at the ith index of 'index[]'
if (min != i) {
int temp = index[min];
index[min] = index[i];
index[i] = temp;
}
}
// printing strings in sorted order
for (i = 0; i < n; i++) {
Console.Write(arr[index[i]] + " " );
}
}
// Driver program to test above
static public void Main() {
String []arr = { "geeks" , "quiz" , "geeks" , "for" };
int n = 4;
printInSortedOrder(arr, n);
}
}
// This code is contributed by 29AjayKumar
输出如下:
for geeks geeks quiz
时间复杂度:上2)
当我们必须最小化数量时, 可以使用该方法光盘刻录就像一系列结构一样。比较结构值, 但不交换它们的值, 而是将它们的索引保存在另一个数组中, 对该数组进行操作以使索引保持顺序, 该顺序代表结构的排序数组。
行使:在合并排序, 插入排序等其他排序技术的帮助下应用此方法。
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。