以特定方式递归/排序数组 [英] Recursive/Sorting an Array a specific way

问题描述

要递归地对数组进行排序，请找到数组中最大的元素，然后将其与最后一个元素交换。然后对数组进行从头到尾的递归排序。编写并测试以这种方式对数组进行递归排序的方法。启动它，我认为我的代码已完成垃圾回收。递归对我来说没有多大意义，仅需要帮助解决此问题。我已经找到了如何在数组中定位最高int的方法，只是麻烦找出递归来对它进行排序。

 公共类排序
 {
 public static void main（String [] args）
 {
 int [] array = {5,1,8,3,4,7}; 
 int length = array.length; 
 int max = -99999; 
 int [] revArray = sortArray（array，length-1，max，length）; 
 
 for（int i：revArray）
 System.out.print（i +）; 
 
} 
 
 public static int [] sortArray（int [] a，int j，int max，int length）
 {
 
 if（j< = 0）
 {
返回a; 
 
} 
 
 if（max< a [j]）
 {
 max = a [j]; 
返回sortArray（a，j-1，max，length）; 
 
} 
 
返回a； 
} 
} 
  

解决方案

您在某种程度上是正确的，但是您的代码确实有点像在黑暗中进行一些拍摄。有时，将问题分解为子问题，并逐个处理每个问题，可以使整个事情变得不那么令人沮丧……

数组中最大元素的索引

首先，您需要能够找出未排序数组中最大元素的索引（或在此数组中情况，在子数组中）。由于数组未排序，因此您必须遍历其所有元素以找到最大值。因此，首先，您可以编写一个辅助方法，该方法将数组作为输入，并返回最大元素的索引。为此，您需要同时跟踪最大元素的值及其索引。用伪代码：

  function indexOfLargestElement（array）
 index = -1 
 max = -infinity i = 0的
到array.length如果array [i]> max然后
索引= i 
 max =数组[i] 
结束
结束
返回索引
结束
  

现在，这仅解决了在完整数组中查找最大元素的问题。修改方法以获取结束索引，以便您可以精确指定要查找的数组的深度。这样一来，您就可以找到从第一个元素开始的任何范围内的最大元素。

交换元素

Java没有某些其他语言所具有的交换功能，因此当您将一个索引的值写入其中时，您将需要一个临时变量来保存一个索引的值。然后，您可以将临时变量的值写入另一个索引，这两个元素将被有效地交换。您也可以编写辅助方法来执行此操作-它以数组作为输入，并交换两个索引。

将其放在一起

现在，您已经有了编写递归排序方法的工具。但是，在执行此操作之前，请考虑一下此算法为何起作用。如果在数组中找到最大的元素并将其与数组的最后一个元素交换，则意味着可以将排序问题减少一个元素。现在，您只需要在子数组中找到最大的元素，该元素从数组的第一个元素开始，到倒数第二个元素结束。然后，将该元素替换为倒数第二个元素，到现在，您已将排序问题减少了两个元素。现在，您只需要在子数组中找到最大的元素，该元素从数组的第一个元素开始，到倒数第二个元素结束。然后您就交换...

这基本上就是递归。简单的递归函数具有一个基本情况（例如，大小为1的数组）和一个归纳情况（大小为n的数组）。这个想法是部分解决归纳案例，因此您可以将其简化为另一个较小的归纳案例，并继续这样做，直到达到基本案例，这通常是微不足道的（大小为1的数组已被排序）。 / p>

To recursively sort an array, fi nd the largest element in the array and swap it with the last element. Then recursively sort the array from the start to the next-to-the-last element. Write and test a method that recursively sorts an array in this manner. Started it and I think my code complete trash. Recursion do not make much sense to me and just needing help with this problem. Ive found how to locate the highest int in the array just havihng trouble finding out the recursion to sort it now.

public class Sorting
{
    public static void main(String[] args) 
    {
        int[] array={5,1,8,3,4,7};
        int length = array.length;
        int max = -99999;
        int[] revArray= sortArray(array,length-1,max,length);  

        for(int i:revArray)
            System.out.print(i+" ");

    }

    public static int[] sortArray(int[] a,int j,int max,int length)
    {        

        if( j <= 0)   
        {    
            return a;  

        }

        if(max < a[j])
        {
            max = a[j];            
            return sortArray(a, j-1, max,length); 

        }  

         return a;
    }
}

解决方案

You're sort of on the right track, but your code does look a bit like you're shooting in the dark with regards to a few things. Sometimes, breaking the problem down into subproblems and tackling each one in isolation makes the whole thing less overwhelming...

Finding the index of the largest element in an array

First of all, you need to be able to figure out the largest element in an unsorted array (or in this case, in a subarray). Since the array is unsorted, you have to loop through all of its elements to find the maximum. So to start off, you can write an auxiliary method that takes as input an array, and returns the index of the largest element. To do this, you need to keep track of both the value of the largest element as well as its index. In pseudo-code:

function indexOfLargestElement(array)
    index = -1
    max = -infinity
    for i = 0 to array.length do
        if array[i] > max then
            index = i
            max = array[i]
        end
    end
    return index
end

Now, this only solves the problem of finding the largest element in a full array. Modify the method to take an end index, so you can specify exactly how far into the array you want to look. This allows you to find the largest element in any range starting from the first element.

Swapping elements

Java doesn't have a swap function like some other languages do, so you will need a temporary variable to hold the value of one index while you write the value of the other index to it. Then you can write the value of the temporary variable to the other index, and the two elements will effectively be swapped. You could also write an auxiliary method to do this - it takes as input an array, and the two indices to swap.

Putting it together

Now you have the tools to write your recursive sorting method. Before you do, though, think about why this algorithm works. If you find the largest element in the array and swap it with the last element of the array, it means that you can reduce your sorting problem by one element. Now you just have to find the largest element in the subarray that starts at the first element of the array and ends at the second-to-last element. Then you swap that element with the second-to-last element, and by now, you have reduced your sorting problem by two elements. Now you just have to find the largest element in the subarray that starts at the first element of the array and ends at the third-to-last element. Then you swa...

And that's basically what recursion is. Simple recursive functions have a base case (e.g. an array of size 1), and an induction case (an array of size n). The idea is to partially solve the induction case, so you can reduce it to another induction case that's smaller, and continue to do so until you reach the base case, which is often trivial (an array of size 1 is already sorted).

这篇关于以特定方式递归/排序数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！