使用插入排序对象的arraylist排序

Question

这是我的代码，使用选择。我需要使用插入，并且不要使用临时数组或ArrayList。我需要如何做插入排序的帮助。

public static void sortStudents(ArrayList<Student> list) 
{//selection sort 
    Student tempStudent; 
    int count1; 
    int count2; 
    int largest; 

    for (count1=0; count1<list.size()-1; count1++) 
    { 
    largest = 0; 
    for (count2=largest+1; count2<list.size()-count1; count2++) 
    { 
    if ((list.get(largest)).compareTo(list.get(count2)) < 0) 
    { 
    largest = count2; 
    } 
    } 
    tempStudent = list.get(list.size()-1-count1); 
    list.set(list.size()-1-count1, list.get(largest)); 
    list.set(largest, tempStudent); 
    } 
} 
} 

Answer 1

选择排序和插入排序的工作方式非常类似，具有列表的“尚未排序”部分和“已排序”部分。一开始，第一个是整个列表，第二个是开始或结束时的空列表。虽然排序“尚未排序”的部分收缩，而“已排序”的部分增长，每迭代一个元素。

选择排序和插入排序的区别是这样的：

• 对于选择排序，你搜索“尚未分类”部分的最小（或最大）元素，有删除它，然后将其添加到已排序部分的结尾（或开始）。
• 对于插入排序，您需要列表中“未排序”部分的下一个元素，在“已排序”部分找到它的插入点并将其插入到那里。

这应该足以将您的选择排序更改为插入排序。

Answer 2

如果仅在循环中使用，则不在循环外定义变量。限制变量的生命周期使得代码更容易推理。

public static void sortStudents (ArrayList<Student> list) 
{ 
    int largest; 

    for (int i=0; i < list.size() - 1; i++) 
    { 
    largest = 0; 
    for (int j=largest + 1; j < list.size() - i; j++) 
    { 
     if ((list.get (largest)).compareTo (list.get (j)) < 0) 
     { 
     largest = j; 
     } 
    } 
    Student tempStudent = list.get (list.size() - 1 - i); 
    list.set (list.size() - 1 - i, list.get (largest)); 
    list.set (largest, tempStudent); 
    } 
} 

多一点缩进让您的代码更具可读性。现在你的具体错误是什么 - 不编译它，会抛出异常还是会产生错误的结果？

下面是一些在内部循环可疑：

largest = 0; 
    for (int j=largest + 1; j < list.size() - i; j++) 

如果设置最大的为0，则j将被初始化为0 + 1 => 1。我想你有另一个意图。你的意思是j = i + 1;？