递归选择排序Java

Question

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

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

示例：SelectionSort(array[] a, int k)，a 为 {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)
}

我不知道如何执行“其他”部分，因为我只知道它必须再次调用该方法。 我不允许创建其他方法。我还需要确保我正好使用 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;
    }

Answer 3

尝试一下，这是代码的基本情况，我给出了代码顺序并给出了解释。

 public int[] selectionSort(int[] a, int k) {
         // Base case
            if (k == 0) {
                return a;
            }

下面的代码显示您应该添加数组中从索引 0 到 k 的最小元素。

int minIndex = k;
for (int i = 0; i <= k; i++) {
    if (a[i] < a[minIndex]) {
        minIndex = i;
    }
}

下面的代码显示了使用此方法将最小元素与索引 k 处的元素交换

  int temp = a[k];
a[k] = a[minIndex];
a[minIndex] = temp;

然后add 递归调用函数对子数组从0到k-1进行排序

 return selectionSort(a, k - 1);

更多解释： 我添加了递归方法，该函数通过对前 k 个元素的子数组进行排序，在每次调用中将问题大小减少 1。

并且您应该找到最小值 在每一步中，该函数都会找到子数组中的最小元素并将其放置在子数组的末尾（第 k 个索引）。

& Swapping 方法会帮助你找到最小的元素与当前索引 k 处的元素进行交换。