Sortowanie ArrayList mieszane liczb i ciągów zachowując względną kolejność łańcuchów i liczb

Question

Rozważmy ArrayList jak podano poniżej

unsortedList = {6,"ball",3,1,"apple","cat",4} 

to musi być klasyfikowane do

sortedList = {1,"apple",3,4,"ball","cat",6} 

Sortuj struny alfabetycznie. Sortuj liczby rosnąco. Ale zanotuj następujący warunek:

• Gdziekolwiek na liście nieposortowanej znajduje się liczba całkowita, musi ona być liczbą całkowitą na posortowanej liście.
• Wszędzie tam, gdzie na liście nieposortowanej znajduje się ciąg, musi to być ciąg na posortowanej liście.

Zauważmy, że w powyższym przykładzie, wszystkie liczby całkowite zostały posortowane rosnąco, a wszystkie ciągi są posortowane rosnąco, ale względne położenia liczb całkowitych i ciągi pozostaje niezmieniona od wcześniej.

Answer 1

Jedną z opcji jest, aby wykonać następujące czynności:

• Utwórz nową listę wszystkich liczb całkowitych na pierwotnej liście.
• Utwórz nową listę wszystkich ciągów z oryginalnej listy.
• Sortowanie każdej listy.
• Iterate na pierwotnej liście, wykonując następujące czynności:
  • Jeśli element nie jest liczbą całkowitą, odpisać następnego niepisaną całkowitą od posortowanej listy całkowitej.
  • Jeśli element zawiera ciąg znaków, napisz następny niepisany ciąg z posortowanej listy ciągów.

Jest całkiem wydajny - wystarczy zrobić dwa rodzaje. Oto kod:

public void relativeOrderSort(List<Object> list) { 
    /* Create a list of just the integers and just the strings 
    * from the original list. 
    */ 
    List<Integer> intList = new ArrayList<Integer>(); 
    List<String> strList = new ArrayList<String>(); 
    for (Object obj: list) { 
     if (obj instanceof Integer) { 
      intList.add((Integer) obj); 
     } else if (obj instanceof String) { 
      strList.add((String) obj); 
     } else { 
      throw new IllegalArgumentException("List has a non-int, non-string member."); 
     } 
    } 

    /* Sort the lists. */ 
    Collections.sort(intList); 
    Collections.sort(strList); 

    /* Merge the lists back together. */ 
    int intIndex = 0, strIndex = 0; 
    for (int i = 0; i < list.size(); i++) { 
     if (list.get(i) instanceof Integer) { 
      list.set(i, intList.get(intIndex++)); 
     } else { 
      list.set(i, strList.get(strIndex++)); 
     } 
    } 
} 

Mam nadzieję, że to pomoże!

Answer 2

Pseudo kod:

Create a list of the indices pointing to integers ({0,2,3,6} in your case - indxInt) 
Sort the integers ({6,3,1,4} turns into {1,3,4,6}) 
Put them back at the locations given by the pointers: 
    sorted(indxInt(0)) = 1; 
    sorted(indxInt(1)) = 3; 
    sorted(3) = 4; // indxInt(2) == 3 
    sorted(6) = 6; // indxInt(3) == 6 
Repeat for the strings