递归选择排序 Java

Question

我一直在寻找递归选择排序，只使用 2 个参数：

需要排序的数组
一个值k，表示直到必须对其进行排序的元素。

示例：SelectionSort(array[] a, int k) 当 a 为 {6,3,5,7,2} 并且 k 为 2 时，将对前 3 个元素进行排序，并保持最后一个元素不变。

我正在考虑从 k 为 0 的 if 语句开始，如果是这样的话，它只会 return 数组原样，因为你不能对大小为 1 的数组进行排序. 类似于：

public int[] sort(int[] a){
    a = selectionSort(a, n-1);
    return a;
}

public int[] selectionSort(int[] a, int k){
    if (k = 0){
        return a;
    }
    else{
        selectionSort(a, k-1 );
               ... (part i really don't know)
}

我不知道如何执行 'else' 部分，因为我只知道它必须再次调用该方法。我不允许创建其他方法。我还需要确保我使用了 2 个参数，仅此而已。

我必须用伪代码来解决它，但我理解一些 Java，所以如果有人可以通过使用伪代码或 Java 来帮助我，那将非常有帮助

Answer 1

编辑：OP 澄清了问题，这可能与 OP 无关，但可能与未来的访问者有关。

请记住您下次对问题的评论。就这一次，我会帮你的，因为你是新来的。通过简单的 google 搜索，我在 this site 上找到了下面代码的大部分。我自己添加了 selectionSort 方法以适合您的参数。请注意，Stack Overflow 不是代码编写服务（尽管人们经常提供代码，但这不是答案的要求）。

    public void selectionSort(int a[], int n) 
    {
      recurSelectionSort(a, n, 0);
    }

    // Recursive selection sort. n is size of a[] and index
    // is index of starting element.
    static void recurSelectionSort(int a[], int n, int index)
    {

        // Return when starting and size are same
        if (index == n)
           return;

        // calling minimum index function for minimum index
        int k = minIndex(a, index, n-1);

        // Swapping when index nd minimum index are not same
        if (k != index){
           // swap
           int temp = a[k];
           a[k] = a[index];
           a[index] = temp;
        }
        // Recursively calling selection sort function
        recurSelectionSort(a, n, index + 1);
    }

    // Return minimum index
    static int minIndex(int a[], int i, int j)
    {
        if (i == j)
            return i;

        // Find minimum of remaining elements
        int k = minIndex(a, i + 1, j);

        // Return minimum of current and remaining.
        return (a[i] < a[k])? i : k;
    }

Answer 2

首先对您的代码做一些说明：

您的方法 sort 和 selectionSort 不需要 return 一个 int[] 数组，因为数组对象 a 一直保持不变。只有这个数组中的内容发生了变化。因此，您可以使用 void 作为 return 类型。
在你的 if 中使用 (k == 0) 而不是 (k = 0)

您已经了解了第一部分。下面是如何用伪代码完成第二部分：

public void selectionSort(int[] a, int k) {
    if (k == 0) {
        return;
    }
    else {
        selectionSort(a, k-1 );
        find x such that a[x] is the smallest of a[k] ... a[a.length - 1]
        if (a[k-1] > a[x]) {
            swap a[k-1] and a[x]
        }
    }
}

我相信您能够将伪代码提炼成真正的 Java 代码。

递归选择排序 Java

Recursive Selection sort Java

java

recursion

pseudocode

selection-sort