Java中的递归选择排序
Java中的递归选择排序
提问于 2018-06-17 04:14:02
我需要实现这个算法，在每次递归调用时创建一个新的ArrayList对象。
我的起始数组包含顺序为“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));
}
}驱动程序类
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);
}
}
}回答 2
Stack Overflow用户
发布于 2018-06-17 05:03:27
使用您的最后一个循环：
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()方法返回List)，然后去掉了最后一个循环，并在其中创建了新对象。
同样，你也必须改变
s.sort();至：
s.sort(s.getarraylist());输出：
ARRAY ELEMENTS
20
40
10
30
50
5
SORTED ELEMENTS
5
10
20
30
40
50Stack Overflow用户
发布于 2018-06-17 05:06:18
我不确定我是否理解了这个问题，但我创建了一个递归的(和迭代的) 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]);
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50891422
复制相关文章
相似问题