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

Ответ 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;
}

Ответ 2

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

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]);
    }
});

Ответ 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 и генерации окончательной коллекции.

Ответ 4

Использование возможностей 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();

Ответ 5

С Функциональная 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();

Ответ 6

Более общий случай Jherico 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);
}

Ответ 7

Лучшее решение будет соответствовать строкам C qsort, которое позволяет вам указывать функции для сравнения и свопинга, поэтому 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();
    }

}

Ответ 8

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;
}

Ответ 9

Преобразуйте вход в класс пары, как показано ниже, а затем выполните сортировку с помощью массива 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;
  }

}

Ответ 10

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

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)];
}

Ответ 11

//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;

    }

Ответ 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];
    }
}

Ответ 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
 }

Ответ 14

Я бы хотел использовать это, потому что это очень быстро. Но я использую его для 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;
    }
}

Ответ 15

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