Java массив сортировка: Быстрый способ получить отсортированный список индексов массива

Question

Проблемы: Consder следующих поплавков []:

d[i] =  1.7 -0.3 2.1 0.5 

То, что я хочу является массивом междунара [], что представляет собой порядок исходного массива с индексами.

s[i] =  1 3 0 2 
d[s[i]] = -0.3 0.5 1.7 2.1 

Конечно, это может быть сделано с помощью пользовательского компаратора, отсортированного набора пользовательских объектов, или просто сортировки массива, а затем искать для индексов в исходном массиве (содрогания).

То, что я на самом деле ищу, эквивалентно второму аргументу возврата Matlab's sort function.

Есть ли простой способ сделать это (< 5 LOC)? Может ли быть решение, которому не нужно выделять новый объект для каждого элемента?

---

Update:

Спасибо за ваши ответы. К сожалению, ни одно из предложенных до сих пор не похоже на простое и эффективное решение, на которое я надеялся. Поэтому я открыл тему в форуме обратной связи JDK, предложив добавить новую функцию класса-библиотеки для решения этой проблемы. Посмотрим, что Sun/Oracle думает о проблеме.

http://forums.java.net/jive/thread.jspa?threadID=62657&tstart=0

Answer 1

Я бы адаптировать алгоритм быстрой сортировки для выполнения операции обмена на нескольких массивов одновременно: массив индексов и массив значений.Например (на основе этого quicksort):

public static void quicksort(float[] main, int[] index) { 
    quicksort(main, index, 0, index.length - 1); 
} 

// quicksort a[left] to a[right] 
public static void quicksort(float[] a, int[] index, int left, int right) { 
    if (right <= left) return; 
    int i = partition(a, index, left, right); 
    quicksort(a, index, left, i-1); 
    quicksort(a, index, i+1, right); 
} 

// partition a[left] to a[right], assumes left < right 
private static int partition(float[] a, int[] index, 
int left, int right) { 
    int i = left - 1; 
    int j = right; 
    while (true) { 
     while (less(a[++i], a[right]))  // find item on left to swap 
      ;        // a[right] acts as sentinel 
     while (less(a[right], a[--j]))  // find item on right to swap 
      if (j == left) break;   // don't go out-of-bounds 
     if (i >= j) break;     // check if pointers cross 
     exch(a, index, i, j);    // swap two elements into place 
    } 
    exch(a, index, i, right);    // swap with partition element 
    return i; 
} 

// is x < y ? 
private static boolean less(float x, float y) { 
    return (x < y); 
} 

// exchange a[i] and a[j] 
private static void exch(float[] a, int[] index, int i, int j) { 
    float swap = a[i]; 
    a[i] = a[j]; 
    a[j] = swap; 
    int b = index[i]; 
    index[i] = index[j]; 
    index[j] = b; 
} 

Answer 2

Я думаю, самый простой способ сделать это, чтобы индексировать массив, как он будет создан. Вам понадобятся пары ключей, значений. Если индекс является отдельной структурой, то я не могу видеть, как вы могли бы сделать это без других объектов (интересно увидеть его, хотя)

Answer 3

Создание TreeMap значений для индексов

float[] array = new float[]{}; 
    Map<Float, Integer> map = new TreeMap<Float, Integer>(); 
    for (int i = 0; i < array.length; ++i) { 
     map.put(array[i], i); 
    } 
    Collection<Integer> indices = map.values(); 

индексы будут отсортированными по их поплавкам, исходный массив не тронут. Преобразование Collection<Integer> в int[] оставлено как упражнение, если это действительно необходимо.

EDIT: Как отмечено в комментариях, этот подход не работает, если в массиве float имеются повторяющиеся значения. Это можно решить, сделав Map<Float, Integer> в Map<Float, List<Integer>>, хотя это будет затруднять внутреннюю часть цикла for и генерации окончательной коллекции.

Answer 4

С Functional Java:

import static fj.data.Array.array; 
import static fj.pre.Ord.*; 
import fj.P2; 

array(d).toStream().zipIndex().sort(p2Ord(doubleOrd, intOrd)) 
    .map(P2.<Double, Integer>__2()).toArray(); 

Answer 5

Преобразование вход в класс пары, как показано ниже, а затем отсортировать это с помощью Arrays.sort(). Arrays.sort() гарантирует, что первоначальный порядок сохраняется для равных значений, таких как Matlab. Затем вам нужно преобразовать отсортированный результат обратно в отдельные массивы.

class SortPair implements Comparable<SortPair> 
{ 
    private int originalIndex; 
    private double value; 

    public SortPair(double value, int originalIndex) 
    { 
    this.value = value; 
    this.originalIndex = originalIndex; 
    } 

    @Override public int compareTo(SortPair o) 
    { 
    return Double.compare(value, o.getValue()); 
    } 

    public int getOriginalIndex() 
    { 
    return originalIndex; 
    } 

    public double getValue() 
    { 
    return value; 
    } 

}

Answer 6

более общий случай Jherico's answer, что позволяет повторяющиеся значения будет таким:

// Assuming you've got: float[] array; defined already 

TreeMap<Float, List<Integer>> map = new TreeMap<Float, List<Integer>>(); 
for(int i = 0; i < array.length; i++) { 
    List<Integer> ind = map.get(array[i]); 
    if(ind == null){ 
     ind = new ArrayList<Integer>(); 
     map.put(array[i], ind); 
    } 
    ind.add(i); 
} 

// Now flatten the list 
List<Integer> indices = new ArrayList<Integer>(); 
for(List<Integer> arr : map.values()) { 
    indices.addAll(arr); 
} 

Answer 7

Простое решение для создания массива индексатор: сортировать индексатор сравнивая значения данных:

final Integer[] idx = { 0, 1, 2, 3 }; 
final float[] data = { 1.7f, -0.3f, 2.1f, 0.5f }; 

Arrays.sort(idx, new Comparator<Integer>() { 
    @Override public int compare(final Integer o1, final Integer o2) { 
     return Float.compare(data[o1], data[o2]); 
    } 
}); 

Answer 8

Другое непростое решение. Вот версия сортировки слиянием, которая равна stable и не модифицирует исходный массив, хотя для слияния требуется дополнительная память.

public static int[] sortedIndices(double[] x) { 
    int[] ix = new int[x.length]; 
    int[] scratch = new int[x.length]; 
    for (int i = 0; i < ix.length; i++) { 
     ix[i] = i; 
    } 
    mergeSortIndexed(x, ix, scratch, 0, x.length - 1); 
    return ix; 
} 

private static void mergeSortIndexed(double[] x, int[] ix, int[] scratch, int lo, int hi) { 
    if (lo == hi) 
     return; 
    int mid = (lo + hi + 1)/2; 
    mergeSortIndexed(x, ix, scratch, lo, mid - 1); 
    mergeSortIndexed(x, ix, scratch, mid, hi); 
    mergeIndexed(x, ix, scratch, lo, mid - 1, mid, hi); 
} 

private static void mergeIndexed(double[] x, int[] ix, int[] scratch, int lo1, int hi1, int lo2, int hi2) { 
    int i = 0; 
    int i1 = lo1; 
    int i2 = lo2; 
    int n1 = hi1 - lo1 + 1; 
    while (i1 <= hi1 && i2 <= hi2) { 
     if (x[ix[i1]] <= x[ix[i2]]) 
      scratch[i++] = ix[i1++]; 
     else 
      scratch[i++] = ix[i2++]; 
    } 
    while (i1 <= hi1) 
     scratch[i++] = ix[i1++]; 
    while (i2 <= hi2) 
     scratch[i++] = ix[i2++]; 
    for (int j = lo1; j <= hi1; j++) 
     ix[j] = scratch[j - lo1]; 
    for (int j = lo2; j <= hi2; j++) 
     ix[j] = scratch[(j - lo2 + n1)]; 
} 

Answer 9

Лучшим решением было бы по линии QSort C, которая позволяет задать функции для сравнения и обмена, поэтому QSort не должны быть осведомлены о типе или организации данных, отсортированных. Вот то, что вы можете попробовать. Поскольку Java не имеет функций, используйте внутренний класс Array для переноса массива или коллекции для сортировки. Затем оберните это в IndexArray и выполните сортировку. Результат getIndex() в IndexArray будет массивом индексов, как описано в JavaDoc.

public class QuickSortArray { 

public interface Array { 
    int cmp(int aindex, int bindex); 
    void swap(int aindex, int bindex); 
    int length(); 
} 

public static void quicksort(Array a) { 
    quicksort(a, 0, a.length() - 1); 
} 

public static void quicksort(Array a, int left, int right) { 
    if (right <= left) return; 
    int i = partition(a, left, right); 
    quicksort(a, left, i-1); 
    quicksort(a, i+1, right); 
} 

public static boolean isSorted(Array a) { 
    for (int i = 1, n = a.length(); i < n; i++) { 
     if (a.cmp(i-1, i) > 0) 
      return false; 
    } 
    return true; 
} 

private static int mid(Array a, int left, int right) { 
    // "sort" three elements and take the middle one 
    int i = left; 
    int j = (left + right)/2; 
    int k = right; 
    // order the first two 
    int cmp = a.cmp(i, j); 
    if (cmp > 0) { 
     int tmp = j; 
     j = i; 
     i = tmp; 
    } 
    // bubble the third down 
    cmp = a.cmp(j, k); 
    if (cmp > 0) { 
     cmp = a.cmp(i, k); 
     if (cmp > 0) 
      return i; 
     return k; 
    } 
    return j; 
} 

private static int partition(Array a, int left, int right) { 
    int mid = mid(a, left, right); 
    a.swap(right, mid); 
    int i = left - 1; 
    int j = right; 

    while (true) { 
     while (a.cmp(++i, right) < 0) 
      ; 
     while (a.cmp(right, --j) < 0) 
      if (j == left) break; 
     if (i >= j) break; 
     a.swap(i, j); 
    } 
    a.swap(i, right); 
    return i; 
} 

public static class IndexArray implements Array { 
    int[] index; 
    Array a; 

    public IndexArray(Array a) { 
     this.a = a; 
     index = new int[a.length()]; 
     for (int i = 0; i < a.length(); i++) 
      index[i] = i; 
    } 

    /** 
    * Return the index after the IndexArray is sorted. 
    * The nested Array is unsorted. Assume the name of 
    * its underlying array is a. The returned index array 
    * is such that a[index[i-1]] <= a[index[i]] for all i 
    * in 1..a.length-1. 
    */ 
    public int[] index() { 
     int i = 0; 
     int j = index.length - 1; 
     while (i < j) { 
      int tmp = index[i]; 
      index[i++] = index[j]; 
      index[j--] = tmp; 
     } 
     int[] tmp = index; 
     index = null; 
     return tmp; 
    } 

    @Override 
    public int cmp(int aindex, int bindex) { 
     return a.cmp(index[aindex], index[bindex]); 
    } 

    @Override 
    public void swap(int aindex, int bindex) { 
     int tmp = index[aindex]; 
     index[aindex] = index[bindex]; 
     index[bindex] = tmp; 
    } 

    @Override 
    public int length() { 
     return a.length(); 
    } 

} 

Answer 10

//Here index array(of length equal to length of d array) contains the numbers from 0 to length of d array 
     public static Integer [] SortWithIndex(float[] data, Integer [] index) 
    { 
    int len = data.length; 
    float temp1[] = new float[len]; 
    int temp2[] = new int[len]; 



     for (int i = 0; i <len; i++) { 


       for (int j = i + 1; j < len; j++) { 


        if(data[i]>data[j]) 
        { 
        temp1[i] = data[i]; 
        data[i] = data[j]; 
        data[j] = temp1[i]; 



        temp2[i] = index[i]; 
        index[i] = index[j]; 
        index[j] = temp2[i]; 

        } 
        } 

     } 

     return index; 

    } 

Answer 11

public static int[] indexSort(final double[] v, boolean keepUnsorted) { 
    final Integer[] II = new Integer[v.length]; 
    for (int i = 0; i < v.length; i++) II[i] = i; 
    Arrays.sort(II, new Comparator<Integer>() { 
     @Override 
     public int compare(Integer o1, Integer o2) { 
      return Double.compare(v[o1],v[o2]); 
     } 
    }); 
    int[] ii = new int[v.length]; 
    for (int i = 0; i < v.length; i++) ii[i] = II[i]; 
    if (!keepUnsorted) { 
     double[] clon = v.clone(); 
     for (int i = 0; i < v.length; i++) v[i] = clon[II[i]]; 
    } 
    return ii; 
} 

Answer 12

Я хотел бы сделать что-то вроде этого:

public class SortedArray<T extends Comparable<T>> { 
    private final T[] tArray; 
    private final ArrayList<Entry> entries; 

    public class Entry implements Comparable<Entry> { 
     public int index; 

     public Entry(int index) { 
      super(); 
      this.index = index; 
     } 

     @Override 
     public int compareTo(Entry o) { 
      return tArray[index].compareTo(tArray[o.index]); 
     } 
    } 

    public SortedArray(T[] array) { 
     tArray = array; 
     entries = new ArrayList<Entry>(array.length); 
     for (int i = 0; i < array.length; i++) { 
      entries.add(new Entry(i)); 
     } 
     Collections.sort(entries); 
    } 

    public T getSorted(int i) { 
     return tArray[entries.get(i).index]; 

    } 

    public T get(int i) { 
     return tArray[i]; 
    } 
} 

Answer 13

Ниже приведен метод, основанный на вставки Сортировка

public static int[] insertionSort(float[] arr){ 
    int[] indices = new int[arr.length]; 
     indices[0] = 0; 
     for(int i=1;i<arr.length;i++){ 
      int j=i; 
      for(;j>=1 && arr[j]<arr[j-1];j--){ 
        float temp = arr[j]; 
        arr[j] = arr[j-1]; 
        indices[j]=indices[j-1]; 
        arr[j-1] = temp; 
      } 
      indices[j]=i; 
     } 
     return indices;//indices of sorted elements 
} 

Answer 14

Использование Java 8 функций (без дополнительной библиотеки), лаконичный способ ее достижения.

int[] a = {1,6,2,7,8} 
int[] sortedIndices = IntStream.range(0, a.length) 
       .boxed().sorted((i, j) -> a[i] - a[j]) 
       .mapToInt(ele -> ele).toArray(); 

Answer 15

Я бы хотел использовать это, потому что это очень быстро. Но я использую его для int, вы можете изменить его на float.

private static void mergeSort(int[]array,int[] indexes,int start,int end){ 
    if(start>=end)return; 
    int middle = (end-start)/2+start; 
    mergeSort(array,indexes,start,middle); 
    mergeSort(array,indexes,middle+1,end); 
    merge(array,indexes,start,middle,end); 
} 
private static void merge(int[]array,int[] indexes,int start,int middle,int end){ 
    int len1 = middle-start+1; 
    int len2 = end - middle; 
    int leftArray[] = new int[len1]; 
    int leftIndex[] = new int[len1]; 
    int rightArray[] = new int[len2]; 
    int rightIndex[] = new int[len2]; 
    for(int i=0;i<len1;++i)leftArray[i] = array[i+start]; 
    for(int i=0;i<len1;++i)leftIndex[i] = indexes[i+start]; 
    for(int i=0;i<len2;++i)rightArray[i] = array[i+middle+1]; 
    for(int i=0;i<len2;++i)rightIndex[i] = indexes[i+middle+1]; 
    //merge 
    int i=0,j=0,k=start; 
    while(i<len1&&j<len2){ 
     if(leftArray[i]<rightArray[j]){ 
      array[k] = leftArray[i]; 
      indexes[k] = leftIndex[i]; 
      ++i; 
     } 
     else{ 
      array[k] = rightArray[j]; 
      indexes[k] = rightIndex[j]; 
      ++j; 
     } 
     ++k; 
    } 
    while(i<len1){ 
     array[k] = leftArray[i]; 
     indexes[k] = leftIndex[i]; 
     ++i;++k; 
    } 
    while(j<len2){ 
     array[k] = rightArray[j]; 
     indexes[k] = rightIndex[j]; 
     ++j;++k; 
    } 
}