java - 通过单独的索引/索引数组对数组进行排序的最快方法

Question

假设我有以下设置:

int[] vectorUsedForSorting = new int[] { 1,0,2,6,3,4,5 }
int[] vectorToBeSorted = new int[] {1,2,3,4,5,6,7}

使用 vectorUsedForSorting 对 vectorToBeSorted 进行排序的最有效/快速的方法是什么？例如，我希望 vectorToBeSorted[0] 变为 vectorToBeSorted[1]，因为 vectorUsedForSorting 的第一个元素是 1 (即 vectorToBeSorted[0] 应变为 `vectorToBeSorted[vectorUsedForSorting[0]] 等)。

排序算法完成后，我的目标是 vectorToBeSorted 为 [2,1,3,5,6,7,4]。

我希望很快就能取得一些成就。请注意，计算复杂性应该是主要关注点，因为我将对大小为 1,000,000 及以上的数组进行排序。

如果可能的话，我的目标是亚线性时间复杂度。

Answer 1

有两种方法可以解决这个问题。第一个是复制快速排序算法，并使用可以处理您所拥有的间接寻址的内容更改访问和交换值部分:

int valueAt(int index) { return vectorUsedForSorting[index]; }
int swap(int i1, int i2) {
    int tmp = vectorUsedForSorting[i1];
    vectorUsedForSorting[i1] = vectorUsedForSorting[i2];
    vectorUsedForSorting[i2] = tmp;

    tmp = vectorToBeSorted[i1];
    vectorToBeSorted[i1] = vectorToBeSorted[i2];
    vectorToBeSorted[i2] = tmp;
}

第二种方法是将值复制到新对象中:

public class Item {
    int index;
    int value;
}

创建一个数组，并用 Item 填充它。使用两个数组中的值创建。然后您可以创建一个 Comparator<Item>将它们进行比较 index .

当你有了这个，你可以用 Arrays.sort(items, comparator) 对数组进行排序.

如果这还不够快，那么您可以创建 N 个线程，并让每个线程对原始数组的 1/N 进行排序。完成后，您可以使用 merge sort 中的合并步骤。加入结果。