Java 中的递归选择排序

Question

我需要实现这个算法，在每次递归调用时创建一个新的 ArrayList object。

我的起始数组包含顺序为“20, 40 ,10, 30 ,50 ,5” 的整数，排序后得到 5,5,5,5,5,5。我认为问题出在递归调用和 SelectionSort 的最后一个 for cicle 中，因为删除最后一个 for 我注意到第一个元素已正确排序。

import java.util.*;

public class SelectionSort {

   //var
   public ArrayList<Integer> arr ;

   //constructor
   public SelectionSort(ArrayList<Integer> arr){
      this.arr = arr;
   }

   public ArrayList<Integer> getarraylist() {
   return arr;
   }


   public void sort(){  

     //position of the last sorted element
     int minimum =0;

     if (arr.size() <=0 )  return;

     for ( int j = 1; j < arr.size()-1; j++ ) { 

           if (arr.get(j) < arr.get(0) ) {
               minimum = j;
               //swap element 0 and minimum
               int temp = arr.get(0);
               arr.set(0, arr.get(minimum));
               arr.set(minimum, temp);
           }
     }

     //recursive call, new array without first element (already sorted)
     ArrayList<Integer> arr2 = new ArrayList<>(arr.subList(1,arr.size()));
     SelectionSort s2 = new SelectionSort(arr2);
     s2.sort();

     for(int i=0;i<s2.getarraylist().size();i++) {
         arr.set(i, s2.getarraylist().get(i));
     }
}

Driver class

public class Main {

    public static void main(String[] args) {

    ArrayList<Integer> arr = new ArrayList<Integer (Arrays.asList(20,40,10,30,50,5));


    System.out.println("\n ARRAY ELEMENTS \n ");
    for (int i: arr) {
        System.out.println(i);
    }

    System.out.println("\n SORTED ELEMENTS \n ");
    SelectionSort s = new SelectionSort(arr);
    s.sort();
    for (int i: s.getarraylist()) {
        System.out.println(i);
    }

}
}

Answer 1

最后一个循环：

for(int i=0;i<s2.getarraylist().size();i++) {
     arr.set(i, s2.getarraylist().get(i));
 }

这会覆盖所有具有相同编号的元素。（为什么你的结果全是 5）这是因为你只迭代到倒数第二个元素（arr.size()-1）。然后复制行中的元素：

 ArrayList<Integer> arr2 = new ArrayList<>(arr.subList(1,arr.size()));

最终，您只是将最后一个元素复制到 (5)，然后将其复制到最后的 ArrayList arr。

每次调用 sort 方法时，您还创建了另一个 SelectionSort 对象。这样不好。

这是我写的代码：

 public void sort(List<Integer> list){  

     //position of the last ordered element
     int minimum =0;
     if (list.size() <=0 )  return;

     for ( int j = 1; j < list.size(); j++ ) { 

           if (list.get(j) < list.get(0) ) {
               minimum = j;
               //swap element 0 and minimum
               int temp = list.get(0);
               list.set(0, list.get(minimum));
               list.set(minimum, temp);

           }

     }


     sort(list.subList(1,list.size()));
}

我将其更改为接受 List<Integer> 的参数（因为 subList() 方法 returns a List）然后摆脱了最后一个循环以及你在哪里创建了新对象。

你还必须改变

s.sort();

至：

s.sort(s.getarraylist());

输出：

 ARRAY ELEMENTS 

20
40
10
30
50
5

 SORTED ELEMENTS 

5
10
20
30
40
50

Answer 2

我不确定我是否理解这个问题，但我创建了一个递归（和迭代）selectionSort 和 InsertionSort 只是为了好玩，希望它有所帮助。

public class Sorts {
    public static void swap(Comparable[] a, int i, int j) {
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void selectionSortItr(Comparable[] a, int n) {
        for (int i = 0; i < n - 1; i++) {
            int f = i;
            for (int j = i + 1; j < n; j++) {
                if (a[j].compareTo(a[f]) < 0)
                    f = j;
            }
            swap(a, i, f);
        }
    }

    public static int select(Comparable[] a, int n, int j, int f) {
        if (j >= n) 
            return f;
        if (a[j].compareTo(a[f]) < 0)
            f = j;
        return select(a, n, j + 1, f);
    }

    public static void selectionSort(Comparable[] a, int n, int i) {
        if (i < n - 1) {
            swap(a, i, select(a, n, i + 1, i));
            selectionSort(a, n, i + 1);
        }
    }

    public static void insertionSortItr(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            int j;
            Comparable cur = a[i];
            for (j = i; j > 0 && cur.compareTo(a[j - 1]) < 0; j--) {
                a[j] = a[j - 1];
            }
            a[j] = cur;
        }
    }

    public static void insertionSortInner(Comparable[] a, Comparable cur, int j) {
        if (j > 0 && cur.compareTo(a[j - 1]) < 0) {
            a[j] = a[j - 1];
            insertionSortInner(a, cur, j - 1);
        } else {
            a[j] = cur;
        }
    }

    public static void insertionSort(Comparable[] a, int i, int n) {
        if (i < n) {
            insertionSortInner(a, a[i], i);
            insertionSort(a, i + 1, n);
        }
    }

    public static void main(String[] args) {
        Integer[] a = new Integer[10];
        for (int i = 0; i < 10; i++) 
            a[i] = (int) (Math.random()*100);
        selectionSort(a, 10, 0);
        for (int i = 0; i < 10; i++) 
            System.out.println(a[i]);
    }
}

Answer 3

您的算法中实际上有两个错误，它们共同导致观察到的输出。

第一个错误出现在 for 循环中，它决定了最小元素：

for ( int j = 1; j < arr.size()-1; j++ ) { ...

您过早地终止了一个元素，即从未考虑过最后一个元素。因此，在第一次迭代之后，5 是 ArrayList 中的最后一个元素。事实上，它是每个的 ArrayList 中的最后一个元素。解决方法是不在 for 条件中减去 1：

for ( int j = 1; j < arr.size(); j++ ) { ...

第二个错误出现在你的最后一个 for 循环中，你将值从 s2 的索引 i 复制到 arr 的索引 i .您忽略了 s2 比 arr 短一个元素这一事实。因此，唯一没有被覆盖的元素是最后一个元素。解决方法是从 s2 获取第 i 个元素，但将其写入 arr 的第 i + 1 个索引处：

arr.set(i + 1, s2.getarraylist().get(i));

现在让我们看看这两个错误是如何导致观察到的输出的。自

您的 ArrayList 中的最后一个元素永远不会被覆盖并且
最后一个元素总是相同的，

所有元素都具有相同的值（在您的测试用例中：5）。

对您的代码的一些评论：

变量minimum是多余的，可以用j代替。
如果将 SelectionSort 中出现的所有 ArrayList 替换为 List，实际上可以将代码的最后一部分简化为：
```
// remove the line declaring arr2, it is no longer needed
SelectionSort s2 = new SelectionSort(arr.subList(1, arr.size()));
s2.sort();
// last for-loop not needed anymore, method ends here
```
这是可能的，因为ArrayList#subList(...) states that "The returned list is backed by this list, so non-structural changes in the returned list are reflected in this list, and vice-versa."
你应该多注意一点。缩进。
您的编码风格有一些小的不一致之处。例如，有时您在 ( 之后或 ) 或 { 之前写一个空格，有时您不这样做。看自己多喜欢，统一使用
在Java中，变量名、参数名和方法名应该写在camelCase中（getarraylist() -> getArrayList()）

Java 中的递归选择排序

Recursive Selection Sort in Java

java

sorting

recursion

arraylist

selection-sort