题解 | #成绩排序#

#include <iostream>
#include <algorithm>
using namespace std;

int Partition(int A[], int B[], int low, int high) {
    int pivot = A[low];
    int pivot2 = B[low];

    while (low < high) {
        while (low < high && A[high] >= pivot)     high--;
        A[low] = A[high];
        B[low] = B[high];

        while (low < high && A[low] <= pivot)      low++;
        A[high] = A[low];
        B[high] = B[low];
    }
    A[low] = pivot;
    B[low] = pivot2;
    return low;
}

void Qsort(int A[], int B[], int low, int high) {
    if (low < high) {
        int pivotpos = Partition(A, B, low, high);
        Qsort(A, B, low, pivotpos - 1);
        Qsort(A, B, pivotpos + 1, high);
    }
}

void SameSort(int A[], int B[], int size) {
    int count = 1;
    int current = A[0];
    int start = 0;  //相同成绩区段

    for (int i = 1; i <= size; i++) {
        if (A[i] != current) {
            if (count != 1) sort(B + start, B + i);
            count = 1;
            start = i;
            current = A[i];
        } else count++;
    }
}

int main() {
    int size;  //学生人数
    while (scanf("%d", &size) != EOF) {
        int* sName = new int[size]();
        int* sGrade = new int[size]();
        for (int i = 0; i < size; i++)
            scanf("%d %d", &sName[i], &sGrade[i]);
        Qsort(sGrade, sName, 0, size - 1);
        SameSort(sGrade, sName, size);
        for (int i = 0; i < size; i++)
            printf("%d %d\n", sName[i], sGrade[i]);
        free(sName);
        free(sGrade);
    }
}