需要幫助瞭解數組排序的遞歸

我的任務是編寫一個稱爲quadSort的遞歸方法，將數組拆分爲4個部分，按照quadSort排序，然後前兩個（A和B）合併成一個數組（X），第二個（C和D）合併成一個（Y），那麼這兩個合併爲一個。 quadSort應該調用quadSort（）4次（每個部分一次）。我的問題是我已完成基本案例，但我無法弄清楚如何編寫該方法的遞歸部分。任何人都可以幫助我理解如何去做這個或者給我一個例子嗎？提前致謝。需要幫助瞭解數組排序的遞歸

編輯：這是我嘗試

public static void quadSort(int array[], int index, int length){ 

    for (int i = 1; i<array.length; i++){ 
     if(array[i] <= 1000){ 
      for(i = 1; i<array.length;i++){   //Start point for the insertion sort 
       int key = array[i]; 
       int j = i-1; 
       while((i>-1) && (array[j] > key)){ 
        array [j+1] = array[j]; 
        i--; 
       } 
       array[j+1] = key; 
      }          //End insertion sort 
     } 
     else{ 
      int split = (array[i])/4; 

     } 
    } 
    return; 
}

來源

2014-09-24 ninjachris16

請發表您現有的嘗試。 – 2014-09-24 14:03:17

你自己說過，你需要首先將數組拆分爲4. – njzk2 2014-09-24 14:26:07

這聽起來與MergeSort類似 - 維基百科關於合併排序的文章有一個遞歸實現的合併排序的例子（在C中，不是java）。 – Sbodd 2014-09-24 15:12:39

這是一個古怪修改歸併，在那裏，而不是遞歸一路，直到你得到1-長度子陣列，然後纔開始合併，你遞歸直到子數組的長度是原始數組長度的1/4爲止，按照你喜歡的任何排序算法排序（quicksort？），然後將其合併備份。目前還不清楚，如果陣列沒有至少4個元素，那麼預期會是什麼。在這種情況下，您可以根據需要調整它。

使用僞代碼將是這樣的：

quadSort(array, l, r): 
    m = array.length/2 - 1 
    //First checking if it is the base case 
    // i.e. l and r define one quarter of the array 
    if((l == 0 AND r < m) OR //First quarter 
     (l > 0 AND r == m) OR //Second quarter 
     (l == m+1 AND r < array.length - 1) OR //Third quarter 
     (l > m+1 AND r == array.length - 1)) //Fourth quarter 
     quicksort(array, l, r) //Base case 
    else 
     //Not the base case, hence we proceed to further split the array 
     //and recurse on quadsort, before proceeding to merge 
     m = (r+l)/2 
     quadsort(array, l, m) 
     quadsort(array, m+1, r) 
     merge(array, l, m , r) 

merge(array, l, m, r): 
    //Standard merge procedure from mergesort

來源

2014-09-24 14:35:06 micantox

對不起，我沒有指定，數組將有40,000個元素。這就是爲什麼該計劃將有4個主要分裂。 – ninjachris16 2014-09-24 21:29:41

需要幫助瞭解數組排序的遞歸

回答

相關問題