简单解释排序的下界，桶式排序与外部排序-洪萨配资

排序的下界

介绍

这里简单介绍比较类排序的时间复杂度下界，比较类排序的核心是通过元素间两两比较确定元素的相对位置，这里通过决策树模型来推导其下界。

决策树是一颗满二叉树，每个节点表示一次元素比较，左分支表示比较结果为真，右分支表示比较结果为假，从根节点到叶子节点的一条路径对应一次完整的排序，即树的高度就对应了排序的次数。

假设有n个元素的序列，那由n个元素所组成的序列情况数量有n！种，那么对应的排列情况也有n！种，即叶子节点是数量至少有n！个，对于满二叉树，其叶子节点的数量是个，h代表树的高度，那就有不等式n！，解出来hnlogn-nloge+log2n,取最高次项得时间复杂度为O(NLogN)。

桶式排序

介绍

之前在学链表时介绍的基数排序中就详细解释过桶式排序了，这里再精简的解释一下：桶式排序采用了分治的思想，先准备合适数量的桶，这些桶需要有一定的条件约束，也就是说元素满足对应桶的条件才能被放入对应的桶里，然后把将所有元素放入合适的桶里，接着在每个桶内用其他排序方法进行排序，最后再合并桶，由于前面桶是按一定规则收纳元素的，所以合并桶的过程就是直接合并，不需要再进行排序操作了。

实现

程序由豆包生成

#include <stdio.h> #include <stdlib.h> // 桶的节点结构（存储单个数据） typedef struct BucketNode { float data; // 存储数据（示例用浮点数，可改为int） struct BucketNode *next; // 指向下一个节点的指针 } BucketNode; // 桶结构（每个桶是一个链表） typedef struct Bucket { BucketNode *head; // 桶的头节点 BucketNode *tail; // 桶的尾节点（优化插入效率） } Bucket; /** * @brief 初始化桶数组 * @param bucketArr 桶数组 * @param bucketNum 桶的数量 */ void initBuckets(Bucket *bucketArr, int bucketNum) { for (int i = 0; i < bucketNum; i++) { bucketArr[i].head = NULL; bucketArr[i].tail = NULL; } } /** * @brief 向桶中插入元素（尾插法） * @param bucket 目标桶 * @param value 要插入的值 */ void insertToBucket(Bucket *bucket, float value) { // 分配节点内存 BucketNode *newNode = (BucketNode *)malloc(sizeof(BucketNode)); if (newNode == NULL) { perror("malloc failed"); exit(EXIT_FAILURE); } newNode->data = value; newNode->next = NULL; // 桶为空时，头节点和尾节点指向新节点 if (bucket->head == NULL) { bucket->head = newNode; bucket->tail = newNode; } else { // 桶非空时，尾插 bucket->tail->next = newNode; bucket->tail = newNode; } } /** * @brief 对单个桶内的元素进行插入排序（稳定排序） * @param head 桶的头节点指针（会修改链表顺序） * @return 排序后的头节点 */ BucketNode *bucketSortInsert(BucketNode *head) { if (head == NULL || head->next == NULL) { return head; // 空桶或单个元素，无需排序 } BucketNode sorted = {0, NULL}; // 哨兵节点，简化插入逻辑 BucketNode *cur = head; // 遍历原链表 while (cur != NULL) { BucketNode *next = cur->next; // 保存下一个节点 BucketNode *p = &sorted; // 找到插入位置 // 找到第一个大于cur->data的节点的前驱 while (p->next != NULL && p->next->data < cur->data) { p = p->next; } // 插入cur到p和p->next之间 cur->next = p->next; p->next = cur; cur = next; } return sorted.next; // 返回排序后的头节点 } /** * @brief 桶排序核心函数 * @param arr 待排序数组 * @param n 数组长度 * @param bucketNum 桶的数量（建议等于数据量平方根） */ void bucketSort(float *arr, int n, int bucketNum) { if (n <= 1 || bucketNum <= 0) { return; // 无需排序 } // 1. 找到数组中的最大值和最小值，确定桶的范围 float min = arr[0], max = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] < min) min = arr[i]; if (arr[i] > max) max = arr[i]; } if (min == max) { return; // 所有元素相同，无需排序 } // 2. 初始化桶数组 Bucket *bucketArr = (Bucket *)malloc(bucketNum * sizeof(Bucket)); if (bucketArr == NULL) { perror("malloc failed"); exit(EXIT_FAILURE); } initBuckets(bucketArr, bucketNum); // 3. 将元素分配到对应的桶中 float bucketRange = (max - min) / bucketNum; // 每个桶的数值范围 for (int i = 0; i < n; i++) { // 计算元素所属的桶索引（向下取整） int bucketIndex = (int)((arr[i] - min) / bucketRange); // 处理最大值（可能超出最后一个桶的索引） if (bucketIndex >= bucketNum) { bucketIndex = bucketNum - 1; } insertToBucket(&bucketArr[bucketIndex], arr[i]); } // 4. 对每个桶排序，并合并回原数组 int index = 0; // 原数组的写入索引 for (int i = 0; i < bucketNum; i++) { // 对当前桶排序 bucketArr[i].head = bucketSortInsert(bucketArr[i].head); // 将排序后的桶元素写入原数组 BucketNode *cur = bucketArr[i].head; while (cur != NULL) { arr[index++] = cur->data; // 释放节点内存（避免内存泄漏） BucketNode *temp = cur; cur = cur->next; free(temp); } } // 5. 释放桶数组内存 free(bucketArr); } /** * @brief 打印数组 * @param arr 数组 * @param n 数组长度 */ void printArray(float *arr, int n) { for (int i = 0; i < n; i++) { printf("%.2f ", arr[i]); } printf("\n"); } // 测试示例 int main() { // 测试用例1：浮点数数组 float arr1[] = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51}; int n1 = sizeof(arr1) / sizeof(arr1[0]); printf("排序前："); printArray(arr1, n1); bucketSort(arr1, n1, 5); // 5个桶（建议桶数为数据量平方根） printf("排序后："); printArray(arr1, n1); // 测试用例2：整数数组（浮点数兼容整数） float arr2[] = {9, 3, 7, 5, 6, 4, 8, 2, 1, 10}; int n2 = sizeof(arr2) / sizeof(arr2[0]); printf("\n排序前："); printArray(arr2, n2); bucketSort(arr2, n2, 4); // 4个桶 printf("排序后："); printArray(arr2, n2); return 0; }

这里通过获取排序数组中的最大值和最小值来确定桶的数量，然后每个桶有对应的约束条件，第一个桶只能放0.3到0.34之间的元素，第二个桶只能放0.34到0.38之间的元素...然后再将对应元素放入对应桶里，本程序中使用的是插入排序对每个桶里的元素进行排序。最后直接合并所有桶完成整个序列的排序。

分析

由于桶式排序不是独立的排序，其稳定性取决于桶内排序用的是什么排序。

可以看桶排序的函数中有两个并列的for循环(第一个for循环是找最大最小值这里忽略)，第一个for循环要循环n次，第二个for循环要循环桶的数量的次数，所有总的时间复杂度(平均)为O(N+K)，K表示桶数。

外部排序

介绍

有时候要排序的元素个数过多导致无法在内存用完成其排序，这时就需要用到外部排序，这里介绍介绍分块内排序+多路归并的经典外部排序思想。

实现

程序由豆包生成

#include <stdio.h> #include <stdlib.h> #include <string.h> // 你的实际目录（必须正确） #define DIR "D:\\Soft2\\CLion\\CLionProject\\Sort\\" // 快速排序 void quickSort(int *arr, int left, int right) { if (left >= right) return; int p = arr[left], i = left, j = right; while (i < j) { while (i < j && arr[j] >= p) j--; arr[i] = arr[j]; while (i < j && arr[i] <= p) i++; arr[j] = arr[i]; } arr[i] = p; quickSort(arr, left, i-1); quickSort(arr, i+1, right); } // 步骤1：生成测试文件 void createTestFile() { char path[256]; strcpy(path, DIR); strcat(path, "data.txt"); FILE *fp = fopen(path, "w"); if (!fp) { printf("创建data.txt失败\n"); exit(1); } int data[] = {9,3,7,5,6,4,8,2,1,10,12,11}; for (int i=0; i<12; i++) fprintf(fp, "%d ", data[i]); fclose(fp); printf("✅ 已生成测试文件：%s\n", path); } // 步骤2：拆分文件为3个有序小文件 void splitToBuckets() { // 桶1 int bucket1[] = {9,3,7,5,6}; quickSort(bucket1, 0, 4); char path1[256]; strcpy(path1, DIR); strcat(path1, "bucket1.txt"); FILE *fp1 = fopen(path1, "w"); for (int i=0; i<5; i++) fprintf(fp1, "%d ", bucket1[i]); fclose(fp1); // 桶2 int bucket2[] = {4,8,2,1,10}; quickSort(bucket2, 0, 4); char path2[256]; strcpy(path2, DIR); strcat(path2, "bucket2.txt"); FILE *fp2 = fopen(path2, "w"); for (int i=0; i<5; i++) fprintf(fp2, "%d ", bucket2[i]); fclose(fp2); // 桶3 int bucket3[] = {12,11}; quickSort(bucket3, 0, 1); char path3[256]; strcpy(path3, DIR); strcat(path3, "bucket3.txt"); FILE *fp3 = fopen(path3, "w"); for (int i=0; i<2; i++) fprintf(fp3, "%d ", bucket3[i]); fclose(fp3); printf("✅ 已生成3个有序桶文件：bucket1.txt、bucket2.txt、bucket3.txt\n"); } // 步骤3：二路归并两个文件 void mergeTwo(const char *f1, const char *f2, const char *out) { FILE *fp1 = fopen(f1, "r"), *fp2 = fopen(f2, "r"), *fpOut = fopen(out, "w"); if (!fp1 || !fp2 || !fpOut) { printf("归并文件打开失败\n"); exit(1); } int a, b, hasA = fscanf(fp1, "%d", &a), hasB = fscanf(fp2, "%d", &b); while (hasA != EOF && hasB != EOF) { if (a <= b) { fprintf(fpOut, "%d ", a); hasA = fscanf(fp1, "%d", &a); } else { fprintf(fpOut, "%d ", b); hasB = fscanf(fp2, "%d", &b); } } while (hasA != EOF) { fprintf(fpOut, "%d ", a); hasA = fscanf(fp1, "%d", &a); } while (hasB != EOF) { fprintf(fpOut, "%d ", b); hasB = fscanf(fp2, "%d", &b); } fclose(fp1); fclose(fp2); fclose(fpOut); remove(f1); remove(f2); } // 步骤4：归并所有文件 void mergeAll() { char f1[256], f2[256], out[256]; // 归并bucket1和bucket2 → merge1.txt strcpy(f1, DIR); strcat(f1, "bucket1.txt"); strcpy(f2, DIR); strcat(f2, "bucket2.txt"); strcpy(out, DIR); strcat(out, "merge1.txt"); mergeTwo(f1, f2, out); printf("✅ 已归并bucket1+bucket2 → merge1.txt\n"); // 归并merge1和bucket3 → sorted.txt strcpy(f1, DIR); strcat(f1, "merge1.txt"); strcpy(f2, DIR); strcat(f2, "bucket3.txt"); strcpy(out, DIR); strcat(out, "sorted.txt"); mergeTwo(f1, f2, out); printf("✅ 已归并merge1+bucket3 → sorted.txt（最终文件）\n"); } // 步骤5：打印结果 void printResult() { char path[256]; strcpy(path, DIR); strcat(path, "sorted.txt"); FILE *fp = fopen(path, "r"); if (!fp) { printf("打开sorted.txt失败\n"); exit(1); } printf("\n🎉 最终排序结果："); int num; while (fscanf(fp, "%d", &num) != EOF) printf("%d ", num); printf("\n"); fclose(fp); } int main() { createTestFile(); splitToBuckets(); mergeAll(); printResult(); printf("\n✅ 所有操作完成！请查看 %ssorted.txt\n", DIR); return 0; }

这里将data.txt文件模拟成无法一次性装入内存的大文件。算法发思路是先将大文件拆分成若干个能放入内存的小文件，然后再对小文件进行快速排序的算法，然后我们就获得了若干个排好序的小文件。接着逐个读取两个小文件，每次取两个小文件中更小的数写入新文件，直到其中一个文件读完那就把另一个文件的剩余数据全部追究进去，这很类似于归并排序的归并操作。进行多轮这样的归并操作，直到合成一个有序的大文件。