数据结构：快速排序与归并排序的深入优化

1.3 三种快排单趟排序运行结果分析

从下面的运行结果分析，lomuto 的前后指针法，面对 key 有大量重复时，lomuto 划分不是很理想，性能退化，hoare 相对还不错，但是大量重复时，没有三路划分快。三路划分算法，把跟 key 相等的值都划分到了中间，可以很好的解决这里的问题。

2.排序数组 OJ 题

排序数组

下面我们来看看这个 OJ 题，这个 OJ，当我们用快排的时候，lomuto 的方法，过不了这个题目，hoare 版本可以过这个题目。堆排序和归并和希尔是可以过的，其他几个 O(N^2) 也不过了，因为这个题的测试用例中不仅仅有数据很多的大数组，也有一些特殊数据的数组，如大量重复数据的数组。堆排序和归并和希尔不是很受数据样本的分布和形态的影响，但是快排会，因为快排要选 key，每次 key 都当趟分割都很偏，就会出现效率退化问题。

• 前面我们分析了 lomuto 的前后指针面对大量重复数据时，效率会退化，hoare 版本会好很多，所以 hoare 是可以过这个 OJ 的，但是 OJ 还是一个相对局限的测试，就像 leetcode 官方为啥开始写的答案是 lomuto，说明那会 lomuto 是可以过的，后面加了大量重复数值的测试用例，所以就过不了，但是答案忘记改了，说明写答案讲解和测试用例补充的不是一个团队，协作出问题。那么 hoare 现在可以过，leetcode 哪天增加一个特殊测试用例以后，就过不了，三路划分也类似，因为他们的思想还是在特殊场景下效率会退化，比如大多数选 key 都是接近最小或者最大的值，导致划分不均衡，效率退化。

1. introsort 是由 David Musser 在 1997 年设计的排序算法，C++ sgi STL sort 中就是用 introspective sort(内省排序) 思想实现的。内省排序可以认为不受数据分布的影响，无论什么原因划分不均匀，导致递归深度太深，他就是转换堆排了，堆排不受数据分布影响，具体看下面代码。
2. 其次三路划分针对有大量重复数据时，效率很好，其他场景就一般，但是三路划分思路还是很有价值的，有些快排思想变形体，要用划分去选数，他能保证跟 key 相等的数都排到中间去，三路划分的价值就体现出来了。

下面我分别展示一下这几种思想去跑排序数组 oj 的思路和代码。

2.1 lomuto 的快速排序跑排序数组 OJ 题

void Swap(int* x, int* y){
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

void QuickSort(int* a, int left, int right){
    if(left >= right) return;
    int begin = left;
    int end = right;
    // 随机选 key
    int randi = left + (rand()%(right-left +1));
    // printf("%d\n", randi);
    Swap(&a[left], &a[randi]);
    int prev = left;
    int cur = prev + 1;
    int keyi = left;
    while(cur <= right){
        if(a[cur] < a[keyi] && ++prev != cur){ Swap(&a[prev], &a[cur]); }
        ++cur;
    }
    Swap(&a[prev], &a[keyi]); keyi = prev;
    // [begin, keyi-1] keyi [keyi+1, end]
    QuickSort(a, begin, keyi -1);
    QuickSort(a, keyi+1, end);
}

int* sortArray(int* nums, int numsSize, int* returnSize){
    srand(time(0));
    QuickSort(nums, 0, numsSize-1);
    *returnSize = numsSize;
    return nums;
}

2.2 hoare 的快速排序跑排序数组 OJ 题

void Swap(int* x, int* y){
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

void QuickSort(int* a, int left, int right){
    if(left >= right) return;
    int begin = left, end = right;
    int randi = left + (rand()%(right-left+1));
    Swap(&a[left], &a[randi]);
    int keyi = left;
    ++left;
    while(left <= right) // left 和 right 相遇的位置的值比基准值要大
    {
        // right 找到比基准值小或等
        while(left <= right && a[right] > a[keyi]){ right--; }
        // left 找到比基准值大或等
        while(left <= right && a[left] < a[keyi]){ left++; }
        if(left <= right){ Swap(&a[left++], &a[right--]); }
    }
    // right keyi 交换
    Swap(&a[keyi], &a[right]); keyi = right;
    // [begin, keyi-1] keyi [keyi+1, end]
    QuickSort(a, begin, keyi -1);
    QuickSort(a, keyi+1, end);
}

int* sortArray(int* nums, int numsSize, int* returnSize){
    srand(time(0));
    QuickSort(nums, 0, numsSize-1);
    *returnSize = numsSize;
    return nums;
}

2.3 三路划分的快速排序跑排序数组 OJ 题

void Swap(int* x, int* y){
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

void QuickSort(int* a, int left, int right){
    if(left >= right) return;
    int begin = left;
    int end = right;
    // 随机选 key
    int randi = left + (rand()%(right-left +1));
    Swap(&a[left], &a[randi]);
    // 三路划分
    // left 和 right 指向就是跟 key 相等的区间
    // [begin, left-1] [left, right] right+1, end]
    int key = a[left];
    int cur = left+1;
    while(cur <= right){
        // 1、cur 遇到比 key 小，小的换到左边，同时把 key 换到中间位置
        // 2、cur 遇到比 key 大，大的换到右边
        if(a[cur] < key){
            Swap(&a[cur], &a[left]);
            ++left;
            ++cur;
        } else if(a[cur] > key){
            Swap(&a[cur], &a[right]);
            --right;
        } else {
            ++cur;
        }
    }
    // [begin, left-1] [left, right] right+1, end]
    QuickSort(a, begin, left -1);
    QuickSort(a, right+1, end);
}

int* sortArray(int* nums, int numsSize, int* returnSize){
    srand(time(0));
    QuickSort(nums, 0, numsSize-1);
    *returnSize = numsSize;
    return nums;
}

2.4 introsort 的快速排序跑排序数组 OJ 题

introsort 是 introspective sort 采用了缩写，他的名字其实表达了他的实现思路，他的思路就是进行自我侦测和反省，快排递归深度太深 (sgi stl 中使用的是深度为 2 倍排序元素数量的对数值) 那就说明在这种数据序列下，选 key 出现了问题，性能在快速退化，那么就不要再进行快排分割递归了，改换为堆排序进行排序。

void Swap(int* x, int* y){
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

void AdjustDown(int* a, int n, int parent){
    int child = parent * 2 + 1;
    while(child < n){
        // 选出左右孩子中大的那一个
        if(child + 1 < n && a[child + 1] > a[child]){ ++child; }
        if(a[child] > a[parent]){ Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; }
        else{ break; }
    }
}

void HeapSort(int* a, int n){
    // 建堆 -- 向下调整建堆 -- O(N)
    for(int i = (n - 1 - 1)/2; i >= 0; --i){ AdjustDown(a, n, i); }
    // 自己先实现 -- O(N*logN)
    int end = n - 1;
    while(end > 0){
        Swap(&a[end], &a[0]);
        AdjustDown(a, end, 0);
        --end;
    }
}

void InsertSort(int* a, int n){
    for(int i = 1; i < n; i++){
        int end = i - 1;
        int tmp = a[i];
        // 将 tmp 插入到 [0,end] 区间中，保持有序
        while(end >= 0){
            if(tmp < a[end]){ a[end + 1] = a[end]; --end; }
            else{ break; }
        }
        a[end + 1] = tmp;
    }
}

void IntroSort(int* a, int left, int right, int depth, int defaultDepth){
    if(left >= right) return;
    // 数组长度小于 16 的小数组，换为插入排序，简单递归次数
    if(right - left + 1 < 16){ InsertSort(a+left, right-left+1); return; }
    // 当深度超过 2*logN 时改用堆排序
    if(depth > defaultDepth){ HeapSort(a+left, right-left+1); return; }
    depth++;
    int begin = left;
    int end = right;
    // 随机选 key
    int randi = left + (rand()%(right-left +1));
    Swap(&a[left], &a[randi]);
    int prev = left;
    int cur = prev + 1;
    int keyi = left;
    while(cur <= right){
        if(a[cur] < a[keyi] && ++prev != cur){ Swap(&a[prev], &a[cur]); }
        ++cur;
    }
    Swap(&a[prev], &a[keyi]); keyi = prev;
    // [begin, keyi-1] keyi [keyi+1, end]
    IntroSort(a, begin, keyi -1, depth, defaultDepth);
    IntroSort(a, keyi+1, end, depth, defaultDepth);
}

void QuickSort(int* a, int left, int right){
    int depth = 0;
    int logn = 0;
    int N = right - left + 1;
    for(int i = 1; i < N; i *= 2){ logn++; }
    // introspective sort -- 自省排序
    IntroSort(a, left, right, depth, logn*2);
}

int* sortArray(int* nums, int numsSize, int* returnSize){
    srand(time(0));
    QuickSort(nums, 0, numsSize-1);
    *returnSize = numsSize;
    return nums;
}

3.外排序介绍

外排序 (External sorting) 是指能够处理极大量数据的排序算法。通常来说，外排序处理的数据不能一次装入内存，只能放在读写较慢的外存储器 (通常是硬盘) 上。外排序通常采用的是一个'排序 - 归并'的策略。在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。然后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果。跟外排序对应的就是内排序，我们之前讲的常见的排序，都是内排序，他们排序思想适应的是数据在内存中，支持随机访问。归并排序的思想不需要随机访问数据，只需要依次按序列读取数据，所以归并排序既是一个内排序，也是一个外排序。

3.1 创建随机数据文件的代码

// 创建 N 个随机数，写到文件中
void CreateNDate(){
    // 造数据
    int n = 1000000;
    srand(time(0));
    const char* file = "data.txt";
    FILE* fin = fopen(file, "w");
    if(fin == NULL){ perror("fopen error"); return; }
    for(int i = 0; i < n; ++i){
        int x = rand() + i;
        fprintf(fin, "%d\n", x);
    }
    fclose(fin);
}

3.2 文件归并排序思路分析

1. 读取 n 个值排序后写到 file1，再读取 n 个值排序后写到 file2。
2. file1 和 file2 利用归并排序的思想，依次读取比较，取小的尾插到 mfile，mfile 归并为一个有序文件。
3. 将 file1 和 file2 删掉，mfile 重命名为 file1。
4. 再次读取 n 个数据排序后写到 file2。
5. 继续走 file1 和 file2 归并，重复步骤 2，直到文件中无法读出数据。最后归并出的有序数据放到了 file1 中。

3.3 文件归并排序代码实现

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

// 创建 N 个随机数，写到文件中
void CreateNDate(){
    // 造数据
    int n = 10000000;
    srand(time(0));
    const char* file = "data.txt";
    FILE* fin = fopen(file, "w");
    if(fin == NULL){ perror("fopen error"); return; }
    for(int i = 0; i < n; ++i){
        int x = rand() + i;
        fprintf(fin, "%d\n", x);
    }
    fclose(fin);
}

int compare(const void* a, const void* b){
    return (*(int*)a - *(int*)b);
}

// 返回实际读到的数据个数，没有数据了，返回 0
int ReadNDataSortToFile(FILE* fout, int n, const char* file1){
    int x = 0;
    int* a = (int*)malloc(sizeof(int)* n);
    if(a == NULL){ perror("malloc error"); return 0; }
    // 想读取 n 个数据，如果遇到文件结束，应该读到 j 个
    int j = 0;
    for(int i = 0; i < n; i++){
        if(fscanf(fout, "%d", &x) == EOF) break;
        a[j++] = x;
    }
    if(j == 0){ free(a); return 0; }
    // 排序 qsort(a, j, sizeof(int), compare);
    FILE* fin = fopen(file1, "w");
    if(fin == NULL){ free(a); perror("fopen error"); return 0; }
    // 写回 file1 文件
    for(int i = 0; i < j; i++){ fprintf(fin, "%d\n", a[i]); }
    free(a);
    fclose(fin);
    return j;
}

void MergeFile(const char* file1, const char* file2, const char* mfile){
    FILE* fout1 = fopen(file1, "r");
    if(fout1 == NULL){ perror("fopen error"); return; }
    FILE* fout2 = fopen(file2, "r");
    if(fout2 == NULL){ perror("fopen error"); return; }
    FILE* mfin = fopen(mfile, "w");
    if(mfin == NULL){ perror("fopen error"); return; }
    // 归并逻辑
    int x1 = 0;
    int x2 = 0;
    int ret1 = fscanf(fout1, "%d", &x1);
    int ret2 = fscanf(fout2, "%d", &x2);
    while(ret1 != EOF && ret2 != EOF){
        if(x1 < x2){ fprintf(mfin, "%d\n", x1); ret1 = fscanf(fout1, "%d", &x1); }
        else{ fprintf(mfin, "%d\n", x2); ret2 = fscanf(fout2, "%d", &x2); }
    }
    while(ret1 != EOF){ fprintf(mfin, "%d\n", x1); ret1 = fscanf(fout1, "%d", &x1); }
    while(ret2 != EOF){ fprintf(mfin, "%d\n", x2); ret2 = fscanf(fout2, "%d", &x2); }
    fclose(fout1);
    fclose(fout2);
    fclose(mfin);
}

int main(){
    CreateNDate();
    const char* file1 = "file1.txt";
    const char* file2 = "file2.txt";
    const char* mfile = "mfile.txt";
    FILE* fout = fopen("data.txt", "r");
    if(fout == NULL){ perror("fopen error"); return; }
    int m = 1000000;
    ReadNDataSortToFile(fout, m, file1);
    ReadNDataSortToFile(fout, m, file2);
    while(1){
        MergeFile(file1, file2, mfile);
        // 删除 file1 和 file2
        remove(file1);
        remove(file2);
        // 重命名 mfile 为 file1
        rename(mfile, file1);
        // 当再去读取数据，一个都读不到，说明已经没有数据了
        // 已经归并完成，归并结果在 file1
        int n = 0;
        if((n = ReadNDataSortToFile(fout, m, file2)) == 0) break;
    }
    return 0;
}

3.4 非递归版本的归并排序

// 归并排序 - 非递归版本
void MergeSortNonR(int* a, int n){
    int* tmp = (int*)malloc(sizeof(int)* n);
    if(tmp == NULL){ perror("malloc fail!\n"); exit(1); }
    int gap = 1;
    while(gap < n){
        // 根据 gap 划分组，两两一合并
        for(int i = 0; i < n; i += 2*gap){
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = end1 + 1, end2 = begin2 + gap - 1;
            if(begin2 >= n){ break; }
            if(end2 >= n){ end2 = n - 1; }
            int index = begin1;
            // 两个有序序列进行合并
            while(begin1 <= end1 && begin2 <= end2){
                if(a[begin1] < a[begin2]){ tmp[index++] = a[begin1++]; }
                else{ tmp[index++] = a[begin2++]; }
            }
            while(begin1 <= end1){ tmp[index++] = a[begin1++]; }
            while(begin2 <= end2){ tmp[index++] = a[begin2++]; }
            // 导入到原数组中
            memcpy(a + i, tmp + i, sizeof(int)*(end2 - i + 1));
        }
        gap *= 2;
    }
}

4.利用排序方法排序学生成绩表

题目要求：创建一个线性表用来存储学生成绩，每个学生的成绩信息作为一个数据元素，对应表中的一行。定义线性表的结构体类型，成绩表的数据项包括：学号、姓名、计算机基础、C 语言、数据结构成绩。首先输入学生人数确定要建立的线性表的长度，录入每个学生的成绩信息，并计算出其总成绩；然后，以总成绩为关键字进行直接插入排序；最后，逆序显示排序后的成绩表。

4.1 利用直接插入排序方法

// 利用直接插入排序方法排序学生成绩表
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdlib.h>
#include <stdio.h>
#define MAXSIZE 20
// 成绩表最大长度

// 定义结构体类型
typedef struct{
    char no[10]; // 学号
    char name[10]; // 姓名
    int score[3]; // 各科成绩
    int total; // 总成绩
} student;

typedef struct // 定义线性表类型
{
    student stu[MAXSIZE]; // 用数组存储每个学生的成绩信息
    int len; // 线性表的实际长度
} SeqList;

// 建立学生成绩统计表
SeqList create(SeqList L, int n){
    int i, j;
    printf("输入学生的学号、姓名、计算机基础、C 语言、数据结构成绩：\n");
    for(i = 1; i <= n; i ++){
        scanf("%s", L.stu[i].no); // 录入学号
        scanf("%s", L.stu[i].name); // 录入姓名
        L.stu[i].total = 0;
        for(j = 0; j < 3; j++){
            scanf("%d", &L.stu[i].score[j]); // 录入各科目的成绩
            L.stu[i].total = L.stu[i].total + L.stu[i].score[j]; // 计算总成绩
        }
        printf("总成绩为：%d\n\n", L.stu[i].total);
    }
    return L;
}

// 利用直接插入排序方式将总成绩升序排序，然后逆序输出
void Insertsort(SeqList L, int n){
    int i, j;
    for(i = 2; i <= n; i++)
        if(L.stu[i].total < L.stu[i-1].total){
            L.stu[0] = L.stu[i];
            L.stu[i] = L.stu[i-1];
            for(j = i - 2; L.stu[0].total < L.stu[j].total; j--) L.stu[j+1] = L.stu[j];
            L.stu[j+1] = L.stu[0];
        }
    printf("按照总成绩进行排序后的成绩表如下：\n");
    for(i = n; i >= 1; i--){
        printf("%s %s ", L.stu[i].no, L.stu[i].name);
        for(j=0; j<3; j++) printf("%d ", L.stu[i].score[j]);
        printf("%d\n", L.stu[i].total);
    }
}

// 主函数
int main(){
    SeqList List;
    printf("输入学生人数：");
    scanf("%d", &List.len);
    List = create(List, List.len);
    Insertsort(List, List.len);
}

4.2 利用冒泡排序方法

// 利用冒泡排序方法排序学生成绩表
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdlib.h>
#include <stdio.h>
#define MAXSIZE 20
// 成绩表最大长度

// 定义结构体类型
typedef struct{
    char no[10]; // 学号
    char name[10]; // 姓名
    int score[3]; // 各科成绩
    int total; // 总成绩
} student;

typedef struct // 定义线性表类型
{
    student stu[MAXSIZE]; // 用数组存储每个学生的成绩信息
    int len; // 线性表的实际长度
} SeqList;

// 建立学生成绩统计表
SeqList create(SeqList L, int n){
    int i, j;
    printf("输入学生的学号、姓名、计算机基础、C 语言、数据结构成绩：\n");
    for(i = 1; i <= n; i ++){
        scanf("%s", L.stu[i].no); // 录入学号
        scanf("%s", L.stu[i].name); // 录入姓名
        L.stu[i].total = 0;
        for(j = 0; j < 3; j++){
            scanf("%d", &L.stu[i].score[j]); // 录入各科目的成绩
            L.stu[i].total = L.stu[i].total + L.stu[i].score[j]; // 计算总成绩
        }
        printf("总成绩为：%d\n\n", L.stu[i].total);
    }
    return L;
}

// 冒泡排序方式将总成绩升序排序，然后逆序输出
void BubbleSort(SeqList L, int n){
    int i, j, flag = 1;
    for(i = 1; i <= n; i++){
        flag = 0; // 交换标志初始值为 0
        for(j = 1; j <= n - i; j++)
            if(L.stu[j].total > L.stu[j+1].total) // 比较总成绩大小
            {
                L.stu[0] = L.stu[j]; // 交换数据元素
                L.stu[j] = L.stu[j+1];
                L.stu[j+1] = L.stu[0];
                flag = 1; // 设置交换标志为 1
            }
        if(!flag) break; // 数据未发生交换时，排序结束
    }
    printf("按照总成绩进行排序后的成绩表如下：\n");
    for(i = n; i >= 1; i--){
        printf("%s %s ", L.stu[i].no, L.stu[i].name);
        for(j=0; j<3; j++) printf("%d ", L.stu[i].score[j]);
        printf("%d\n", L.stu[i].total);
    }
}

// 主函数
int main(){
    SeqList List;
    printf("输入学生人数：");
    scanf("%d", &List.len);
    List = create(List, List.len);
    BubbleSort(List, List.len);
}

4.3 利用直接选择排序方法

// 利用直接选择排序方法排序学生成绩表
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdlib.h>
#include <stdio.h>
#define MAXSIZE 20
// 成绩表最大长度

// 定义结构体类型
typedef struct{
    char no[10]; // 学号
    char name[10]; // 姓名
    int score[3]; // 各科成绩
    int total; // 总成绩
} student;

typedef struct // 定义线性表类型
{
    student stu[MAXSIZE]; // 用数组存储每个学生的成绩信息
    int len; // 线性表的实际长度
} SeqList;

// 建立学生成绩统计表
SeqList create(SeqList L, int n){
    int i, j;
    printf("输入学生的学号、姓名、计算机基础、C 语言、数据结构成绩：\n");
    for(i = 1; i <= n; i ++){
        scanf("%s", L.stu[i].no); // 录入学号
        scanf("%s", L.stu[i].name); // 录入姓名
        L.stu[i].total = 0;
        for(j = 0; j < 3; j++){
            scanf("%d", &L.stu[i].score[j]); // 录入各科目的成绩
            L.stu[i].total = L.stu[i].total + L.stu[i].score[j]; // 计算总成绩
        }
        printf("总成绩为：%d\n\n", L.stu[i].total);
    }
    return L;
}

// 直接选择排序方式将总成绩升序排序，然后逆序输出
void SelectSort(SeqList L, int n){
    int i, j, t;
    for(i = 1; i < n; i++){
        for(t = i, j = i + 1; j <= n; j++)
            if(L.stu[j].total < L.stu[t].total) t = j;
        if(t != i){
            L.stu[0] = L.stu[t];
            L.stu[t] = L.stu[i];
            L.stu[i] = L.stu[0];
        }
    }
    printf("按照总成绩进行排序后的成绩表如下：\n");
    for(i = n; i >= 1; i--){
        printf("%s %s ", L.stu[i].no, L.stu[i].name);
        for(j = 0; j < 3; j++) printf("%d ", L.stu[i].score[j]);
        printf("%d\n", L.stu[i].total);
    }
}

// 主函数
int main(){
    SeqList List;
    printf("输入学生人数：");
    scanf("%d", &List.len);
    List = create(List, List.len);
    SelectSort(List, List.len);
}

4.4 利用堆排序方法

// 利用堆排序方法排序学生成绩表
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdlib.h>
#include <stdio.h>
#define MAXSIZE 20
// 成绩表最大长度

// 定义结构体类型
typedef struct{
    char no[10]; // 学号
    char name[10]; // 姓名
    int score[3]; // 各科成绩
    int total; // 总成绩
} student;

typedef struct // 定义线性表类型
{
    student stu[MAXSIZE]; // 用数组存储每个学生的成绩信息
    int len; // 线性表的实际长度
} SeqList;

// 建立学生成绩统计表
SeqList create(SeqList L, int n){
    int i, j;
    printf("输入学生的学号、姓名、计算机基础、C 语言、数据结构成绩：\n");
    for(i = 1; i <= n; i ++){
        scanf("%s", L.stu[i].no); // 录入学号
        scanf("%s", L.stu[i].name); // 录入姓名
        L.stu[i].total = 0;
        for(j = 0; j < 3; j++){
            scanf("%d", &L.stu[i].score[j]); // 录入各科目的成绩
            L.stu[i].total = L.stu[i].total + L.stu[i].score[j]; // 计算总成绩
        }
        printf("总成绩为：%d\n\n", L.stu[i].total);
    }
    return L;
}

// 将无序的学生总成绩调整为大顶堆
void HeapAdjust(SeqList *L, int s, int m){
    int j;
    L->stu[0] = L->stu[s];
    for(j = 2*s; j <= m; j *= 2){
        if(j < m && L->stu[j].total < L->stu[j+1].total) j++;
        if( L->stu[0].total >= L->stu[j].total) break;
        else{
            L->stu[s] = L->stu[j];
            s = j;
        }
    }
    L->stu[s] = L->stu[0];
}

// 堆排序方式将总成绩升序排序，然后逆序输出
void HeapSort(SeqList *L, int n){
    int i, j;
    for(i = L->len/2; i > 0; i--) HeapAdjust(L, i, L->len);
    for(i = L->len; i > 1; i--){
        L->stu[0] = L->stu[1];
        L->stu[1] = L->stu[i];
        L->stu[i] = L->stu[0];
        HeapAdjust(L, 1, i-1);
    }
    printf("按照总成绩进行排序后的成绩表如下：\n");
    for(i = n; i > 0; i--){
        printf("%s %s ", L->stu[i].no, L->stu[i].name);
        for(j = 0; j < 3; j++) printf("%d ", L->stu[i].score[j]);
        printf("%d\n", L->stu[i].total);
    }
}

// 主函数
int main(){
    SeqList List;
    printf("输入学生人数：");
    scanf("%d", &List.len);
    List = create(List, List.len);
    HeapSort(&List, List.len);
}