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

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

为了避免混乱，下面有一个例子：烫发数组保持原始数组NUMS []的初始索引（即，0至nums.length - 1）

我要移动的索引烫发阵列中基于nums []数组中的数据，以便索引表示排序顺序。

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)); 
    } 
}

来源

2015-10-04 chettyharish

“数组排序的索引” ???虽然不是很清楚，但在第二次阅读它时，似乎您想要对保存另一个数组索引的数组进行排序。这是无关紧要的，你想对数组的内容进行排序，并且存在所有这些。请尽量不要混淆想要帮助你的人... :) – alfasin

你可以在**到你的问题**输出并指出哪里与你的期望有什么不同。 – hotzst

对不起，如果有任何困惑，我现在增加了一个例子来说明我想要做什么。 – chettyharish

我觉得这行需要改变从perm到temp：

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

来源

2015-10-04 20:52:37 Andreas

哇，这是一个愚蠢的错误，非常感谢:) – chettyharish

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

回答

相关问题