需要帮助了解数组排序的递归

我的任务是编写一个称为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

需要帮助了解数组排序的递归

回答

相关问题