使用合并排序对数组索引进行排序

Question

我正在尝试使用合并排序对数组的索引进行排序。 mergesort 完美运行，最终答案完全正确，但我不确定为什么索引不能在正确的位置运行。我不想对数组进行排序，我只想对作为索引列表的 perm[] 数组进行排序。

为避免混淆，举个例子： perm 数组保存原始数组 nums[] 的初始索引（即 0 到 nums.length - 1）

我想根据 nums[] 数组中的数据移动 perm 数组中的索引，以便索引代表排序顺序。

For example :
Array -> (-1,9,-5,3,0)
Initial perm -> (0,1,2,3,4)
After sorting perm based on array - > (2,0,4,3,1)

这是我的代码：

import java.util.Arrays;

public class IndexSort {

    public boolean leq(Comparable u, Comparable v) {
        return u.compareTo(v) <= 0;
    }

    public void merge(Comparable a[], int temp[], int perm[], int lo, int mid, int hi) {
        int i = lo, j = mid + 1;

        for (int k = lo; k <= hi; k++) {
            temp[k] = perm[k];
        }

        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                perm[k] = temp[j++];
            } else if (j > hi) {
                perm[k] = temp[i++];
            } else if (leq(a[perm[i]], a[perm[j]])) {
                perm[k] = temp[i++];
            } else {
                perm[k] = temp[j++];
            }
        }
    }

    public void mergeSort(Comparable a[], int temp[], int perm[], int lo, int hi) {
        if (hi <= lo)
            return;
        int mid = (hi + lo) / 2;
        mergeSort(a, temp, perm, lo, mid);
        mergeSort(a, temp, perm, mid + 1, hi);
        merge(a, temp, perm, lo, mid, hi);
        System.out.println(" lo  = " + lo + "  mid  = " + mid + "  hi  = " + hi);
        System.out.println(Arrays.toString(perm));
    }

    public void indexSort(Comparable nums[], int perm[]) {
        int temp[] = new int[nums.length];
        Comparable temp2[] = new Comparable[nums.length];
        mergeSort(nums, temp, perm, 0, nums.length - 1);
    }

    public static void main(String[] args) {
        IndexSort o1 = new IndexSort();
        Comparable nums[] = { 12, -12, 0, 123, -123, 1, 2, 3, 4, -4, -4, -3, -2, 1 };
        int perm[] = new int[nums.length];
        for (int i = 0; i < perm.length; i++) {
            perm[i] = i;
        }
        System.out.println(Arrays.toString(nums));
        System.out.println(Arrays.toString(perm));
        o1.indexSort(nums, perm);
        System.out.println(Arrays.toString(perm));
    }
}

Answer 1

我认为这一行需要从 perm 更改为 temp:

} else if (leq(a[temp[i]], a[temp[j]])) {

使用合并排序对数组索引进行排序

Sorting index of array using merge Sort

java

mergesort

divide-and-conquer