如何有效排序一個數組另一

假設我有以下設置：如何有效排序一個數組另一

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

如何有效排序一個數組另一

回答

相關問題