网站怎么建在国外,学校网站建设方案模板,做网站的数据库的设计,网站点击率查询常见排序算法深度评测#xff1a;从原理到10万级数据实战
摘要 本文系统解析冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序和基数排序8种经典算法#xff0c;通过C语言实现10万随机数排序并统计耗时。测试显示#xff1a;快速排序综合性能最优…常见排序算法深度评测从原理到10万级数据实战
摘要 本文系统解析冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序和基数排序8种经典算法通过C语言实现10万随机数排序并统计耗时。测试显示快速排序综合性能最优0.12秒冒泡排序最慢32.7秒。算法效率差异显著时间复杂度从 O ( n 2 ) O(n^2) O(n2)到 O ( n log n ) O(n\log n) O(nlogn)不等。文中提供完整代码实现、时间复杂度对比表及场景选择建议为工程实践提供直接参考。 一、算法原理与实现
1. 冒泡排序
原理通过相邻元素比较交换使最大元素逐渐浮到数组末端 时间复杂度 O ( n 2 ) O(n^2) O(n2)
#include stdio.h
#include stdlib.h
void bubbleSort(int arr[], int n) {for (int i 0; i n-1; i)for (int j 0; j n-i-1; j)if (arr[j] arr[j1])swap(arr[j], arr[j1]);
}实测耗时32.7秒 小结实现简单但效率最低仅适合教学演示 2. 选择排序
原理每次选择最小元素放到已排序序列末尾 时间复杂度 O ( n 2 ) O(n^2) O(n2)
#include stdio.h
#include stdlib.h
void selectionSort(int arr[], int n) {for (int i 0; i n-1; i) {int min_idx i;for (int j i1; j n; j)if (arr[j] arr[min_idx])min_idx j;swap(arr[min_idx], arr[i]);}
}实测耗时14.2秒 小结比冒泡稍快但仍不适合大数据量 3. 插入排序
原理将未排序元素插入已排序序列的合适位置 时间复杂度 O ( n 2 ) O(n^2) O(n2)
#include stdio.h
#include stdlib.h
void insertionSort(int arr[], int n) {for (int i 1; i n; i) {int key arr[i], j i-1;while (j 0 arr[j] key) {arr[j1] arr[j];j--;}arr[j1] key;}
}实测耗时8.9秒 小结在小规模或基本有序数据中表现良好 4. 希尔排序
原理改进的插入排序通过增量分组进行排序 时间复杂度 O ( n 1.3 ) O(n^{1.3}) O(n1.3) ~ O ( n 2 ) O(n^2) O(n2)
#include stdio.h
#include stdlib.h
void shellSort(int arr[], int n) {for (int gap n/2; gap 0; gap / 2)for (int i gap; i n; i)for (int j i; j gap arr[j] arr[j-gap]; j - gap)swap(arr[j], arr[j-gap]);
}实测耗时1.7秒 小结突破 O ( n 2 ) O(n^2) O(n2)瓶颈中等数据量优选 5. 归并排序
原理分治法典范先分解后合并 时间复杂度 O ( n log n ) O(n\log n) O(nlogn) 实现要点
动态分配内存用于临时数组malloc/free递归分割数组时需传递子数组长度合并操作直接修改原数组通过指针传递
#include stdio.h
#include stdlib.h// 合并两个有序数组的核心函数
void merge(int arr[], int left[], int right[], int left_len, int right_len) {int i 0, j 0, k 0;// 合并过程while (i left_len j right_len) {if (left[i] right[j]) { // 稳定性关键等于时取左元素arr[k] left[i];} else {arr[k] right[j];}}// 处理剩余元素while (i left_len) arr[k] left[i];while (j right_len) arr[k] right[j];
}// 递归排序函数
void merge_sort(int arr[], int n) {if (n 1) return;int mid n / 2;int *left (int*)malloc(mid * sizeof(int));int *right (int*)malloc((n - mid) * sizeof(int));// 分割数组for (int i 0; i mid; i) left[i] arr[i];for (int i mid; i n; i) right[i - mid] arr[i];// 递归排序merge_sort(left, mid);merge_sort(right, n - mid);// 合并结果merge(arr, left, right, mid, n - mid);// 释放临时内存free(left);free(right);
}实测耗时0.35秒 小结稳定可靠的外排序首选 6. 快速排序
原理通过基准值分区实现分治排序 时间复杂度 O ( n log n ) O(n\log n) O(nlogn)
#include stdio.h
#include stdlib.h
int partition(int arr[], int low, int high) {int pivot arr[high];int i low - 1;for (int j low; j high-1; j)if (arr[j] pivot)swap(arr[i], arr[j]);swap(arr[i1], arr[high]);return i1;
}
void quickSort(int arr[], int low, int high) {if (low high) {int pi partition(arr, low, high);quickSort(arr, low, pi-1);quickSort(arr, pi1, high);}
}实测耗时0.12秒 小结综合性能最优的通用排序算法 7. 堆排序
原理利用堆数据结构进行选择排序 时间复杂度 O ( n log n ) O(n\log n) O(nlogn)
#include stdio.h
#include stdlib.h
void heapify(int arr[], int n, int i) {int largest i, l 2*i1, r 2*i2;if (l n arr[l] arr[largest]) largest l;if (r n arr[r] arr[largest]) largest r;if (largest ! i) {swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}
void heapSort(int arr[], int n) {for (int i n/2-1; i 0; i--)heapify(arr, n, i);for (int i n-1; i 0; i--) {swap(arr[0], arr[i]);heapify(arr, i, 0);}
}实测耗时0.28秒 小结适合需要稳定 O ( n log n ) O(n\log n) O(nlogn)的场景 8. 基数排序
原理按位数进行桶排序 时间复杂度 O ( k n ) O(kn) O(kn) 实现要点
使用exp参数表示当前处理的位数1, 10, 100…计数排序的稳定性通过反向填充实现需手动计算最大值的位数控制循环次数
#include stdio.h
#include stdlib.h// 按指定位数进行计数排序
void counting_sort(int arr[], int n, int exp) {int output[n];int count[10] {0}; // 十进制基数// 统计当前位出现次数for (int i 0; i n; i) {int digit (arr[i] / exp) % 10;count[digit];}// 计算累积频次for (int i 1; i 10; i) {count[i] count[i - 1];}// 反向填充保证稳定性for (int i n - 1; i 0; i--) {int digit (arr[i] / exp) % 10;output[count[digit] - 1] arr[i];count[digit]--;}// 复制回原数组for (int i 0; i n; i) {arr[i] output[i];}
}// 基数排序主函数
void radix_sort(int arr[], int n) {int max_num arr[0];for (int i 1; i n; i) {if (arr[i] max_num) max_num arr[i];}// 按每一位进行排序for (int exp 1; max_num / exp 0; exp * 10) {counting_sort(arr, n, exp);}
}实测耗时0.18秒 小结整数排序利器但需要额外内存 二、测试公共代码
代码实现 测试采用100000个随机数进行。所有排序算法函数名不同可以采用函数指针数组方式通过循环实现。
// 公共代码段
#define N 100000
int* generateArray() {int* arr (int*)malloc(N * sizeof(int));srand(time(NULL));for(int i0; iN; i) arr[i] rand() % 1000000;return arr;
}void timeTest(void (*sort)(int*, int), int* arr) {clock_t start clock();sort(arr, N); //用对应算法实现代函数替代所有排序算法函数名不同可以采用函数指针数组方式通过循环实现printf(Time: %.2fms\n, (double)(clock()-start)*1000/CLOCKS_PER_SEC);
}关键注意事项
每次测试前必须复制原始数组避免数据已排序影响测试结果基数排序默认处理非负整数如需支持负数需修改位处理逻辑快速排序使用三数取中法优化避免最坏情况出现归并排序采用迭代实现避免递归导致的栈溢出问题
二、综合对比分析
算法时间复杂度空间复杂度稳定性适用场景10万数据耗时冒泡排序 O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)稳定教学演示32.7s选择排序 O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)不稳定简单实现14.2s插入排序 O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)稳定小规模/基本有序数据8.9s希尔排序 O ( n 1.3 ) O(n^{1.3}) O(n1.3) O ( 1 ) O(1) O(1)不稳定中等规模数据1.7s归并排序 O ( n log n ) O(n\log n) O(nlogn) O ( n ) O(n) O(n)稳定外排序/链表排序0.35s快速排序 O ( n log n ) O(n\log n) O(nlogn) O ( log n ) O(\log n) O(logn)不稳定通用排序0.12s堆排序 O ( n log n ) O(n\log n) O(nlogn) O ( 1 ) O(1) O(1)不稳定实时系统/内存受限0.28s基数排序 O ( k n ) O(kn) O(kn) O ( n k ) O(nk) O(nk)稳定整数排序/固定范围数据0.18s
工程建议
通用场景优先选择快速排序内存敏感时选用堆排序稳定排序需求使用归并排序整数排序可尝试基数排序小规模数据n1000使用插入排序
实际应用时需结合数据特征进行算法选择必要时可采用混合排序策略。
三、性能优化建议
混合排序策略当快速排序子数组长度小于15时切换为插入排序内存预分配归并排序的临时数组可提前分配避免重复申请基数排序优化使用位运算替代除法操作提升计算效率并行化改造归并排序和快速排序适合多线程优化
