【820复试】数据结构面试问题

文章目录

1.用循环比递归的效率高吗

循环和递归两者是可以互换的，无法陈述谁效率高。

递归
优点：代码简洁清晰，容易检查正确性；
缺点：递归调用次数较多时，要增加额外的堆栈处理，有可能产生堆栈溢出的情况，会对执行效率有一定的影响。

循环
优点：结构检点，速度快；
缺点：不能解决全部问题，有些问题适合于用递归来解决不适合用循环解决。

2.顺序表和链表的比较

从 存取方式、 逻辑结构和物理结构、 查找插入和删除操作、空间分配四个方面分别做比较即可。

3.头指针和头结点的区别

头指针：是指向第一个结点存储位置的指针，具有表示作用，头指针是链表的必要元素，无论链表是否为空，头指针都存在。

头结点：是放在第一个元素结点之前，便于在第一个元素结点之前进行插入和删除的操作，头结点不是链表的必须元素，可有可无，头结点的数据域也可以不存储任何信息。

4.如何区分循环队列是队满还是队空？

①牺牲一个单元来区分队满和队空。
队空就是Q.front == Q.rear
队满就是(Q.rear+1)%Maxsize == Q.front

②增设数据成员元素
队空Q.size0
队满Q.sizeMaxsize

③标记上一次是入队还是出队
若是入队flag=1，此时出现Q.frontQ.rear，那么即为队满
若是出队flag=0，此时出现Q.frontQ.rear，那么即为队空

5.栈在通过后缀表达式求值的算法思想

但凡出现左括号，做入栈操作，否则做以下操作：
是否为空？与栈顶元素是否匹配？

表达式检验结束后，还要检查栈中是否还有元素。

6.栈在递归中的应用

在递归函数中，每次函数调用都会创建一个新的函数调用帧（frame），这个帧包含了函数的局部变量、参数值以及函数返回地址等信息。
当函数调用自身（递归调用）时，每次都会创建一个新的函数调用帧。这些函数调用帧被存储在内存中的栈数据结构中，这就是所谓的调用栈（call stack）。

当递归函数开始执行时，会一直递归调用自身，每次递归调用都会将一个新的函数调用帧压入调用栈中。
当递归条件不再满足，函数开始返回时，会从栈顶依次弹出函数调用帧，并执行相应的返回操作，直到栈为空，整个递归过程结束。

7.队列在层次遍历中的作用

遇到某类信息需要逐层/逐行处理时，往往是在处理当前层或当前行时就对下一层或下一行做预处理，把处理顺序安排好，待当前层或当前行处理完毕，就可以处理下一层或下一行。

二叉树的层序遍历、广度优先搜索、任务调度、消息队列、缓冲池、批处理系统。

8.队列在计算机系统中的应用
  1. 任务调度和作业管理： 操作系统使用队列来管理和调度各种任务和作业。例如，多任务操作系统可以使用队列来安排进程的执行顺序，确保按照优先级和其他调度策略执行任务。
  2. I/O请求管理： 计算机系统中的I/O设备通常会产生大量的请求，如磁盘I/O请求、网络数据包等。队列被广泛应用于管理这些请求，以便按照请求到达的顺序来处理它们。
  3. 消息传递和事件处理： 在事件驱动的系统中，队列用于管理事件和消息的处理顺序。例如，图形用户界面（GUI）应用程序可以使用队列来处理用户输入事件、定时器事件等。
  4. 网络数据包排队： 在网络系统中，路由器和交换机使用队列来缓冲传入和传出的数据包。这些队列可以帮助调节网络流量，并确保数据包按照一定的优先级和服务质量要求被处理。
  5. 缓存系统： 队列常被用于实现缓存系统，例如最近最少使用（LRU）缓存算法。在缓存满时，新的数据项可以被放入队列，而最久未使用的数据项可以从队列的头部被移除。
  6. 并发编程： 在多线程和并发编程中，队列常被用于实现线程间的通信和同步。例如，生产者-消费者模型中，一个线程（生产者）向队列中放入数据，而另一个线程（消费者）则从队列中取出数据进行处理。
  7. 日志和消息处理系统： 队列可用于实现日志和消息处理系统，用于收集、存储和处理系统产生的日志和消息。通过将日志和消息放入队列中，可以实现异步处理和解耦。
  8. 批处理系统： 在数据处理领域，队列被广泛用于构建批处理系统。数据处理任务可以被放入队列中，然后由后台任务逐个处理，从而提高处理效率。
9.矩阵的压缩存储

矩阵的压缩存储是一种优化存储矩阵的方法，特别是当矩阵中有大量的重复值或者是稀疏矩阵（大部分元素为零）时。
它的主要目的是减少内存占用，提高存储和处理效率。

行压缩存储、列压缩存储、对角线压缩存储、十字链表法。

10.串的模式匹配

朴素算法（Naive Algorithm）：
也称为暴力匹配算法，它是最简单直观的模式匹配算法。它的思路是在文本串中从头到尾逐个字符地与模式串进行比较，直到找到匹配或者遍历完整个文本串。
朴素算法的时间复杂度为 O(m*n)，其中 m 是模式串的长度，n 是文本串的长度。

// 朴素算法函数
int naiveSearch(char *text, char *pattern) {
    int textLength = strlen(text);
    int patternLength = strlen(pattern);
    
    for (int i = 0; i <= textLength - patternLength; ++i) {
        int j;
        // 检查文本串中从第 i 个位置开始的子串是否与模式串匹配
        for (j = 0; j < patternLength; ++j) {
            if (text[i + j] != pattern[j])
                break;  // 如果当前字符不匹配，则跳出内循环
        }
        // 如果内循环完全匹配了模式串，则返回匹配位置
        if (j == patternLength)
            return i;
    }
    return -1;  // 没有找到匹配的子串，返回 -1
}

Knuth-Morris-Pratt 算法（KMP Algorithm）：
KMP 算法是一种高效的模式匹配算法，它利用了模式串中已经匹配的信息来避免不必要的比较。
通过构建部分**匹配表（Partial Match Table）**来记录模式串中的前缀和后缀的最长公共部分，KMP 算法能够在 O(n+m) 的时间复杂度内完成匹配，其中 n 是文本串的长度，m 是模式串的长度。

// 构建部分匹配表
void buildPartialMatchTable(char *pattern, int *table) {
    int patternLength = strlen(pattern);
    table[0] = 0;  // 首字符的部分匹配值总是 0
    int length = 0; // 用于记录当前匹配的长度
    for (int i = 1; i < patternLength; ++i) {
        // 如果当前字符和当前匹配长度处的字符相同，匹配长度加1
        if (pattern[i] == pattern[length]) {
            ++length;
            table[i] = length;
        } else {
    // 如果当前字符和当前匹配长度处的字符不同，根据部分匹配表更新当前匹配长度
            if (length != 0) {
                length = table[length - 1];
                --i; // 回退一步重新尝试匹配
            } else   table[i] = 0;
        }
    }
}
// KMP算法函数
int KMP(char *text, char *pattern) {
    int textLength = strlen(text);
    int patternLength = strlen(pattern);
    int *table = (int*)malloc(patternLength * sizeof(int));
    buildPartialMatchTable(pattern, table);
    int i = 0, j = 0;  // i用于遍历文本串，j用于遍历模式串
    while (i < textLength) {
        if (text[i] == pattern[j]) {
            ++i;
            ++j;
        }
        if (j == patternLength) {
            free(table);
            return i - j; // 匹配成功，返回匹配位置的起始索引
        } else if (i < textLength && text[i] != pattern[j]) {
            if (j != 0)
                j = table[j - 1];  // 根据部分匹配表更新模式串的起始位置
            else
                ++i;
        }
    }
    free(table);
    return -1;  // 未找到匹配，返回 -1
}

调用KMP(text,pattern); //text文本串，pattern模式串
11.如何由遍历序列构造一棵二叉树

先序+中序

后序+中序

层序+中序

12.线索二叉树的概念

对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次
序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。

注意：线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，解决了二叉链表找左、右孩子困难的问题。

13.树的4种存储方式

①双亲表示法：这种存储方式采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示
其双亲结点在数组中的位置。结构体为【[data]，[parent]】。

struct TreeNode {
    int data;
    int parent;  // 父节点的索引
};
void addChild(int parentIndex, int childData) {
    int childIndex = -1;
    // 查找一个空闲的位置存储新的子节点
    for (int i = 0; i < MAX_NODES; ++i) {
        if (tree[i].parent == -1) {
            childIndex = i;
            break;
        }
    }
    if (childIndex != -1) {
        tree[childIndex].data = childData;
        tree[childIndex].parent = parentIndex;
    } else {
        printf("No space to add child.\n");
    }
}

该存储结构利用了每个结点（根结点除外）只有唯一双亲的性质，可以很快得到每个结点的
双亲结点，但求结点的孩子时需要遍历整个结构。

②孩子表示法：将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n 个结点
就有n 个孩子链表（叶子结点的孩子链表为空表），这种存储方式寻找子女的操作非常直接，而
寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。

// 定义树节点结构
struct TreeNode {
    int data;
    struct TreeNode *firstChild;  // 指向第一个孩子节点
    struct TreeNode *nextSibling; // 指向右兄弟节点
};
//链式结构

③孩子兄弟表示法：二叉树表示法，使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针，及指向结点下一个兄弟结点的指针（沿此域可以找到结点的所有兄弟结点）。

// 定义树节点结构
struct TreeNode {
    int data;
    struct TreeNode *firstChild;  // 指向第一个孩子节点
    struct TreeNode *nextSibling;  // 指向右兄弟节点
};
//结构相同，但是写法不同

④左右孩子表示法：用于二叉树，每个结点包括三部分内容：结点值、指向结点左孩子结点的指针，及指向结点右孩子结点的指针。

// 定义树节点结构
struct TreeNode {
    int data;
    struct TreeNode *LeftChild;  // 指向结点左孩子节点
    struct TreeNode *RightChild;  // 指向结点右孩子节点
};
14.平衡二叉树

为避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除二叉树结点时，要保证任
意结点的左、右子树高度差的绝对值不超过1, 将这样的二叉树称为平衡二叉树(Balanced Binary
Tree), 简称平衡树。
定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点
的平衡因子的值只可能是-1 、0 或1 。

15.dijkstra算法

一种用于计算图中单源最短路径的贪心算法。Dijkstra 算法基于贪心策略，每次选择当前距离起点最近的节点作为下一个中间节点，并更新与该节点相邻的节点的最短路径。

基本步骤：
1.初始化距离数组 dist 和标记数组 visited，用于记录每个节点到起点的最短距离和节点是否已经访问过。
2.将起点的最短距离设为0，并标记起点为已访问。
3.对于起点相邻的所有节点，更新它们的最短距离为起点到它们的距离，并标记它们为已访问。
4.重复以下步骤，直到所有节点都被访问过：
a. 从未访问的节点中选择距离起点最近的节点。
b. 对于选中的节点，更新其相邻节点的最短距离为起点到该节点的距离加上选中节点的最短距离。
c. 将选中的节点标记为已访问。
5.当所有节点都被访问过后，距离数组 dist 中存储的即为起点到每个节点的最短距离。

// 计算未访问节点中距离起点最近的节点的索引
int minDistance(int dist[], bool visited[]) {
    int min = INF, min_index;

    for (int v = 0; v < V; v++) {
        if (visited[v] == false && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }

    return min_index;
}
// 使用 Dijkstra 算法计算单源最短路径
void dijkstra(int graph[V][V], int src) {
    int dist[V];     // 存储从源到每个顶点的最短距离
    bool visited[V]; // 记录每个顶点是否已被访问

    // 初始化所有距离为无穷大，所有节点均未被访问
    for (int i = 0; i < V; i++) {  
        dist[i] = INF;
        visited[i] = false;
    }  //可以用memset(dist, INF, sizeof(dist));替换

    dist[src] = 0;  // 源节点到自身的距离为0

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, visited); // 选取未访问节点中距离最近的节点
        visited[u] = true; // 标记该节点为已访问

        // 更新相邻节点的最短距离
        for (int v = 0; v < V; v++) {
            if (!visited[v] && graph[u][v] && dist[u] != INF && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
        }
    }

    printSolution(dist);
}

// 打印最短路径
void printSolution(int dist[]) {
    printf("Vertex \t Distance from Source\n");
    for (int i = 0; i < V; i++)
        printf("%d \t %d\n", i, dist[i]);
}
16.Floyd算法

一种用于求解所有节点对之间最短路径的动态规划算法。它可以处理带权重的有向图或无向图，即使存在负权边或负权环，也能正确计算出最短路径。

void floyd(int graph[][MAX_NODES], int n) {
    int i, j, k;
    // 逐步考察每一个中间节点
    for (k = 0; k < n; k++) {  //枚举每一个中间结点
        // 以结点 i 为起点
        for (i = 0; i < n; i++) {
            // 以结点 j 为终点
            for (j = 0; j < n; j++) {
                // 如果从结点i经过结点k再到结点j的路径更短，则更新最短路径
                if (graph[i][k] + graph[k][j] < graph[i][j]) {
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
}
17.Prim算法

一种用于求解最小生成树的贪心算法。最小生成树是一棵包含图中所有节点且边权重之和最小的树。Prim算法从一个初始节点开始，逐步选取与当前生成树相连的权重最小的边，直到所有节点都被加入到生成树中为止。

Prim算法的基本思想：
1.选择一个初始节点作为生成树的根节点，并将其加入生成树中。
2.在生成树与剩余节点之间的边中选择权重最小的边，并将其加入生成树。
3.重复步骤2，直到所有节点都被加入到生成树中。

void prim(int start) {
    bool visited[MAX_NODES] = {false};  // 记录已加入生成树的节点
    visited[start] = true;
    int MST[MAX_NODES][2];  // 最小生成树的边集合
    int edgeCount = 0;
    while (edgeCount < n - 1) {
        int minEdge = INF;
        int minNode = -1;
        for (int node = 0; node < n; node++) {
            if (visited[node]) {
                for (int neighbor = 0; neighbor < n; neighbor++) {
                    if (!visited[neighbor] && graph[node][neighbor] < minEdge) {
                        minEdge = graph[node][neighbor];
                        minNode = neighbor;
                    }
                }
            }
        }
        if (minNode != -1) {
            MST[edgeCount][0] = minNode;
            MST[edgeCount][1] = minEdge;
            edgeCount++;
            visited[minNode] = true;
        }
    }

    // 输出最小生成树的边集合
    printf("Minimum Spanning Tree edges:\n");
    for (int i = 0; i < n - 1; i++) {
        printf("%d - %d\n", start, MST[i][0]);
    }
}
18.Kraskal算法

一种用于求解最小生成树（Minimum Spanning Tree，MST）的贪心算法。其基本思想是从图中所有边中选择权重最小的边，然后逐步添加边，直到所有的顶点都被连接为止。在添加边的过程中，要确保不形成环路，因为最小生成树是一个树，不应该包含环路。

以下是Kruskal算法的基本步骤：
1.将图中的所有边按照权重进行排序。
2.初始化一个空的最小生成树。
3.依次遍历排好序的边，每次选择一条边，判断加入后是否形成环路。若不形成环路，则将该边加入最小生成树。
4.重复步骤3，直到最小生成树中包含了所有的顶点。

// Kruskal算法
void KruskalMST(struct Graph* graph) {
    int V = graph->V;
    struct Edge result[V];  // 存储最小生成树的边
    int e = 0;  // 用于result数组的索引
    int i = 0;  // 用于遍历graph->edge数组
    int parent[V]; // 用于记录顶点的父节点
    // 初始化parent数组
    for (int v = 0; v < V; v++) parent[v] = -1;
    // 将图的所有边按照权重进行排序
    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), [](const void* a, const void* b) {
        struct Edge* a1 = (struct Edge*)a;
        struct Edge* b1 = (struct Edge*)b;
        return a1->weight > b1->weight;
    });
    // 遍历排序后的边数组，构建最小生成树
    while (e < V - 1 && i < graph->E) {
        struct Edge next_edge = graph->edge[i++];
        int x = find(parent, next_edge.src);
        int y = find(parent, next_edge.dest);
        // 如果不形成环路，则加入最小生成树
        if (x != y) {
            result[e++] = next_edge;
            Union(parent, x, y);
        }
    }
    // 输出最小生成树的边
    printf("Edges in the minimum spanning tree:\n");
    int minimumCost = 0;
    for (i = 0; i < e; ++i) {
        printf("%d - %d: %d\n", result[i].src, result[i].dest, result[i].weight);
        minimumCost += result[i].weight;
    }
    printf("Minimum cost of MST: %d\n", minimumCost);
}
19.拓扑排序

一种对有向无环图（DAG）进行排序的算法，它使得图中的所有顶点按照一定的顺序排列，使得所有的有向边从前面的顶点指向后面的顶点。如果图中存在环路，则无法进行拓扑排序。

拓扑排序的基本思想：
不断地从图中选择入度为0的顶点，并删除以该顶点为起点的边，直到图中所有的顶点都被选择完毕为止。如果图中有顶点无法被选择，则说明图中存在环路，无法进行拓扑排序。

拓扑排序的算法步骤：
1.初始化一个队列，并将所有入度为0的顶点加入队列。
2.不断地从队列中取出顶点，并将该顶点输出到拓扑排序结果中。
3.对于每个被取出的顶点，遍历其所有邻接顶点，将这些邻接顶点的入度减1。若某个邻接顶点的入度减为0，则将其加入队列。
4.重复步骤2和步骤3，直到队列为空。

// 拓扑排序算法
void topologicalSort(struct Graph* graph) {
    int V = graph->V;
    int* indegree = graph->indegree;
    // 初始化一个队列
    int queue[MAX_VERTICES];
    int front = 0, rear = -1;
    // 将入度为0的顶点加入队列
    for (int i = 0; i < V; i++) {
        if (indegree[i] == 0) {
            queue[++rear] = i;
        }
    }
    // 记录拓扑排序结果
    int count = 0;
    int* topologicalOrder = (int*)malloc(V * sizeof(int));
    while (front <= rear) {
        int vertex = queue[front++];  // 出队列
        topologicalOrder[count++] = vertex;
        // 遍历顶点的邻接顶点，减少其入度
        struct Node* temp = graph->adjList[vertex];
        while (temp != NULL) {
            indegree[temp->vertex]--;
            if (indegree[temp->vertex] == 0) {
                queue[++rear] = temp->vertex;
            }
            temp = temp->next;
        }
    }
    // 输出拓扑排序结果
    printf("Topological Sort Order: ");
    for (int i = 0; i < count; i++) {
        printf("%d ", topologicalOrder[i]);
    }
    printf("\n");
}
20.B树和B+树

B树（B-tree）：

  • B树是一种平衡的多路搜索树，其中每个节点可以包含多个子节点。
  • 每个节点中的关键字按非递减顺序排列，且节点中关键字的数量至少等于子节点数目的一半。
  • 所有叶子节点位于同一层，并且没有数据的重复。
  • B树的节点在插入和删除操作后可以进行自平衡，使得树保持平衡状态。

B+树（B±tree）：

  • B+树是在B树的基础上进行了改进，它与B树相比有更大的节点容量。
  • B+树的内部节点不存储数据，只存储关键字和指向子节点的指针。
  • 所有数据都存储在叶子节点中，叶子节点之间使用指针连接成一个有序链表，使得范围查询更加高效。
  • B+树的叶子节点形成了一个有序链表，可以进行范围查询等操作。

B+树通常被认为是一种更适合数据库索引的数据结构，因为它的数据存储方式更加有序，可以更快地进行范围查询和顺序遍历。

21.哈希表的概念、构造方法，哈希冲突的解决方法

哈希表基于哈希函数（Hash Function）实现，将关键字映射到表中的位置。
通常，哈希函数将关键字转换为固定长度的哈希值，然后根据哈希值确定关键字在表中的位置。

构造方法：
1.选择哈希函数：选择合适的哈希函数是构造哈希表的第一步。哈希函数应该将关键字均匀地分布到哈希表中的位置，以避免冲突。
2.确定哈希表大小：确定哈希表的大小，通常选择素数作为表的大小，以减少冲突的可能性。
3.解决冲突：在确定了哈希函数和哈希表大小后，需要解决哈希冲突的问题。常见的冲突解决方法包括开放定址法（如线性探测和二次探测）、链地址法和再哈希法等。

哈希冲突的解决方法：

  1. 开放定址法：当发生冲突时，通过探测序列来找到下一个可用的位置。常见的探测方法有线性探测、二次探测和双重散列。
  2. 链地址法：将哈希表的每个位置都连接一个链表，当发生冲突时，将冲突的元素添加到链表中。这种方法需要在表中存储指向链表头的指针。
  3. 再哈希法：当发生冲突时，使用另一个哈希函数对冲突的关键字进行重新哈希，直到找到空闲位置为止。通常需要多个哈希函数。
22.内部排序辨析

内部排序是指对数据集合（通常是存储在内存中）进行排序的过程。
在内部排序中，整个数据集合可以一次性加载到内存中，并且所有的排序操作都在内存中进行，因此也称为内存排序。

  1. 冒泡排序（Bubble Sort）：依次比较相邻的元素，将较大（或较小）的元素逐步交换至右侧，直到整个序列有序。时间复杂度：O(n^2) 空间复杂度：O(1)
  2. 选择排序（Selection Sort）：每次从未排序的部分选择最小（或最大）的元素，放置到已排序部分的末尾。时间复杂度：O(n^2) 空间复杂度：O(1)
  3. 插入排序（Insertion Sort）：将未排序的元素逐个插入到已排序部分的合适位置，直到整个序列有序。时间复杂度：O(n^2) 空间复杂度：O(1)
  4. 希尔排序（Shell Sort）：是插入排序的改进版本，通过将序列分成多个子序列进行排序，然后逐步缩小子序列的长度，最终完成排序。
    时间复杂度：O(n log n)~O(n^2) 空间复杂度：O(1)
  5. 归并排序（Merge Sort）：采用分治法，将序列分成两个子序列，分别进行排序，然后将排好序的子序列合并成一个有序序列。时间复杂度：O(n log n) 空间复杂度：O(n)
  6. 快速排序（Quick Sort）：采用分治法，通过选择一个基准元素，将序列分成小于基准的部分和大于基准的部分，然后对这两部分分别进行递归排序。时间复杂度：O(n log n) 空间复杂度：O(log n) ~ O(n)
  7. 堆排序（Heap Sort）：利用堆这种数据结构进行排序，通过构建最大堆或最小堆来实现排序。时间复杂度：O(n log n) 空间复杂度：O(1)
23.外部排序辨析

外部排序是一种在数据量过大无法全部加载到内存中进行排序时使用的排序方法。
它通常涉及将数据分成适当大小的块，然后在内存中对每个块进行排序，最后将排序后的块合并成一个有序序列。
外部排序的核心思想是尽量减少对外部存储的访问次数，以提高排序效率。

  1. 多路归并排序：
    • 基本思想：将数据分成多个块，每个块都能够全部加载到内存中进行排序。然后利用归并排序的思想，将多个有序块合并成一个更大的有序块，直到整个数据集合排序完成。
    • 优点：适用于大规模数据的排序，且可以利用多个磁盘进行并行排序。
    • 缺点：需要额外的磁盘空间来存储排序后的块，且合并过程可能会产生额外的磁盘读写开销。
  2. 置换-选择排序：
    • 基本思想：将数据分成多个块，并在内存中维护一个“缓冲区”，用于存储每个块中的一部分数据。然后在缓冲区中选择最小（或最大）的元素，输出到外部存储，直到所有块中的数据都被输出。
    • 优点：不需要额外的磁盘空间来存储排序后的块，适用于数据集合无法全部加载到内存中的情况。
    • 缺点：可能需要多次访问外部存储，造成较高的磁盘读写开销。
  3. 多路平衡归并排序：
    • 基本思想：类似于多路归并排序，但是在归并过程中需要保持各个块之间的平衡，以提高归并的效率。
    • 优点：能够更好地利用外部存储的空间，减少归并过程中的磁盘读写开销。
    • 缺点：实现较为复杂，需要维护块之间的平衡。
  4. 外部快速排序：
    • 基本思想：类似于快速排序，但是在划分过程中需要将数据分成适当大小的块，并在内存中对每个块进行排序。然后利用归并操作将排序后的块合并成一个有序序列。
    • 优点：基于快速排序，具有较好的平均时间复杂度。
    • 缺点：可能会产生较大的磁盘读写开销，特别是在数据分布不均匀的情况下。