Сортировка ArrayList с использованием предопределенного списка индексов

Question

Я пытаюсь сортировать ArrayList с помощью предопределенного массива индексов. Мой текущий пример использует копию оригинального ArrayList для сортировки и, следовательно, не является масштабируемым для ArrayLists более крупных объектов

package sortExample; 

import java.awt.List; 
import java.util.ArrayList; 
import java.util.Arrays; 

public class sortExample { 

    public static void main(String[] args) { 

     String [] str = new String[] {"a","b","c","d"}; 
     ArrayList<String> arr1 = new ArrayList<String>(Arrays.asList(str)); 

     int [] indices = {3,1,2,0}; 

     ArrayList<String> arr2 = new ArrayList(arr1.size()); 

     for (int i = 0; i < arr1.size(); i++) { 
      arr2.add("0"); 
     } 

     int arrIndex = 0; 
     for (int i : indices){ 
      String st = arr1.get(arrIndex); 
      arr2.set(i, st); 
      arrIndex++; 
     } 

     System.out.println(arr1.toString()); 
     System.out.println(arr2.toString()); 
    } 

} 

Answer 1

Для повторного использования те же данные, пожалуйста, см мое решение:

public static void main(String[] args) { 

    String[] strs = new String[]{"a", "b", "c", "d"}; 
    int[] indices = {3, 1, 2, 0}; 

    String tmp; 
    for (int i = 0; i < strs.length; i++) { 
     if (i != indices[i]) { 
      tmp = strs[i]; 
      strs[i] = strs[indices[i]]; 
      strs[indices[i]] = tmp; 

      indices[indices[i]] = indices[i]; 
      indices[i] = i; 
     } 
    } 

    for (int i : indices) { 
     System.out.print(i + " "); 
    } 
    System.out.println(); 
    for (String str : strs) { 
     System.out.print(str + " "); 
    } 
} 

Выход есть:

DBCA

Answer 2

Существует а (немного) более простое решение:

int [] indices = {3,1,2,0}; 
ArrayList<String> arr2 = new ArrayList<String>(); 

for (int i = 0; i < arr1.size(); i++) { 
    arr2.add(arr1.get(indices[i])); 
} 

Answer 3

Альтернативный перезаказ на месте на основе циклов. Обратите внимание, что индексы будут изменены на {0,1,2,3}. У меня нет установленной Java (пока), поэтому я преобразовал рабочий код на C++ в то, что я считаю правильным синтаксисом Java.

for (int i = 0; i < arr1.size(); i++) { 
     if(i != indices[i]) { 
      String st = arr1.get(i); 
      int t = indices[i]; 
      int k = i; 
      int j; 
      while(i != (j = indices[k])){ 
       arr1.set(k, arr1.get(j)); 
       indices[k] = k; 
       k = j; 
      } 
      arr1.set(k, st); 
      indices[k] = k; 
     } 
    } 

В данном конкретном случае {3,1,2,0}, все это делает подкачки 0 и 3. Самый длинный цикл происходит, когда индексы повернуты, например, {3 0 1 2}, в в этом случае st = arr1 [0], arr1 [0] = arr1 [3], arr [3] = arr1 [2], arr1 [2] = arr1 [1], arr1 [1] = st.

Answer 4

На нижнем уровне используйте «индексы» для нового массива.

public class Sorting { 
    public static void main(String[] args) { 
     String [] str = new String[] {"a","b","c","d"}; 

      int [] indices = {3,1,2,0}; 

      String sorted [] = new String [str.length] ; 
      int i = 0; 
      for (String string : str) { 
       sorted[indices[i]] = string; 
       i++; 
      } 

      for (String string : sorted) { 
       System.out.print(string + " "); 
      } 
    } 
} 

печатает: d б р а