一文彻底搞清楚数据结构之快速排序和归并排序的深入优化

承渊政道

发布于 2025-12-18 17:26:51

2290

�

前言:前面小编已经介绍八大排序算法的基本思想和实现方法!但关于其中的快速排序和归并排序还有一些细节可以优化!接下来跟着小编来看看快速排序和归并排序的深入优化,学习一下优化完之后,具体在实际中的应用!废话不多说,下面跟着小编的节奏🎵一起学习吧！

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>
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 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);
}
int main()
{
 TestPartSort1();
 TestPartSort2();
 TestPartSort3();
 return 0;
}

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题

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.2hoare的快速排序跑排序数组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.4introsort的快速排序跑排序数组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
#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);
        }
    }
    //主函数
void main ()
{
    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>
#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);
    }
}
//主函数
void main ()
{
    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>
#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);
    }
}
//主函数
void main ()
{
    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>
#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);
    }
}
//主函数
void main()
{
    SeqList List;
    printf("输入学生人数：");
    scanf("%d", &List.len);
    List = create(List, List.len);
    HeapSort(&List, List.len);
}