如何有效排序一个数组另一

假设我有以下设置：如何有效排序一个数组另一

double[] vectorUsedForSorting = new double[] { 5.8,6.2,1.5,5.4 } 
double[] vectorToBeSorted = new double[] {1.1,1.2,1.3,1.4}

我想基础上的vectorUsedForSorting自然的数字顺序进行排序vectorToBeSorted。

例如，自然排序为[1.5,5.4,5.8,6.2]，其对应于索引[2,3,0,1]，这意味着我希望排序函数的输出为[1.3,1.4,1.1,1.2]。

我该如何以最绝对有效/快速的方式做到这一点？我主要关心时间复杂性，因为我将为1,000,000个长度的数组做这件事。

一个快速/有效的答案将奖励一笔大额奖金。

来源

2014-02-07 user2763361

A）写入排序B）传递两个数组C）同时只根据第一个值进行排序。 –

你是否改变了主意w.r.t. [上一个问题]（http://stackoverflow.com/questions/21608646/fastest-way-to-sort-an-array-by-a-separate-array-of-indices-indexes）？现在你真的需要排序吗？ – maaartinus

简单的解决方案：

class D implements Comparable<D> { 
    double key; 
    double value; 

    @Override 
    public int compareTo(D other) { 
     return Double.compare(key, other.key); 
    } 
} 

public class Test { 
    public static void main(String[] args) { 
     double[] vectorUsedForSorting = new double[] { 5.8,6.2,1.5,5.4 }; 
     double[] vectorToBeSorted = new double[] {1.1,1.2,1.3,1.4}; 

     D[] array = new D[vectorUsedForSorting.length]; 
     for (int i = 0; i < array.length; i++) { 
      array[i] = new D(); 
      array[i].key = vectorUsedForSorting[i]; 
      array[i].value = vectorToBeSorted[i]; 
     } 

     Arrays.sort(array); 

     for (int i = 0; i < array.length; i++) { 
      vectorToBeSorted[i] = array[i].value; 
     } 

     System.out.println(Arrays.toString(vectorToBeSorted)); 

    } 
}

这并不需要辅助数组和对象一点点额外的内存，但应该接近最优的执行时间。

来源

2014-02-07 21:59:41 meriton

由于Arrays.sort（）是O（nlogn），所以此算法为O（nlogn）。这可能是一样好。 – Rainbolt

这给了100万个数据点560毫秒。够好了。 – user2763361

在第一个表上执行合并排序，并在第二个表上同时执行相同的操作。复杂nlogn保证

来源

2014-02-07 21:52:26 janek

嗯，我不确定，你能写一个方法吗？我会奖励奖金。 – user2763361

你知道合并排序算法吗？ http://en.wikipedia.org/wiki/Merge_sort – janek

是的，没关系。我会写点东西，如果它比实际速度快，我会意识到你的答案。干杯。 – user2763361

如何有效排序一个数组另一

回答

相关问题