如何编写一个使用泛型Comparable类型在java中对ArrayList进行排序的方法

Question

我正在尝试编写一个方法来对整数数组进行排序。

该方法必须使用Comparable接口。我设计了一个测试用例，并试图编写一个解决方案。

预期：

Enter 10 integers: 3 4 12 7 3 4 5 6 4 7
The sorted numbers are 3 3 4 4 4 5 6 7 7 12

实际：

Enter 10 integers: 1
Enter 10 integers: 2
Enter 10 integers: 34
Enter 10 integers: 4
Enter 10 integers: 3
Enter 10 integers: 2
Enter 10 integers: 1
Enter 10 integers: 4
Enter 10 integers: 5
Enter 10 integers: 6
The sorted numbers are: 3 5 4 1 2 2 1 4 5 6

我的尝试

public class Test2 {

public static void main(String args[]){
ArrayList<Integer> array = new ArrayList<>();
Scanner input = new Scanner(System.in);
for(int i = 0; i < 10; i++){
System.out.print("Enter 10 integers: ");
int integer    = input.nextInt();
array.add(integer);
}
sort(array);
System.out.print("The sorted numbers are ");
for(int i = 0; i <= array.size()-1; i++){
System.out.print(array.get(i)+" ");
}
}
public static <E extends Comparable <E>> void sort(ArrayList<E> list) {
int n = list.size();

for(int  i = 1; i < n-1; i++) {
for(int j = 0; j < n-i-1; j++) {
if(list.get(i).compareTo(list.get(i+1)) < 0) {
E temp = list.get(i);
list.set(j, list.get(j+1));
list.set(j + 1, temp);
}
}
}
}
}

我下一步可以尝试什么？

Answer 1

它的工作方式不同，因为您可以将值分配给数组的元素。

对于列表，您必须使用方法set():

list.set(j + 1, temp);

此外，避免将ArrayList等具体类型用于方法参数和变量，请根据List等接口编写代码。现在，您的方法sort()仅限于接受实例ArrayList，而不能处理LinkedList。

Answer 2

实际上逻辑是错误的，重复交换不一定会对所有内容进行排序。

该代码没有提供任何保证来覆盖所有需要交换的配对：

public static <E extends Comparable <E>> void sort(List<E> list) {
int n = list.size();
for (int  i = 1; i < n-1; i++) { // n-2 i's
for (int j = 0; j < n-1-i; j++) { // for all i: n-1-i
if (list.get(i).compareTo(list.get(i+1)) < 0) {
Collections.swap(i, j+1);
}
}
}
}

它假设n-1-i之后的元素稍后将被排序。特别是最后一个元素i==n-1似乎没有被处理。

更值得信赖：

public static <E extends Comparable <E>> void sort(List<E> list) {
int n = list.size();
// INVARIANT list[0, i> is sorted
for (int  i = 0; i < n; i++) {
// INVARIANT list[0, i> is sorted
// INVARIANT list[0, j> is sorted
// INVARIANT list[j, i> is sorted
for (int j = 0; j < i; j++) {
// INVARIANT list[0, j> is sorted
// INVARIANT list[j, i> is sorted
if (list.get(i).compareTo(list.get(j)) < 0) {
Collections.swap(i, j);
// And greater j's are unsorted w.r.t. j
}
// INVARIANT list[j+1, i> is sorted
// INVARIANT list[0, j+1> is sorted
}
// INVARIANT list[0, i+1> is sorted
}
// INVARIANT list[0, n> is sorted
}

您可以检查前置条件、后置条件、循环变体、不变量和证明。

(两者的(复杂性都是O(n²(，这可能会更好，因为100²已经是10_000(5_000个循环步骤(。

Answer 3

import java.util.ArrayList;
import java.util.Scanner;

public class Exercise19_09 {

public static void main(String args[]){
ArrayList<Integer> array = new ArrayList<>();
Scanner input = new Scanner(System.in);
System.out.print("Enter 10 integers: ");
for(int i = 0; i < 10; i++){
int integer    = input.nextInt();
array.add(integer);
}
sort(array);
System.out.print("The sorted numbers are ");
for(int i = 0; i <= array.size()-1; i++){
System.out.print(array.get(i)+" ");
}
}
public static <E extends Comparable <E>> void sort(ArrayList<E> list){
int n = list.size();

for(int  i = 0; i < n-1; i++){
for(int j = 0; j < n-i-1; j++)
if(list.get(j).compareTo(list.get(j+1)) > 0){
E temp = list.get(j);
list.set(j, list.get(j+1));
list.set(j + 1, temp);
}
}
}
}