使用选择排序对字符串中的字符进行排序

Question

我的代码有什么错误？

Given a string consisting of lowercase letters, arrange all its letters in ascending order.

Input: The first line of the input contains T, denoting number of testcases. Then follows description of each testcase. The first line of the testcase contains positive integer N denoting the length of string. The second line contains the string.

Output: For each testcase, output the sorted string.

Constraints:
1 <= T <= 100
1 <= N <= 100

import java.util.*;
class GFG {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 1; i <= t; i++) {
            int n = sc.nextInt();
            sc.nextLine();
            String S = sc.nextLine();
            String sor = "";
            for (int j = 0; j < n; j++) {
                int min = j;
                for (int k = j + 1; k < n; k++) {
                    if (S.charAt(k) > S.charAt(min)) {
                        min = k;
                    }
                }
                sor += S.substring(min, min + 1);
            }
            System.out.println(sor);
        }
    }
}

对于输入：

1
5
edcab

输出：

edcbb

预期输出：

abcde

Answer 1

你不是在找到 min 字符后交换它的位置。但是 java 中的 String 是不可变的，所以你不能交换其中字符的位置。我建议您将字符串转换为 char[] 以便您可以交换字符：


public static void main (String[] args){
     Scanner sc = new Scanner(System.in);
     int t = sc.nextInt();
     for(int i=1; i<=t; i++){
         int n = sc.nextInt();
         sc.nextLine();
         String S = sc.nextLine().toCharArray(); // convert it to char array
         char[] sor = new char[S.length];
         for(int j=0; j<n; j++){
             int min = j;
             for(int k =j+1; k<n; k++){
                 if(S[k]<S[min]){
                     min = k;
                 }
             }
             swap(S, min, j);
             sor[j] = S[min]
         }
         System.out.println(new String(sor));// reconvert to string
     }
}
public static void swap(char[] c,int x,int y){
    char temp= c[x];
    c[x] = c[y];
    c[y] = temp;
}

Answer 2

import java.util.*;

class GFG {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 1; i <= t; i++) {
            int n = sc.nextInt();
            sc.nextLine();
            
            String S = sc.nextLine();
            System.out.println("S: "+S);
            String sor = "";
            for (int j = 0; n > 0; j++) {
                int min = 0;
                for (int k = 0; k < n; k++) {
                    if (S.charAt(k) < S.charAt(min)) {
                        min = k;
                    }
                }
                sor += S.substring(min, min + 1);
                S = S.substring(0, min) + S.substring(min + 1);
                n--;
            }
            System.out.println(sor);
        }
    }
}

这段代码可以满足您的需求。我将 > 更改为 <，并从未排序的字符串中删除了添加到已排序字符串的每个字符。这样我们就不需要一次又一次地处理同一个字符。

Answer 3

您可以使用String.toCharArray方法遍历此字符串的字符数组char[]，对它们的十进制值进行排序，然后return返回包含已排序字符的字符串数组：

public static void main(String[] args) {
    String str = "edcab";
    String sorted = selectionSort(str.toCharArray());
    System.out.println(sorted); // abcde
}

public static String selectionSort(char[] arr) {
    // iterate over all subsets of the array
    // (0-last, 1-last, 2-last, 3-last, ...)
    for (int i = 0; i < arr.length; i++) {
        // assume the min is
        // the first element
        char min = arr[i];
        // index of the
        // min element
        int min_i = i;
        // check the elements
        // after i to find
        // the smallest
        for (int j = i + 1; j < arr.length; j++) {
            // if this element
            // is less, then it
            // is the new min
            if (arr[j] < min) {
                min = arr[j];
                min_i = j;
            }
        }
        // if min element is not
        // equal to the current
        // one, then swap them
        if (i != min_i) {
            char temp = arr[i];
            arr[i] = arr[min_i];
            arr[min_i] = temp;
        }
    }
    return String.valueOf(arr);
}

您可以使用String.codePoints方法遍历此字符串字符的int个值，对它们进行排序并收集另一个排序后的字符串：

String str = "edcab";

String sorted = str.codePoints()
        .sorted()
        .mapToObj(Character::toString)
        .collect(Collectors.joining());

System.out.println(sorted); // abcde

^{另请参阅：

•

• Java Selection Sort}

使用选择排序对字符串中的字符进行排序

Sorting characters in a string using selection sort

java

string

sorting

selection-sort