网站制作可能出现的问题wordpress固定连接只能访问首页

网站制作可能出现的问题,wordpress固定连接只能访问首页,网络服务费属于什么费用,建设网站 程序员的提成排序是计算机科学中最基础且核心的操作之一#xff0c;它通过特定规则将无序数据转化为有序序列#xff0c;广泛应用于购物筛选、数据统计、院校排名等实际场景。在 C 语言中#xff0c;排序算法的实现直接影响程序的执行效率#xff0c;不同场景下选择合适的排序算法能显著…排序是计算机科学中最基础且核心的操作之一它通过特定规则将无序数据转化为有序序列广泛应用于购物筛选、数据统计、院校排名等实际场景。在 C 语言中排序算法的实现直接影响程序的执行效率不同场景下选择合适的排序算法能显著提升性能。本文将详细拆解常见排序算法的原理、代码实现并通过实战对比分析各算法的优劣帮助读者深入理解并灵活运用。一、排序基础概念1.1 核心定义排序使一串记录按照某个或某些关键字的大小递增或递减排列的操作。关键字可以是数字、字符等可比较的属性例如商品价格、销量、学生成绩等。1.2 关键评价指标时间复杂度算法执行所需的时间与数据规模的关系反映算法的执行效率。空间复杂度算法执行所需的额外存储空间与数据规模的关系。稳定性若待排序序列中存在多个关键字相同的记录排序后它们的相对次序保持不变则称该算法稳定否则不稳定。稳定性在多关键字排序场景如先按价格排序再按销量排序中至关重要。1.3 常见排序算法分类根据实现思路常见排序算法可分为以下几类插入排序直接插入排序、希尔排序选择排序直接选择排序、堆排序交换排序冒泡排序、快速排序归并排序二路归并排序非比较排序计数排序二、经典排序算法详解原理 代码以下所有算法均基于整型数组排序升序实现测试用例统一为int a[] {5, 3, 9, 6, 2, 4, 7, 1, 8}2.1 插入排序类插入排序的核心思想是将待排序元素逐个插入到已有序的子序列中最终形成完整的有序序列。2.1.1 直接插入排序原理初始时将第一个元素视为有序子序列。对于第 ii≥1个元素与有序子序列中的元素从后往前依次比较。找到合适的插入位置将该元素插入原位置元素依次后移。这就像玩扑克牌时我们会把新摸到的牌插入到手中已排好序的牌组中。代码实现#include stdio.h // 直接插入排序升序 void InsertSort(int* a, int n) { // 遍历待插入的元素从第二个元素开始 for (int i 0; i n - 1; i) { int end i; // 有序子序列的最后一个元素下标 int tmp a[end 1]; // 待插入的元素 // 从后往前查找插入位置 while (end 0) { if (a[end] tmp) { a[end 1] a[end]; // 元素后移 end--; } else { break; // 找到插入位置退出循环 } } a[end 1] tmp; // 插入元素 } } // 打印数组 void PrintArray(int* a, int n) { for (int i 0; i n; i) { printf(%d , a[i]); } printf(\n); } int main() { int a[] {5, 3, 9, 6, 2, 4, 7, 1, 8}; int n sizeof(a) / sizeof(a[0]); printf(直接插入排序前); PrintArray(a, n); InsertSort(a, n); printf(直接插入排序后); PrintArray(a, n); return 0; }特性总结时间复杂度O (N²)最坏 / 平均情况O (N)最好情况数组已有序空间复杂度O (1)原地排序稳定性稳定适用场景数据量小或接近有序的场景如少量数据的局部排序2.1.2 希尔排序缩小增量排序原理直接插入排序在数据量较大且无序时效率较低希尔排序通过 预排序 让数组接近有序再进行直接插入排序从而优化性能。选定一个增量 gap初始通常为 n/31将数组按 gap 分组每组内元素距离为 gap。对每组内元素进行直接插入排序。缩小 gapgapgap/31重复分组和排序操作。当 gap1 时数组已接近有序此时进行一次直接插入排序即可完成最终排序。代码实现// 希尔排序升序 void ShellSort(int* a, int n) { int gap n; // 逐步缩小gap直到gap1 while (gap 1) { gap gap / 3 1; // 增量计算公式确保最后gap1 // 对每组进行插入排序 for (int i 0; i n - gap; i) { int end i; int tmp a[end gap]; while (end 0) { if (a[end] tmp) { a[end gap] a[end]; end - gap; } else { break; } } a[end gap] tmp; } } } int main() { int a[] {5, 3, 9, 6, 2, 4, 7, 1, 8}; int n sizeof(a) / sizeof(a[0]); printf(希尔排序前); PrintArray(a, n); ShellSort(a, n); printf(希尔排序后); PrintArray(a, n); return 0; }特性总结时间复杂度O (N^1.3)~O (N²)取决于 gap 序列严蔚敏《数据结构》中给出平均复杂度约 O (N^1.3)空间复杂度O (1)稳定性不稳定分组排序会破坏相同元素的相对次序适用场景中等数据量的排序性能优于直接插入排序2.2 选择排序类选择排序的核心思想是每次从待排序序列中选出最小或最大的元素放到序列的起始或末尾位置重复直到排序完成。2.2.1 直接选择排序原理遍历序列找到最小元素和最大元素的下标。将最小元素与序列起始位置元素交换最大元素与序列末尾位置元素交换。缩小排序范围起始位置后移末尾位置前移重复上述操作直到范围缩小为 1。代码实现// 交换两个整数 void Swap(int* x, int* y) { int tmp *x; *x *y; *y tmp; } // 直接选择排序升序 void SelectSort(int* a, int n) { int begin 0, end n - 1; while (begin end) { int mini begin, maxi begin; // 最小、最大元素下标 // 查找[begin, end]区间内的最小和最大元素 for (int i begin; i end; i) { if (a[i] a[mini]) { mini i; } if (a[i] a[maxi]) { maxi i; } } // 处理最小元素防止最小元素在end位置被覆盖 Swap(a[mini], a[begin]); if (begin maxi) { // 若最大元素在begin位置交换后maxi应指向mini的原位置 maxi mini; } // 处理最大元素 Swap(a[maxi], a[end]); begin; end--; } } int main() { int a[] {5, 3, 9, 6, 2, 4, 7, 1, 8}; int n sizeof(a) / sizeof(a[0]); printf(直接选择排序前); PrintArray(a, n); SelectSort(a, n); printf(直接选择排序后); PrintArray(a, n); return 0; }特性总结时间复杂度O (N²)最坏 / 平均 / 最好情况均需遍历查找空间复杂度O (1)稳定性不稳定例如序列 [5,8,5,2]第一次交换后两个 5 的相对次序改变适用场景数据量小对稳定性无要求的场景实际应用中较少使用2.2.2 堆排序原理堆排序是选择排序的优化版本利用堆完全二叉树的数据结构快速获取最大 / 最小元素。排升序需构建大堆父节点值≥子节点值排降序需构建小堆。构建大堆后堆顶元素为最大值将其与堆尾元素交换此时堆尾为有序区。对剩余元素无序区重新调整为大堆重复交换堆顶与堆尾操作直到无序区为空。代码实现// 堆调整大堆 void AdjustHeap(int* a, int n, int parent) { int child 2 * parent 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 2 * parent 1; } else { break; } } } // 堆排序升序 void HeapSort(int* a, int n) { // 1. 构建大堆从最后一个非叶子节点开始调整 for (int i (n - 2) / 2; i 0; i--) { AdjustHeap(a, n, i); } // 2. 排序交换堆顶与堆尾调整堆 for (int i n - 1; i 0; i--) { Swap(a[0], a[i]); // 堆顶最大值放入有序区 AdjustHeap(a, i, 0); // 调整剩余无序区为大堆 } } int main() { int a[] {5, 3, 9, 6, 2, 4, 7, 1, 8}; int n sizeof(a) / sizeof(a[0]); printf(堆排序前); PrintArray(a, n); HeapSort(a, n); printf(堆排序后); PrintArray(a, n); return 0; }特性总结时间复杂度O (NlogN)建堆 O (N)调整堆 O (NlogN)空间复杂度O (1)稳定性不稳定适用场景大数据量排序对空间开销敏感的场景2.3 交换排序类交换排序的核心思想是通过比较两个元素的关键字若次序错误则交换它们的位置直到整个序列有序。2.3.1 冒泡排序原理冒泡排序是最基础的交换排序元素像气泡一样 上浮 到对应位置。从序列起始位置开始依次比较相邻元素若前元素大于后元素则交换。每一轮遍历后最大元素会 冒泡 到序列末尾有序区。优化若某一轮未发生交换说明序列已有序可直接退出。代码实现// 冒泡排序升序优化版 void BubbleSort(int* a, int n) { for (int i 0; i n; i) { int exchange 0; // 标记是否发生交换 // 遍历无序区相邻元素比较交换 for (int j 0; j n - i - 1; j) { if (a[j] a[j 1]) { Swap(a[j], a[j 1]); exchange 1; } } if (exchange 0) { break; // 无交换序列已有序 } } } int main() { int a[] {5, 3, 9, 6, 2, 4, 7, 1, 8}; int n sizeof(a) / sizeof(a[0]); printf(冒泡排序前); PrintArray(a, n); BubbleSort(a, n); printf(冒泡排序后); PrintArray(a, n); return 0; }特性总结时间复杂度O (N²)最坏 / 平均情况O (N)最好情况优化后空间复杂度O (1)稳定性稳定适用场景数据量小或教学场景实际应用中效率较低2.3.2 快速排序快速排序是 Hoare 于 1962 年提出的高效排序算法基于分治法思想是实际应用中最常用的排序算法之一。原理选择序列中的一个元素作为基准值key。划分将序列分割为两部分左部分元素均小于基准值右部分元素均大于基准值。递归对左右两部分分别重复上述过程直到整个序列有序。核心实现划分算法快速排序的效率关键在于划分算法以下实现三种常用划分方式1Hoare 版本左右指针法// Hoare版本划分 int PartitionHoare(int* a, int left, int right) { int keyi left; // 基准值下标选左端点 while (left right) { // 右指针找比基准值小的元素 while (left right a[right] a[keyi]) { right--; } // 左指针找比基准值大的元素 while (left right a[left] a[keyi]) { left; } // 交换左右指针指向的元素 Swap(a[left], a[right]); } // 基准值归位leftright为基准值的正确位置 Swap(a[keyi], a[left]); return left; // 返回基准值下标 } // 快速排序主函数 void QuickSort(int* a, int left, int right) { if (left right) { return; // 递归终止条件 } int keyi PartitionHoare(a, left, right); // 递归排序左区间和右区间 QuickSort(a, left, keyi - 1); QuickSort(a, keyi 1, right); }2挖坑法// 挖坑法划分 int PartitionHole(int* a, int left, int right) { int key a[left]; // 基准值挖坑 int hole left; // 坑的位置 while (left right) { // 右指针找比基准值小的元素填入左坑 while (left right a[right] key) { right--; } a[hole] a[right]; hole right; // 右指针位置变为新坑 // 左指针找比基准值大的元素填入右坑 while (left right a[left] key) { left; } a[hole] a[left]; hole left; // 左指针位置变为新坑 } a[hole] key; // 基准值填入最后一个坑 return hole; } // 快速排序挖坑法 void QuickSortHole(int* a, int left, int right) { if (left right) { return; } int keyi PartitionHole(a, left, right); QuickSortHole(a, left, keyi - 1); QuickSortHole(a, keyi 1, right); }3前后指针法Lomuto 版本// 前后指针法划分 int PartitionPrevCur(int* a, int left, int right) { int keyi left; // 基准值下标 int prev left; // 前指针指向小于基准值区域的末尾 int cur left 1;// 后指针遍历序列 while (cur right) { // 找到比基准值小的元素前指针后移并交换 if (a[cur] a[keyi] prev ! cur) { Swap(a[prev], a[cur]); } cur; } // 基准值归位 Swap(a[keyi], a[prev]); return prev; } // 快速排序前后指针法 void QuickSortPrevCur(int* a, int left, int right) { if (left right) { return; } int keyi PartitionPrevCur(a, left, right); QuickSortPrevCur(a, left, keyi - 1); QuickSortPrevCur(a, keyi 1, right); }4非递归版本避免栈溢出递归版本的快速排序在数据量极大时可能出现栈溢出非递归版本通过栈模拟递归过程#include stdlib.h // 栈结构定义存储区间左右边界 typedef struct Stack { int* data; int top; int capacity; } Stack; // 栈初始化 void StackInit(Stack* st, int capacity) { st-data (int*)malloc(sizeof(int) * capacity); st-top -1; st-capacity capacity; } // 入栈 void StackPush(Stack* st, int val) { st-data[st-top] val; } // 出栈 void StackPop(Stack* st) { st-top--; } // 获取栈顶元素 int StackTop(Stack* st) { return st-data[st-top]; } // 栈是否为空 int StackEmpty(Stack* st) { return st-top -1; } // 栈销毁 void StackDestroy(Stack* st) { free(st-data); st-data NULL; st-top -1; st-capacity 0; } // 快速排序非递归版本 void QuickSortNonR(int* a, int left, int right) { Stack st; StackInit(st, right - left 1); // 初始区间入栈先入右边界再入左边界 StackPush(st, right); StackPush(st, left); while (!StackEmpty(st)) { // 出栈获取当前区间 int l StackTop(st); StackPop(st); int r StackTop(st); StackPop(st); // 划分区间 int keyi PartitionPrevCur(a, l, r); // 右区间入栈若存在 if (keyi 1 r) { StackPush(st, r); StackPush(st, keyi 1); } // 左区间入栈若存在 if (l keyi - 1) { StackPush(st, keyi - 1); StackPush(st, l); } } StackDestroy(st); } int main() { int a[] {5, 3, 9, 6, 2, 4, 7, 1, 8}; int n sizeof(a) / sizeof(a[0]); printf(快速排序前); PrintArray(a, n); QuickSort(a, 0, n - 1); // 递归版本 // QuickSortNonR(a, 0, n - 1); // 非递归版本 printf(快速排序后); PrintArray(a, n); return 0; }特性总结时间复杂度O (NlogN)平均情况O (N²)最坏情况如有序数组选端点为基准值空间复杂度O (logN)递归栈开销非递归版本 O (logN)栈存储区间稳定性不稳定适用场景大数据量排序是实际应用中效率最高的排序算法之一需优化基准值选择如三数取中2.4 归并排序归并排序是基于分治法的稳定排序算法核心思想是 先分后合。原理分解将数组递归拆分为两个子数组直到每个子数组只有一个元素天然有序。合并将两个有序子数组合并为一个有序数组重复合并过程直到得到完整的有序数组。代码实现// 合并两个有序子数组 void Merge(int* a, int left, int mid, int right, int* tmp) { int begin1 left, end1 mid; // 第一个子数组区间 int begin2 mid 1, end2 right;// 第二个子数组区间 int index left; // 临时数组下标 // 合并两个有序子数组到临时数组 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]; } // 临时数组元素拷贝回原数组 for (int i left; i right; i) { a[i] tmp[i]; } } // 归并排序递归函数 void _MergeSort(int* a, int left, int right, int* tmp) { if (left right) { return; // 递归终止条件 } int mid (left right) / 2; // 分解左区间和右区间 _MergeSort(a, left, mid, tmp); _MergeSort(a, mid 1, right, tmp); // 合并两个有序子数组 Merge(a, left, mid, right, tmp); } // 归并排序主函数 void MergeSort(int* a, int n) { int* tmp (int*)malloc(sizeof(int) * n); // 临时数组避免递归中重复创建 if (tmp NULL) { perror(malloc fail); return; } _MergeSort(a, 0, n - 1, tmp); free(tmp); tmp NULL; } int main() { int a[] {5, 3, 9, 6, 2, 4, 7, 1, 8}; int n sizeof(a) / sizeof(a[0]); printf(归并排序前); PrintArray(a, n); MergeSort(a, n); printf(归并排序后); PrintArray(a, n); return 0; }特性总结时间复杂度O (NlogN)最坏 / 平均 / 最好情况空间复杂度O (N)需要临时数组存储合并结果稳定性稳定适用场景大数据量排序对稳定性有要求的场景如多关键字排序2.5 非比较排序计数排序计数排序不属于比较排序基于 鸽巢原理通过统计元素出现次数实现排序适用于数据范围集中的场景。原理找出待排序数组中的最大值和最小值计算数据范围 range max - min 1。创建计数数组 count统计每个元素出现的次数。根据计数数组的统计结果将元素按顺序放回原数组。代码实现#include string.h // 计数排序 void CountSort(int* a, int n) { if (n 1) { return; } // 1. 找出最大值和最小值 int min a[0], max a[0]; for (int i 1; i n; i) { if (a[i] max) { max a[i]; } if (a[i] min) { min a[i]; } } // 2. 创建计数数组并初始化 int range max - min 1; int* count (int*)malloc(sizeof(int) * range); if (count NULL) { perror(malloc fail); return; } memset(count, 0, sizeof(int) * range); // 3. 统计每个元素出现次数 for (int i 0; i n; i) { count[a[i] - min]; // 映射到计数数组下标避免数据范围从0开始 } // 4. 根据计数结果排序 int j 0; for (int i 0; i range; i) { while (count[i]-- 0) { a[j] i min; // 恢复原数据 } } free(count); count NULL; } int main() { int a[] {6, 1, 2, 9, 4, 2, 4, 1, 4}; int n sizeof(a) / sizeof(a[0]); printf(计数排序前); PrintArray(a, n); CountSort(a, n); printf(计数排序后); PrintArray(a, n); return 0; }特性总结时间复杂度O (N range)N 为数据量range 为数据范围空间复杂度O (range)稳定性稳定按顺序放回元素可保持相对次序适用场景数据范围小且集中的场景如学生成绩、年龄排序三、排序算法性能对比实战为了直观感受各算法的效率我们通过测试代码对比 7 种排序算法在 10 万条随机数据下的执行时间单位毫秒。测试代码#include stdio.h #include stdlib.h #include time.h #include string.h // 此处省略上述所有排序算法的实现InsertSort、ShellSort、SelectSort、HeapSort、QuickSort、MergeSort、BubbleSort // 测试排序性能 void TestSortPerformance() { srand(time(0)); const int N 100000; // 数据量10万条 // 分配7个数组存储相同的随机数据 int* a1 (int*)malloc(sizeof(int) * N); int* a2 (int*)malloc(sizeof(int) * N); int* a3 (int*)malloc(sizeof(int) * N); int* a4 (int*)malloc(sizeof(int) * N); int* a5 (int*)malloc(sizeof(int) * N); int* a6 (int*)malloc(sizeof(int) * N); int* a7 (int*)malloc(sizeof(int) * N); // 生成随机数据 for (int i 0; i N; i) { a1[i] rand(); a2[i] a1[i]; a3[i] a1[i]; a4[i] a1[i]; a5[i] a1[i]; a6[i] a1[i]; a7[i] a1[i]; } // 测试各排序算法执行时间 clock_t begin, end; // 1. 直接插入排序 begin clock(); InsertSort(a1, N); end clock(); printf(直接插入排序%d ms\n, end - begin); // 2. 希尔排序 begin clock(); ShellSort(a2, N); end clock(); printf(希尔排序%d ms\n, end - begin); // 3. 直接选择排序 begin clock(); SelectSort(a3, N); end clock(); printf(直接选择排序%d ms\n, end - begin); // 4. 堆排序 begin clock(); HeapSort(a4, N); end clock(); printf(堆排序%d ms\n, end - begin); // 5. 快速排序 begin clock(); QuickSort(a5, 0, N - 1); end clock(); printf(快速排序%d ms\n, end - begin); // 6. 归并排序 begin clock(); MergeSort(a6, N); end clock(); printf(归并排序%d ms\n, end - begin); // 7. 冒泡排序 begin clock(); BubbleSort(a7, N); end clock(); printf(冒泡排序%d ms\n, end - begin); // 释放内存 free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); } int main() { TestSortPerformance(); return 0; }测试结果参考排序算法执行时间ms直接插入排序3820希尔排序12直接选择排序2560堆排序18快速排序8归并排序15冒泡排序7650结果分析冒泡排序和直接选择排序效率最低时间复杂度为 O (N²)不适用于大数据量。直接插入排序在大数据量下效率较差但在数据接近有序时表现优异。希尔排序通过预排序优化效率远高于直接插入排序适用于中等数据量。快速排序、堆排序、归并排序效率最高时间复杂度为 O (NlogN)其中快速排序在平均情况下表现最佳。归并排序是稳定的 O (NlogN) 算法但需要额外空间堆排序无需额外空间但不稳定。四、排序算法选择指南场景需求推荐算法数据量小N≤100直接插入排序 / 直接选择排序数据量中等100N≤10000希尔排序数据量大N10000快速排序 / 堆排序 / 归并排序要求稳定排序归并排序 / 冒泡排序 / 直接插入排序数据范围集中如成绩计数排序对空间开销敏感堆排序 / 快速排序数据接近有序直接插入排序 / 冒泡排序优化版