我遵循一個好的方法嗎？

我跟着採取隨機排列這下面的方法。希望你的建議可以遵循什麼其他方法來解決問題： -

public class ThreeMachineInsertionSorting { 
    public static void main(String[] args) { 
     int[] ar1 = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,-10}; 
     int[] ar2 = { 20, 19, 18, 17, 16, 15, 14, 23, 12, 11, 10 }; 
     int[] ar3 = { 20, 19, 21, 122, 10, 9, 11, 12, 4, 13, 18, 17 }; 

     performInsertionSort(ar1, ar2, ar3); 
    } 

    private static void performInsertionSort(int[] ar1, int[] ar2, int[] ar3) { 
     int[][] arrayOfArrays = { ar1, ar2, ar3 }; 

     int [] unSortedArray= mergeArrays(ar1,ar2,ar3,arrayOfArrays); 

     int i,j,key; 
     for(i=1;i<unSortedArray.length;i++){ 
      key= unSortedArray[i]; 
      j=i-1; 
      while(j>=0 && key<unSortedArray[j]){ 
       unSortedArray[j+1] = unSortedArray[j]; 
       j--; 
      } 
      unSortedArray[j+1] = key; 
     } 

     System.out.println("Size of the unSorted array is :=" + unSortedArray.length); 


     shareLoad(unSortedArray, arrayOfArrays); 


    } 

    private static void shareLoad(int[] sortedArray, int[][] arrayOfArrays) { 
     int loadFactor = sortedArray.length/3; 
     int index=0; 

     while(index<sortedArray.length){ 
      for(int [] ar : arrayOfArrays){ 
       for(int i=0; i<ar.length;i++){ 
        if(i<=loadFactor){ 
         ar[i] = sortedArray[index]; 
         index++; 
        } 
       } 
      } 
     } 

     for(int [] ar : arrayOfArrays){ 
      System.out.println("******************************************array properties**************************************"); 
      System.out.println("Size of array::" + ar.length); 
      for(int i=0; i<ar.length;i++){ 
       System.out.print(ar[i]+" "); 
      } 
      System.out.println("\n******************************************************************"); 
     } 


    } 

    private static int[] mergeArrays(int[] ar1, int[] ar2, int[] ar3,int[][] arrayOfArrays) { 

     int[] colaboratedArray = new int[ar1.length + ar2.length + ar3.length]; 
     System.out.println("Length of multi-dimensional array :-" 
       + arrayOfArrays.length); 

     int i = 0; 

     while (i < colaboratedArray.length) { 
      for (int[] ar : arrayOfArrays) { 
       for (int j = 0; j < ar.length; j++) { 
        colaboratedArray[i++] = ar[j]; 
       } 
      } 

     } 

     return colaboratedArray; 
    } 
}

來源

2015-02-24 Ankit

這裏有點幼稚的解決方案。

使用就地排序算法對M1，M2和M3進行排序。

通過找出M1中所有元素都可以換出M3中較小元素的點來組合M1和M3。

爲了找到這個點，在M3中取1/9的數字並移到M1中的緩衝區。請注意，1/9的數字恰好是可用的10％容量。我們從M3中最小的桶開始，並將其與M1中最大的桶進行比較。通過比較M3桶的最大值和M1桶的最小值，我們可以確定是否可以將它們完全換出。如果我們可以將水桶從M1移到M3並從M3中抽入新水桶。這樣做，直到我們有M1和M3分區。

現在我們必須再次分類M1和M3。現在我們必須從M2中取出最小的元素，並將它們移動到M1，直到我們劃分出M1和M2。完成之後，我們可以對M1和M2進行排序。請注意，M1現已完成。

通過對M2和M3進行分區然後對兩者進行排序並解決問題。

請注意，該解決方案要求我們對所有機器進行三次分類，並且每個數據元素在最壞情況下在機器之間移動了3次。

如果我們能夠找到兩個未排序集合的中位數，那麼我們可以根據這個中位數然後轉移元素來劃分這些集合，並且只有在我們知道最終數字已經打開每臺機器。

如果我們能夠在不傳輸數據的情況下高效地找到3個未分類集的第K個最大元素，可以進一步改進。

來源

2015-02-24 13:09:58

我遵循一個好的方法嗎？

回答

相關問題