C算法
数据结构：快速排序与归并排序的深入优化
快速排序与归并排序的深入优化方案包括针对大量重复数据的三路划分算法、应对递归深度过大的内省排序（Introsort）机制、处理海量数据的外排序“排序 - 归并”策略以及归并排序的非递归版本实现。通过学生成绩表案例展示了多种排序方法的应用对比，重点解决了快排在特定场景下的性能退化问题。
快速排序与归并排序的深入优化方案包括针对大量重复数据的三路划分算法、应对递归深度过大的内省排序（Introsort）机制、处理海量数据的外排序“排序 - 归并”策略以及归并排序的非递归版本实现。通过学生成绩表案例展示了多种排序方法的应用对比，重点解决了快排在特定场景下的性能退化问题。
决定快排性能的关键点是每次单趟排序后，key 对数组的分割。如果每次选 key 基本二分居中，那么快排的递归树就是颗均匀的满二叉树，性能最佳。但是实践中虽然不可能每次都是二分居中，但是性能也还是可控的。但是如果出现每次选到最小值/最大值，划分为 0 个和 N-1 的子问题时，时间复杂度为 O(N^2)，数组序列有序时就会出现这样的问题。我们前面已经用三数取中或者随机选 key 解决了这个问题，也就是说我们解决了绝大多数的问题，但是现在还有一些场景没解决（数组中有大量重复数据时），类似以下代码。
// 数组中有多个跟 key 相等的值
int a[] = { 6, 1, 7, 6, 6, 6, 4, 9 };
int a[] = { 3, 2, 3, 3, 3, 3, 2, 3 };
// 数组中全是相同的值
int a[] = { 2, 2, 2, 2, 2, 2, 2, 2 };
当面对有大量跟 key 相同的值时，三路划分的核心思想有点类似 hoare 的左右指针和 lomuto 的前后指针的结合。核心思想是把数组中的数据分为三段【比 key 小的值】【跟 key 相等的值】【比 key 大的值】，所以叫做三路划分算法。结合下图，理解一下实现思想：
数组中有大量重复数据时，快排单趟选 key 划分效果对象:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
void PrintArray(int* a, int n){
for(int i = 0; i < n; ++i){
printf("%d ", a[i]);
}
printf("\n");
}
void Swap(int* p1, int* p2){
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
// hoare
// [left, right]
int PartSort1(int* a, int left, int right){
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++; }
// right left
if(left <= right){ Swap(&a[left++], &a[right--]); }
}
// right keyi 交换
Swap(&a[keyi], &a[right]);
return right;
}
// 前后指针
int PartSort2(int* a, int left, int right){
int prev = left;
int cur = left + 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;
return keyi;
}
typedef struct{
int leftKeyi;
int rightKeyi;
} KeyWayIndex;
// 三路划分
KeyWayIndex PartSort3Way(int* a, int left, int right){
int key = a[left];
// left 和 right 指向就是跟 key 相等的区间
// [开始，left-1][left, right][right+1, 结束]
int cur = left + 1;
while(cur <= right){
// 1、cur 遇到比 key 小，小的换到左边，同时把 key 换到中间位置
// 2、cur 遇到比 key 大，大的换到右边
if(a[cur] < key){
Swap(&a[cur], &a[left]);
++cur;
++left;
} else if(a[cur] > key){
Swap(&a[cur], &a[right]);
--right;
} else {
++cur;
}
}
KeyWayIndex kwi;
kwi.leftKeyi = left;
kwi.rightKeyi = right;
return kwi;
}
void TestPartSort1(){
int a1[] = {6, 1, 7, 6, 6, 6, 4, 9};
int a2[] = {3, 2, 3, 3, 3, 3, 2, 3};
int a3[] = {2, 2, 2, 2, 2, 2, 2, 2};
PrintArray(a1, sizeof(a1)/sizeof(int));
int keyi1 = PartSort1(a1, 0, sizeof(a1)/sizeof(int)-1);
PrintArray(a1, sizeof(a1)/sizeof(int));
printf("hoare keyi:%d\n\n", keyi1);
PrintArray(a2, sizeof(a2)/sizeof(int));
int keyi2 = PartSort1(a2, 0, sizeof(a2)/sizeof(int)-1);
PrintArray(a2, sizeof(a2)/sizeof(int));
printf("hoare keyi:%d\n\n", keyi2);
PrintArray(a3, sizeof(a3)/sizeof(int));
int keyi3 = PartSort1(a3, 0, sizeof(a3)/sizeof(int)-1);
PrintArray(a3, sizeof(a3)/sizeof(int));
printf("hoare keyi:%d\n\n", keyi3);
}
void TestPartSort2(){
int a1[] = {6, 1, 7, 6, 6, 6, 4, 9};
int a2[] = {3, 2, 3, 3, 3, 3, 2, 3};
int a3[] = {2, 2, 2, 2, 2, 2, 2, 2};
PrintArray(a1, sizeof(a1)/sizeof(int));
int keyi1 = PartSort2(a1, 0, sizeof(a1)/sizeof(int)-1);
PrintArray(a1, sizeof(a1)/sizeof(int));
printf("前后指针 keyi:%d\n\n", keyi1);
PrintArray(a2, sizeof(a2)/sizeof(int));
int keyi2 = PartSort2(a2, 0, sizeof(a2)/sizeof(int)-1);
PrintArray(a2, sizeof(a2)/sizeof(int));
printf("前后指针 keyi:%d\n\n", keyi2);
PrintArray(a3, sizeof(a3)/sizeof(int));
int keyi3 = PartSort2(a3, 0, sizeof(a3)/sizeof(int)-1);
PrintArray(a3, sizeof(a3)/sizeof(int));
printf("前后指针 keyi:%d\n\n", keyi3);
}
void TestPartSort3(){
int a1[] = {6, 1, 7, 6, 6, 6, 4, 9};
int a2[] = {3, 2, 3, 3, 3, 3, 2, 3};
int a3[] = {2, 2, 2, 2, 2, 2, 2, 2};
PrintArray(a1, sizeof(a1)/sizeof(int));
KeyWayIndex kwi1 = PartSort3Way(a1, 0, sizeof(a1)/sizeof(int)-1);
PrintArray(a1, sizeof(a1)/sizeof(int));
printf("3Way keyi:%d,%d\n\n", kwi1.leftKeyi, kwi1.rightKeyi);
PrintArray(a2, sizeof(a2)/sizeof(int));
KeyWayIndex kwi2 = PartSort3Way(a2, 0, sizeof(a2)/sizeof(int)-1);
PrintArray(a2, sizeof(a2)/sizeof(int));
printf("3Way keyi:%d,%d\n\n", kwi2.leftKeyi, kwi2.rightKeyi);
PrintArray(a3, sizeof(a3)/sizeof(int));
KeyWayIndex kwi3 = PartSort3Way(a3, 0, sizeof(a3)/sizeof(int)-1);
PrintArray(a3, sizeof(a3)/sizeof(int));
printf("3Way keyi:%d,%d\n\n", kwi3.leftKeyi, kwi3.rightKeyi);
}
int main(){
TestPartSort1();
TestPartSort2();
TestPartSort3();
return 0;
}
从下面的运行结果分析，lomuto 的前后指针法，面对 key 有大量重复时，lomuto 划分不是很理想，性能退化，hoare 相对还不错，但是大量重复时，没有三路划分快。三路划分算法，把跟 key 相等的值都划分到了中间，可以很好的解决这里的问题。
下面我们来看看这个 OJ 题，这个 OJ，当我们用快排的时候，lomuto 的方法，过不了这个题目，hoare 版本可以过这个题目。堆排序和归并和希尔是可以过的，其他几个 O(N^2) 也不过了，因为这个题的测试用例中不仅仅有数据很多的大数组，也有一些特殊数据的数组，如大量重复数据的数组。堆排序和归并和希尔不是很受数据样本的分布和形态的影响，但是快排会，因为快排要选 key，每次 key 都当趟分割都很偏，就会出现效率退化问题。
• 前面我们分析了 lomuto 的前后指针面对大量重复数据时，效率会退化，hoare 版本会好很多，所以 hoare 是可以过这个 OJ 的，但是 OJ 还是一个相对局限的测试，就像 leetcode 官方为啥开始写的答案是 lomuto，说明那会 lomuto 是可以过的，后面加了大量重复数值的测试用例，所以就过不了，但是答案忘记改了，说明写答案讲解和测试用例补充的不是一个团队，协作出问题。那么 hoare 现在可以过，leetcode 哪天增加一个特殊测试用例以后，就过不了，三路划分也类似，因为他们的思想还是在特殊场景下效率会退化，比如大多数选 key 都是接近最小或者最大的值，导致划分不均衡，效率退化。
下面我分别展示一下这几种思想去跑排序数组 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;
}
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;
}
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;
}
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;
}
外排序 (External sorting) 是指能够处理极大量数据的排序算法。通常来说，外排序处理的数据不能一次装入内存，只能放在读写较慢的外存储器 (通常是硬盘) 上。外排序通常采用的是一个'排序 - 归并'的策略。在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。然后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果。跟外排序对应的就是内排序，我们之前讲的常见的排序，都是内排序，他们排序思想适应的是数据在内存中，支持随机访问。归并排序的思想不需要随机访问数据，只需要依次按序列读取数据，所以归并排序既是一个内排序，也是一个外排序。
// 创建 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);
}
#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;
}
// 归并排序 - 非递归版本
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;
}
}
题目要求：创建一个线性表用来存储学生成绩，每个学生的成绩信息作为一个数据元素，对应表中的一行。定义线性表的结构体类型，成绩表的数据项包括：学号、姓名、计算机基础、C 语言、数据结构成绩。首先输入学生人数确定要建立的线性表的长度，录入每个学生的成绩信息，并计算出其总成绩；然后，以总成绩为关键字进行直接插入排序；最后，逆序显示排序后的成绩表。
// 利用直接插入排序方法排序学生成绩表
#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);
}
// 利用冒泡排序方法排序学生成绩表
#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);
}
// 利用直接选择排序方法排序学生成绩表
#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);
}
// 利用堆排序方法排序学生成绩表
#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);
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online