使用 java 中的选择排序按字符串对用户定义的数组进行排序

Question

我正在做作业，我需要执行二分查找。但不知何故，我认为我的选择排序有问题。在这里我有一个用户定义的 class 叫做 Record。它具有以下属性：

class Record{
   String studentId;
   int assignment;
   int exam;
   int total;
   String grade;
}

我有这些属性的吸气剂。现在有另一个 class 叫做 GradeBook，其中有一个 Record 类型的数组。我通过名为 loadFromTables 的方法手动加载记录数组，如下所示：

private void loadFromTables(){

    String[] students = {
        "S10","S20","S30","S40","S50", "S60", 
        "S08","S18","S28","S38","S48", "S58",
        "S06","S16","S26","S36","S46", "S56",
    };

    int[] assignment = {
        0, 10, 20, 30, 30, 40, 
        0, 10, 20, 30, 30, 40, 
        0, 10, 20, 30, 30, 40,
    };

    int[] exam = {
        0, 39, 44, 44, 54, 59, 
        1, 40, 45, 45, 55, 60, 
        2, 41, 46, 46, 56, 58, 
    };

    nrecords = students.length;
    gradeBook = new Record[nrecords];

    for (int i = 0; i < nrecords; i++ ) {

        int t = assignment[i] + exam[i];
        String g = calculateGrade(t);
        Record r = new Record( students[i], assignment[i], exam[i], t, g );
        gradeBook[i] = r;

    }


}

现在我想进行二进制搜索以通过属性 studentId 查找记录。但首先我必须对 记录数组 进行排序。我被告知使用 选择排序。所以，我这样做了，我认为 这就是问题所在 但我似乎无法弄清楚哪里..:[=15=]

private void sortById(){

    //Selection Sort

    for(int i=0; i<nrecords-1; i++){

        int index = i;

        for(int j=i+1; j<nrecords; j++){

            if((gradeBook[index].studentId).compareTo(gradeBook[j].studentId) > 0){

                index = j;

            }

            Record temp =  gradeBook[i];
            gradeBook[i] = gradeBook[index];
            gradeBook[index] = temp;

        }

    }

}

这是我使用的二进制搜索代码，尽管我认为二进制搜索已正确实现。因为我试图用 冒泡排序 来做到这一点，而这正是我想要的。

public Record find(String id){

    //Binary Search

    int low = 0;
    int high = nrecords - 1;
    Record record = null;

    while(low <= high){

        int mid = (high + low)/2;

        if(id.compareTo(gradeBook[mid].studentId) == 0){

            record = new Record(id, gradeBook[mid].assignment, gradeBook[mid].exam, gradeBook[mid].total, gradeBook[mid].grade);
            return record;

        }
        else if(id.compareTo(gradeBook[mid].studentId) > 0){

            low = mid + 1;

        }
        else if(id.compareTo(gradeBook[mid].studentId) < 0){

            high = mid - 1;

        }

    }

    return record;

}

提前致谢。我知道问题出在选择排序上，这让我很头疼。感谢您的建议！ :)

Answer 1

在选择排序中，我们首先遍历子数组，找到子数组中的最小元素，最后在每次迭代中，Swap当前和最小元素。

您的代码中存在问题。

for(int j=i+1; j<nrecords; j++){

    if((gradeBook[index].studentId).compareTo(gradeBook[j].studentId) > 0){
            index = j;
    }

    Record temp =  gradeBook[i];
    gradeBook[i] = gradeBook[index];
    gradeBook[index] = temp;

}

您已正确找到最小元素，但是当您找到比当前字符串更小的字典序字符串时，您正在迭代中进行交换。所以在这个循环中，你只需要找到最小的元素，swap操作应该在这个循环执行后完成。

更正代码：

private void sortById(){

    //Selection Sort

    for(int i=0; i<nrecords-1; i++){

        int index = i;

        for(int j=i+1; j<nrecords; j++){

            if((gradeBook[index].studentId).compareTo(gradeBook[j].studentId) > 0){

                index = j;

            }

            Record temp =  gradeBook[i];
            gradeBook[i] = gradeBook[index];
            gradeBook[index] = temp;

        }

    }

}

使用 java 中的选择排序按字符串对用户定义的数组进行排序

Sorting user defined array by string using selection sort in java

java

arrays

sorting

selection-sort