递归选择排序 Java

Question

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

• 必须排序的数组
• 一个值 k，指示直到哪个 元素，它必须被排序。

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

我正在考虑从 k 为 0 的 if 语句开始，如果是这种情况，它只会按原样返回数组，因为您无法对大小为 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

首先对你的代码进行一些注释：

• 您的方法sort，selectionSort不需要返回int[]数组， 因为数组对象a始终保持不变。 只有此数组中的内容会发生变化。 因此，您可以使用void作为返回类型。
• 在您的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代码。

Answer 2

通过做一个简单的谷歌搜索，我在这个网站上找到了下面代码的最大部分。我自己添加了selectionSort方法以适合您的参数。

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