一文彻底搞清楚数据结构之快速排序和归并排序的深入优化
🔥承渊政道：个人主页
❄️个人专栏: 《C语言基础语法知识》《数据结构与算法初阶》
✨逆境不吐心中苦,顺境不忘来时路!🎬 博主简介:
前言:前面小编已经介绍八大排序算法的基本思想和实现方法!但关于其中的快速排序和归并排序还有一些细节可以优化!接下来跟着小编来看看快速排序和归并排序的深入优化,学习一下优化完之后,具体在实际中的应用!废话不多说,下面跟着小编的节奏🎵一起学习吧！
目录
1.快速排序性能的关键点分析
决定快排性能的关键点是每次单趟排序后,key对数组的分割,如果每次选key基本⼆分居中,那么快排的递归树就是颗均匀的满⼆叉树,性能最佳.但是实践中虽然不可能每次都是⼆分居中,但是性能也还是可控的.但是如果出现每次选到最⼩值/最⼤值,划分为0个和N-1的⼦问题时,时间复杂度为O(N2),数组序列有序时就会出现这样的问题,我们前⾯已经⽤三数取中或者随机选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 };
1.1三路划分算法思想讲解
当⾯对有⼤量跟key相同的值时,三路划分的核⼼思想有点类似hoare的左右指针和lomuto的前后指针的结合.核⼼思想是把数组中的数据分为三段【⽐key⼩的值】【跟key相等的值】【⽐key⼤的值】,所以叫做三路划分算法.结合下图,理解⼀下实现思想：
1️⃣key默认取left位置的值.
2️⃣left指向区间最左边,right指向区间最后边,cur指向left+1位置.
3️⃣cur遇到⽐key⼩的值后跟left位置交换,换到左边,left++,cur++.
4️⃣cur遇到⽐key⼤的值后跟right位置交换,换到右边,right–.
5️⃣cur遇到跟key相等的值后,cur++.
6️⃣直到cur>right结束.
1.2hoare和lomuto和三路划分单趟排序代码分析
数组中有⼤量重复数据时,快排单趟选key划分效果对象:
#include<stdio.h>#include<stdlib.h>#include<time.h>#include<string.h>voidPrintArray(int* a,int n){for(int i =0; i < n;++i){printf("%d ", a[i]);}printf("\n");}voidSwap(int* p1,int* p2){int tmp =*p1;*p1 =*p2;*p2 = tmp;}// hoare// [left, right]intPartSort1(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 leftif(left <= right){Swap(&a[left++],&a[right--]);}}//right keyi交换Swap(&a[keyi],&a[right]);return right;}// 前后指针intPartSort2(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;}typedefstruct{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;}elseif(a[cur]> key){Swap(&a[cur],&a[right]);--right;}else{++cur;}} KeyWayIndex kwi; kwi.leftKeyi = left; kwi.rightKeyi = right;return kwi;}voidTestPartSort1(){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);}voidTestPartSort2(){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);}voidTestPartSort3(){//int a0[] = { 6,1,2,7,9,3,4,5,10,4 };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);}intmain(){TestPartSort1();TestPartSort2();TestPartSort3();return0;}1.3三种快排单趟排序运⾏结果分析
从下⾯的运⾏结果分析,lomuto的前后指针法,⾯对key有⼤量重复时,lomuto划分不是很理想,性能退化,hoare相对还不错,但是⼤量重复时,没有三路划分快.三路划分算法,把跟key相等的值都划分到了中间,可以很好的解决这⾥的问题.
2.排序数组OJ题
排序数组
下⾯我们来看看这个OJ题,这个OJ,当我们⽤快排的时候,lomuto的⽅法,过不了这个题⽬,hoare版本可以过这个题⽬.堆排序和归并和希尔是可以过的,其他⼏个O(N2)也不过了,因为这个题的测试⽤例中不仅仅有数据很多的⼤数组,也有⼀些特殊数据的数组,如⼤量重复数据的数组.堆排序和归并和希尔不是很受数据样本的分布和形态的影响,但是快排会,因为快排要选key,每次key都当趟分割都很偏,就会出现效率退化问题.
•前⾯我们分析了lomuto的前后指针⾯对⼤量重复数据时,效率会退化,hoare版本会好很多,所以
hoare是可以过这个OJ的,但是OJ还是⼀个相对局限的测试,就像leetcode官⽅为啥开始写的答案
是lomuto,说明那会lomuto是可以过的,后⾯加了⼤量重复数值的测试⽤例,所以就过不了,但是答案忘记改了,说明写答案讲解和测试⽤例补充的不是⼀个团队,协作出问题.那么hoare现在可以过,leetcode哪天增加⼀个特殊测试⽤例以后,就过不了,三路划分也类似,因为他们的思想还是在特殊场景下效率会退化,⽐如⼤多数选key都是接近最⼩或者最⼤的值,导致划分不均衡,效率退化.
1️⃣introsort是由DavidMusser在1997年设计的排序算法,C++ sgi STL sort中就是⽤的introspective
sort(内省排序)思想实现的.内省排序可以认为不受数据分布的影响,⽆论什么原因划分不均匀,导致递归深度太深,他就是转换堆排了,堆排不受数据分布影响,具体看下⾯代码.
2️⃣其次三路划分针对有⼤量重复数据时,效率很好,其他场景就⼀般,但是三路划分思路还是很有价值的,有些快排思想变形体,要⽤划分去选数,他能保证跟key相等的数都排到中间去,三路划分的价值就体现出来了.
下⾯我分别展⽰⼀下这⼏种思想去跑排序数组oj的思路和代码.
2.1lomuto的快速排序跑排序数组OJ题
voidSwap(int* x,int* y){int tmp =*x;*x =*y;*y = tmp;}voidQuickSort(int* a,int left,int right){if(left >= right)return;int begin = left;int end = right;// 随机选keyint 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.2hoare的快速排序跑排序数组OJ题
voidSwap(int* x,int* y){int tmp =*x;*x =*y;*y = tmp;}voidQuickSort(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题
voidSwap(int* x,int* y){int tmp =*x;*x =*y;*y = tmp;}voidQuickSort(int* a,int left,int right){if(left >= right)return;int begin = left;int end = right;// 随机选keyint 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;}elseif(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.4introsort的快速排序跑排序数组OJ题
introsort是introspective sort采⽤了缩写,他的名字其实表达了他的实现思路,他的思路就是进⾏⾃
我侦测和反省,快排递归深度太深(sgi stl中使⽤的是深度为2倍排序元素数量的对数值)那就说明在这种数据序列下,选key出现了问题,性能在快速退化,那么就不要再进⾏快排分割递归了,改换为堆排序进⾏排序.
voidSwap(int* x,int* y){int tmp =*x;*x =*y;*y = tmp;}voidAdjustDown(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;}}}voidHeapSort(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;}}voidInsertSort(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;}}voidIntroSort(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;// 随机选keyint 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);}voidQuickSort(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个随机数，写到⽂件中voidCreateNDate(){// 造数据int n =1000000;srand(time(0));constchar* 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_WARNINGS1#include<stdio.h>#include<time.h>#include<stdlib.h>// 创建N个随机数，写到文件中voidCreateNDate(){// 造数据int n =10000000;srand(time(0));constchar* 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);}intcompare(constvoid* a,constvoid* b){return(*(int*)a -*(int*)b);}// 返回实际读到的数据个数，没有数据了，返回0intReadNDataSortToFile(FILE* fout,int n,constchar* file1){int x =0;int* a =(int*)malloc(sizeof(int)* n);if(a ==NULL){perror("malloc error");return0;}// 想读取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);return0;}// 排序qsort(a, j,sizeof(int), compare); FILE* fin =fopen(file1,"w");if(fin ==NULL){free(a);perror("fopen error");return0;}// 写回file1文件for(int i =0; i < j; i++){fprintf(fin,"%d\n", a[i]);}free(a);fclose(fin);return j;}voidMergeFile(constchar* file1,constchar* file2,constchar* 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);}intmain(){CreateNDate();constchar* file1 ="file1.txt";constchar* file2 ="file2.txt";constchar* 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和file2remove(file1);remove(file2);// 重命名mfile为file1rename(mfile, file1);// 当再去读取数据，一个都读不到，说明已经没有数据了// 已经归并完成，归并结果在file1int n =0;if((n =ReadNDataSortToFile(fout, m, file2))==0)break;}return0;}3.4非递归版本的归并排序
//归并排序-非递归版本voidMergeSortNonR(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#include<stdlib.h>#include<stdio.h>#defineMAXSIZE20//成绩表最大长度//定义结构体类型typedefstruct{char no[10];//学号char name[10];//姓名int score[3];//各科成绩int total;//总成绩}student;typedefstruct//定义线性表类型{ 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;}//利用直接插入排序方式将总成绩升序排序，然后逆序输出voidInsertsort(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);}}//主函数voidmain(){ SeqList List;printf("输入学生人数：");scanf("%d",&List.len); List =create(List, List.len);Insertsort(List, List.len);}
运行结果:
4.2利用冒泡排序方法
//利用冒泡排序方法排序学生成绩表#define_CRT_SECURE_NO_WARNINGS#include<stdlib.h>#include<stdio.h>#defineMAXSIZE20//成绩表最大长度//定义结构体类型typedefstruct{char no[10];//学号char name[10];//姓名int score[3];//各科成绩int total;//总成绩}student;typedefstruct//定义线性表类型{ 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;}//冒泡排序方式将总成绩升序排序，然后逆序输出voidBubbleSort(SeqList L,int n){int i,j,flag =1;for(i =1; i <= n; i++){ flag=0;//交换标志初始值为0for(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);}}//主函数voidmain(){ SeqList List;printf("输入学生人数：");scanf("%d",&List.len); List =create(List, List.len);BubbleSort(List, List.len);}
运行结果:
4.3利用直接选择排序方法
//利用直接选择排序方法排序学生成绩表#define_CRT_SECURE_NO_WARNINGS#include<stdlib.h>#include<stdio.h>#defineMAXSIZE20//成绩表最大长度//定义结构体类型typedefstruct{char no[10];//学号char name[10];//姓名int score[3];//各科成绩int total;//总成绩}student;typedefstruct//定义线性表类型{ 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;}//直接选择排序方式将总成绩升序排序，然后逆序输出voidSelectSort(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);}}//主函数voidmain(){ SeqList List;printf("输入学生人数：");scanf("%d",&List.len); List =create(List, List.len);SelectSort(List, List.len);}
运行结果:
4.4利用堆排序方法
//利用堆排序方法排序学生成绩表#define_CRT_SECURE_NO_WARNINGS#include<stdlib.h>#include<stdio.h>#defineMAXSIZE20//成绩表最大长度//定义结构体类型typedefstruct{char no[10];//学号char name[10];//姓名int score[3];//各科成绩int total;//总成绩}student;typedefstruct//定义线性表类型{ 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;}//将无序的学生总成绩调整为大顶堆voidHeapAdjust(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];}//堆排序方式将总成绩升序排序，然后逆序输出voidHeapSort(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);}}//主函数voidmain(){ SeqList List;printf("输入学生人数：");scanf("%d",&List.len); List =create(List, List.len);HeapSort(&List, List.len);}
运行结果:
敬请期待下一篇文章内容!
