c++ - 查找计数排序的起始索引

Question

int schoolToIndex(string school) {
    if (school == "UCB")  return 0;
    if (school == "UCD")  return 1;
    if (school == "UCI")  return 2;
    if (school == "UCLA") return 3;
    if (school == "UCM")  return 4;
    if (school == "UCSD") return 5;
    if (school == "UCSF") return 6;

    cerr << "Unknown school " << school << endl;
    return -1;
}



void sortByGroupById2(Student students[], int len) {
    int numberofschools = 7;
    int counters[numberofschools];

    for (int i = 0; i < numberofschools; i++) {
        counters[i] = 0;
    }

    for (int i = 0; i < numberofschools; i++) {
        counters[schoolToIndex(students[i].getSchool())]++;
    }

    Student *sortedArray = new Student[len];

    for (int i = 0; i < len; i++) {
    sortedArray[counters[schoolToIndex(students[i].getSchool())]] = students[i];
    counters[schoolToIndex(students[i].getSchool())]++;
    }

    for (int i = 0; i < len; i++) {
        students[i] = sortedArray[i];
    }

}

int main() {
    const int LEN = 350000;

    // Rough timing
    Student* uc2 = readStudentsFromFile("uc_students_sorted_by_id.txt", LEN);
    time(&start);
    sortByGroupById2(uc2, LEN);
    time(&end);
    cout << "Using counting sort it took " << difftime(end, start) << " seconds." << endl;

    writeStudentsToFile(uc1, LEN, "uc_by_school_by_id1.txt");
    writeStudentsToFile(uc2, LEN, "uc_by_school_by_id2.txt");
    return 0;
}

我有疑问的具体问题在代码中

 sortedArray[counters[schoolToIndex(students[i].getSchool())]] = students[i],

sortedArray 的开始索引是学校的学生人数。我不确定如何做的是让起始索引为之前学校的学生累计数。

例如，如果我想要 UCLA 的起始索引，我需要将 UCB 和 UCD 以及 UCI 的学生人数相加以获得该桶的起始索引。

所以我的行动计划是让计数器数组存储学生人数的组合值。 例如，如果我的计数器数组有 [5, 10, 15, 20] 作为学生人数，我希望它存储 [5, 15, 30, 50] 作为我的 sortedArray 的起始索引数组。

我可以使用什么方法吗？我使用递归吗？

Answer 1

计数排序的一部分是对 counters[] 的转换从简单的直方图到索引到sortedArray[]的数组.

为此，您使用一种称为部分求和的算法。

对于每个元素，使其等于所有先前元素加上该元素的总和。例如:

0 1 3 0 4 0   -->    0 1 4 4 7 7

(您可以手动执行此操作或使用 std::partial_sum() 中的 <numeric> 函数。)

现在您可以使用索引将内容移动到输出中的最终位置。为了保持稳定，从 students[] 中的 last 元素开始并在 histogram 输出索引数组中查找它。

从值中减一(修改输出索引)并将源元素复制到最终数组:

for (int i = len; i-->0; )
{
    sortedArray[ --counters[ students[i].getSchool() ] ] = students[i];
}

希望这对您有所帮助。