使用合併對數組進行排序索引排序

我試圖使用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

使用合併對數組進行排序索引排序

回答

相關問題