CareerCup

// Use bucket sort 
//Time complexity: O(N+K)
//Space: O(K)

class Sorting
{
	public static void main (String[] args) throws java.lang.Exception
	{
		System.out.println(sorting("a390testai")); // output: 039aaeistt
	}
	
	public static String sorting(String str) {
		if (str == null || str.length() == 0)
			return str;
		
		ArrayList<Character>[] al = new ArrayList[80]; 	
		for (char c: str.toCharArray()) {
			if (c - '0' >= 0) {
				if (al[c - '0'] == null)
					al[c - '0'] = new ArrayList<Character>();
				al[c - '0'].add(c);	
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for (List<Character> list: al) {
			if (list == null) continue;
			for (char c: list) {
				sb.append(c);
			}
		}
		
		return sb.toString();
	}
}

You could implement any sort also (merge or quicksort). Make sure the comparison is done 
on the ascii values of these characters. This will give then sorted string.

static String sortString(String s){
String result="";
int[] asciiArr= new int[256];
for(int i=0; i<s.length();i++){
asciiArr[s.charAt(i)]+=1;

}
for(int i=0; i<256; i++){
if(asciiArr[i]>0){
for(int j=0; j<asciiArr[i]; j++){
result+=(char)i;

}
}
}

return result;
}

class Sorting
{
	public static void main (String[] args) throws java.lang.Exception
	{
		System.out.println(sortString("a390testai")); // output: 039aaeistt
	}

	public static String sortString (String str){
		String result = "";
		String[] arr = new String[256];
		for (char c: str.toCharArray()) {
			int index = c - '0';
			arr[index] = c + getNonNullVal(arr[index]);
		}
		for (String s : arr) {
			result += getNonNullVal(s);
		}
		return result;
	}
	
	private static String getNonNullVal(String s){
		return (s == null) ? "" : s;
	}

I/P: "a390testai"
O/P: "039aaeistt"

String originalString = "a390testai";
        List<Character> originalArrayList = new ArrayList<>();
        for(char c : originalString.toCharArray())
            originalArrayList.add(c);
        System.out.println(originalArrayList);
        String sortedString = "";
        while (originalArrayList.size() > 0) {
            char minChar = originalArrayList.get(0);
            for (int i=1; i<originalArrayList.size(); i++) {
                if(minChar > originalArrayList.get(i))
                    minChar = originalArrayList.get(i);
            }
            sortedString += minChar;
            originalArrayList.remove((Character) minChar);
        }
        System.out.println(sortedString);

String originalString = "a390testai";
        List<Character> originalArrayList = new ArrayList<>();
        for(char c : originalString.toCharArray())
            originalArrayList.add(c);
        System.out.println(originalArrayList);
        String sortedString = "";
        while (originalArrayList.size() > 0) {
            char minChar = originalArrayList.get(0);
            for (int i=1; i<originalArrayList.size(); i++) {
                if(minChar > originalArrayList.get(i))
                    minChar = originalArrayList.get(i);
            }
            sortedString += minChar;
            originalArrayList.remove((Character) minChar);
        }
        System.out.println(sortedString);

String originalString = "a390testai";
        List<Character> originalArrayList = new ArrayList<>();
        for(char c : originalString.toCharArray())
            originalArrayList.add(c);
        System.out.println(originalArrayList);
        String sortedString = "";
        while (originalArrayList.size() > 0) {
            char minChar = originalArrayList.get(0);
            for (int i=1; i<originalArrayList.size(); i++) {
                if(minChar > originalArrayList.get(i))
                    minChar = originalArrayList.get(i);
            }
            sortedString += minChar;
            originalArrayList.remove((Character) minChar);
        }
        System.out.println(sortedString);