万维网如何建设网站天津高端网站建设企业

万维网如何建设网站,天津高端网站建设企业,空间制作网站,氧化锌网站建设排序的下界介绍这里简单介绍比较类排序的时间复杂度下界#xff0c;比较类排序的核心是通过元素间两两比较确定元素的相对位置#xff0c;这里通过决策树模型来推导其下界。决策树是一颗满二叉树#xff0c;每个节点表示一次元素比较#xff0c;左分支表示比较结果为真比较类排序的核心是通过元素间两两比较确定元素的相对位置这里通过决策树模型来推导其下界。决策树是一颗满二叉树每个节点表示一次元素比较左分支表示比较结果为真右分支表示比较结果为假从根节点到叶子节点的一条路径对应一次完整的排序即树的高度就对应了排序的次数。假设有n个元素的序列那由n个元素所组成的序列情况数量有n种那么对应的排列情况也有n种即叶子节点是数量至少有n个对于满二叉树其叶子节点的数量是个h代表树的高度那就有不等式n解出来hnlogn-nlogelog2n,取最高次项得时间复杂度为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(NK)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, i1, 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 i0; i12; 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 i0; i5; 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 i0; i5; 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 i0; i2; 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(✅ 已归并bucket1bucket2 → 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(✅ 已归并merge1bucket3 → 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文件模拟成无法一次性装入内存的大文件。算法发思路是先将大文件拆分成若干个能放入内存的小文件然后再对小文件进行快速排序的算法然后我们就获得了若干个排好序的小文件。接着逐个读取两个小文件每次取两个小文件中更小的数写入新文件直到其中一个文件读完那就把另一个文件的剩余数据全部追究进去这很类似于归并排序的归并操作。进行多轮这样的归并操作直到合成一个有序的大文件。分析外部排序的稳定性由内排序的算法和归并逻辑共同决定这里的归并是稳定的但内排序用了不稳定的快速排序所以总体是不稳定的。本版本中归并的时间复杂度是O(N)内排序所用的快速排序的时间复杂度是O(NLogN)合起来是O(NLogN)。