如何使用递归创建排序方法? [英] How do I make a sort method using recursion?

问题描述

我正在学习递归，我被指示制作一个对数组进行排序的递归方法.到目前为止，我有这个:

I'm learning recursion and I was instructed to make a recursive method that sorts an array. So far I have this:

public static void sort(int [] a, int i) {
    if(i == a.length - 1){
        System.out.println(a[i]);
    }
    if(i < a.length) {
        if(a[i] > a[i+1]) {
            int temp = a[i+1];
            a[i+1] = a[i];
            a[i] = temp;
            sort(a,i++);
        }
        printArray(a); 
    }
}

现在我知道这是错误的，因为我仍然不太明白如何在我的编程中使用递归.如果有人可以帮助我使用该方法，我将不胜感激，但是关于如何在我的编程中使用递归的解释会很棒.提前致谢.

Now I know this is wrong because I still really don't quite understand how to use recursion in my programming. If someone could just help me with the method I would appreciate it, but and explanation on how to use recursion in my programming would be great. Thank you in advance.

推荐答案

要编写递归算法，您需要按照以下思路思考:如何通过解决同一问题的一个或多个较小实例来解决问题?对于对 N 个整数的数组进行排序"这样的问题，较小的问题可能是 N-1 个整数的数组，也可能是两个 N/2 个整数的数组(大致)，或其他可能性.

To write a recursive algorithm, you need to think along these lines: How can I solve the problem by solving one or more smaller instances of the same problem? For a problem like "sort an array of N integers", the smaller problem could be an array of N-1 integers, or it could be two arrays of N/2 integers (roughly), or other possibilities.

因为您没有给出任何其他提示，所以最简单的事情是:好的，我有一个由 N 个整数组成的数组.假设我对最后 N-1 个整数进行了排序，以便我的数组看起来像

Since you weren't give any other hints, the simplest thing would be: OK, I have an array of N integers. Let's say I sorted the last N-1 integers, so that my array would look like

------------------------------------------------|
| a[0]         | a[1] | a[2] | ...... | a[N-1]  |
------------------------------------------------|
| out of order | ......... all sorted ......... | 

如果你能做到这一点，那么由于你只有一个乱序元素，你应该能够弄清楚如何交换元素以将 a[0] 放在正确的位置.

If you could do that, then since you only have one out-of-order element, you should be able to figure out how to swap elements to get a[0] in the right place.

所以现在方法的大纲如下所示:

So now the outline of a method looks like this:

void sort(int[] a, int i) {   // sort the elements from a[i] to a[N-1]
    if (i <= a.length - 2) {
        // Solve the smaller problem recursively.  But if the smaller problem is
        // only 0 or 1 elements, there's nothing else to do.
        sort (a, i + 1);      
    }
    // At this point, we've sorted elements from a[i+1] to a[N-1].  Now a[i] is
    // out of order; write logic that exchanges elements to get a[i] in the right
    // place.
}

另一种可能的方法:不是先对 N-1 个元素进行排序，您可以找到最小的元素，将其移动到数组的开头，这样您的数组看起来像

Another possible approach: Instead of sorting the N-1 elements first, you could find the smallest element, move it to the beginning of the array, so that your array looks like

--------------------------------------------|
| a[0]     | a[1] | a[2] | ...... | a[N-1]  |
--------------------------------------------|
| in order | ........ out of order ........ | 

and then 递归调用该方法将 N-1 个元素 a[1] 排序到 a[N-1]，然后那么你就完成了.

and then call the method recursively to sort the N-1 elements a[1] to a[N-1], and then you're done.

我认为您的起点是正确的；你只需要以正确的方式将问题形象化，这需要一点练习.

I think you started out on the right track; you just need to visualize the problem in the correct way, which takes a little practice.

这篇关于如何使用递归创建排序方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！