java - 如何使用递归创建排序方法？

Question

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

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); 
    }
}

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

Answer 1

要编写递归算法，您需要沿着这些思路思考:如何通过解决同一问题的一个或多个较小实例来解决问题？对于像“对 N 个整数的数组进行排序”这样的问题，较小的问题可能是一个 N-1 个整数的数组，也可能是两个 N/2 个整数的数组(大致)，或者其他可能性。

由于您没有给出任何其他提示，最简单的事情是:好的，我有一个包含 N 个整数的数组。假设我对最后的 N-1 个整数进行了排序，这样我的数组看起来像

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

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

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

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 个元素进行排序，而是找到最小的元素，将其移动到数组的开头，这样您的数组看起来像

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

和then递归调用该方法将N-1个元素a[1]排序为a[N-1]，并且然后你就完成了。

我认为您的起点是正确的；您只需要以正确的方式想象问题，这需要一些练习。