創建未排序數組索引的最快方法

Question

我正在處理一個存在未排序數組的問題。我需要處理這個數組以便生成一個索引數組，就好像它是按升序排序的。

實施例1：

讓我們說我有一個未排序的陣列[9,7，8,6，12]

而作爲一個輸出，我需要索引陣列[3，1,2，... 0，4]。

實施例2：

未排序數組：[10，9，11，8，12] 索引陣列應該是：[2，1，3,0，4]

截至目前，我這樣做就像老式的「泡沫排序」，我在比較每一種可能性。我想知道如何讓它變得更快。

Answer 1

如果您不擔心額外的空間，這樣做：

1. 做對的數組按升序值（第一部件）(value, index)
2. 排序對
3. 收穫指數（第二從對

使用您的數據爲例的有序數組成員），你會得到這樣的：

[{9,0}, {7,1}, {8,2}, {6,3}, {12,4}] // Step 1 
[{6,3}, {7,1}, {8,2}, {9,0}, {12,4}] // Step 2 
[ 3,  1,  2,  0,  4 ] // Step 3 

（評論）我需要的是一個未排序數組的索引，就好像它們按升序排序。

您也可以使用步驟3中的數組生成此輸出。使用你的第二個例子，你會得到這樣的：

[{10,0}, {9,1}, {11,2}, {8,3}, {12,4}] 
[ {8,3}, {9,1}, {10,0}, {11,2}, {12,4}] 
[ 3,  1,  0,  2,  4 ] 

現在創建輸出數組，走索引的陣列（即[3,1,0,2,4]）和每個項目的指標設置成價值，即確定在結果的位置索引3將得到0，因爲3在索引0處，索引1將得到1，因爲1在1處，索引0將得到2，因爲0在2處，依此類推。

下面是另外的步驟的圖示：

int position[] = {3, 1, 0, 2, 4}; 
int res[5]; 
for (int i = 0 ; i != 5 ; i++) { 
    res[position[i]] = i; 
} 

這將產生以下的數組：

[2, 1, 3, 0, 4] 

Answer 2

「快速」意味着您需要一個複雜度爲O（log n）的插入（當然還有查找）的排序數據結構。所以二叉樹就可以做到。

Answer 3

創建索引作爲位置的數組，並將其初始化到現有的順序：idx = [0,1,2，...，n-1]。
然後，使用您喜歡的排序算法對索引數組進行排序，但是每次執行比較時，都會使用這些值作爲位置來引用原始數組，而不是直接比較它們。例如，要比較項目i和j，執行cmp（arr [idx [i]]，arr [idx [j]]）而不是cmp（idx [i]，idx [j]）。

Answer 4

你嘗試基數排序：

* Approach: 
* radix sort, like counting sort and bucket sort, is an integer based 
* algorithm (i.e. the values of the input array are assumed to be 
* integers). Hence radix sort is among the fastest sorting algorithms 
* around, in theory. The particular distinction for radix sort is that it 
* creates a bucket for each cipher (i.e. digit); as such, similar to 
* bucket sort, each bucket in radix sort must be a growable list that may 
* admit different keys. 

***************************************************************************/ 
import java.io.IOException; 


public class RadixSort { 

    public static void sort(int[] a) 
    { 
     int i, m = a[0], exp = 1, n = a.length; 
     int[] b = new int[10]; 
     for (i = 1; i < n; i++) 
      if (a[i] > m) 
       m = a[i]; 
     while (m/exp > 0) 
     { 
      int[] bucket = new int[10]; 

      for (i = 0; i < n; i++) 
       bucket[(a[i]/exp) % 10]++; 
      for (i = 1; i < 10; i++) 
       bucket[i] += bucket[i - 1]; 
      for (i = n - 1; i >= 0; i--) 
       b[--bucket[(a[i]/exp) % 10]] = a[i]; 
      for (i = 0; i < n; i++) 
       a[i] = b[i]; 
      exp *= 10;   
     } 
    } 

    public static void main(String[] args) throws IOException { 

     int[] aa={9,7,8,6,12}; 
     for (int i = 0; i < aa.length; i++) { 
      System.out.print(aa[i]+" "); 
     } 
     System.out.println(); 
     sort(aa); 
     for (int i = 0; i < aa.length; i++) { 
      System.out.print(aa[i]+" "); 
     } 
    } 


}