我需要实现这个算法,在每次递归调用时创建一个新的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);
}
}
}
发布于 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
50
发布于 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]);
}
}
https://stackoverflow.com/questions/50891422
复制相似问题