销售型网站,惠州自适应网站建设,苏州加基森网站建设,wordpress 排序插件数组排序算法 用C语言实现的数组排序算法。 排序算法平均时间复杂度最坏时间复杂度最好时间复杂度空间复杂度是否稳定适用场景QuickO(n log n)O(n)O(n log n)O(log n)不稳定大规模数据#xff0c;通用排序BubbleO(n)O(n)O(n)O(1)稳定小规模数据#xff0c;教学用途InsertO(n)…数组排序算法 用C语言实现的数组排序算法。 排序算法平均时间复杂度最坏时间复杂度最好时间复杂度空间复杂度是否稳定适用场景QuickO(n log n)O(n²)O(n log n)O(log n)不稳定大规模数据通用排序BubbleO(n²)O(n²)O(n)O(1)稳定小规模数据教学用途InsertO(n²)O(n²)O(n)O(1)稳定小规模或部分有序数据SelectO(n²)O(n²)O(n²)O(1)不稳定小规模数据简单实现MergeO(n log n)O(n log n)O(n log n)O(n)稳定大规模数据稳定排序需求HeapO(n log n)O(n log n)O(n log n)O(1)不稳定大规模数据原地排序需求CountO(n k)O(n k)O(n k)O(n k)稳定小范围整数排序RadixO(d(n k))O(d(n k))O(d(n k))O(n k)稳定整数或字符串排序位数较小BucketO(n k)O(n²)O(n)O(n k)稳定均匀分布的数据ShellO(n log n)O(n²)O(n log n)O(1)不稳定中等规模数据改进的插入排序
快速排序
快速排序Quick Sort是一种高效的排序算法采用分治法Divide and Conquer策略。以下是使用C语言实现数组的快速排序的代码
#include stdio.h// 交换两个元素的值
void swap(int* a, int* b) {int temp *a;*a *b;*b temp;
}// 分区函数返回分区点的索引
int partition(int arr[], int low, int high) {int pivot arr[high]; // 选择最后一个元素作为基准int i (low - 1); // i是较小元素的索引for (int j low; j high - 1; j) {// 如果当前元素小于或等于基准if (arr[j] pivot) {i; // 增加较小元素的索引swap(arr[i], arr[j]);}}swap(arr[i 1], arr[high]); // 将基准元素放到正确的位置return (i 1);
}// 快速排序的递归函数
void quickSort(int arr[], int low, int high) {if (low high) {// pi是分区点arr[pi]已经排好序int pi partition(arr, low, high);// 递归地对分区点左边和右边的子数组进行排序quickSort(arr, low, pi - 1);quickSort(arr, pi 1, high);}
}// 打印数组
void printArray(int arr[], int size) {for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);
}// 主函数
int main() {int arr[] {10, 7, 8, 9, 1, 5};int n sizeof(arr) / sizeof(arr[0]);printf(原始数组: \n);printArray(arr, n);quickSort(arr, 0, n - 1);printf(排序后的数组: \n);printArray(arr, n);return 0;
}代码说明
swap函数用于交换两个元素的值。partition函数选择数组的最后一个元素作为基准pivot然后将数组分为两部分左边部分的元素都小于或等于基准右边部分的元素都大于基准。最后返回基准元素的正确位置。quickSort函数递归地对数组进行排序。首先通过partition函数找到分区点然后对分区点左边和右边的子数组分别进行快速排序。printArray函数用于打印数组的内容。main函数测试快速排序的实现。
运行结果
原始数组:
10 7 8 9 1 5
排序后的数组:
1 5 7 8 9 10 时间复杂度
平均时间复杂度O(n log n)最坏时间复杂度O(n^2)当数组已经有序或所有元素相等时空间复杂度O(log n)递归栈的深度
快速排序是一种非常高效的排序算法尤其适用于大规模数据的排序。
冒泡排序
冒泡排序Bubble Sort是一种简单的排序算法它重复地遍历数组比较相邻的元素并交换它们的位置直到整个数组有序。以下是使用C语言实现数组的冒泡排序的代码
#include stdio.h// 交换两个元素的值
void swap(int* a, int* b) {int temp *a;*a *b;*b temp;
}// 冒泡排序函数
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[j 1]) {swap(arr[j], arr[j 1]); // 如果顺序错误交换元素}}}
}// 打印数组
void printArray(int arr[], int size) {for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);
}// 主函数
int main() {int arr[] {64, 34, 25, 12, 22, 11, 90};int n sizeof(arr) / sizeof(arr[0]);printf(原始数组: \n);printArray(arr, n);bubbleSort(arr, n);printf(排序后的数组: \n);printArray(arr, n);return 0;
}代码说明
swap函数用于交换两个元素的值。bubbleSort函数 外层循环控制遍历次数每次遍历会将当前未排序部分的最大值“冒泡”到正确的位置。内层循环比较相邻元素如果顺序错误前一个元素大于后一个元素则交换它们。 printArray函数用于打印数组的内容。main函数测试冒泡排序的实现。 运行结果
原始数组:
64 34 25 12 22 11 90
排序后的数组:
11 12 22 25 34 64 90 优化版本
如果某次遍历中没有发生任何交换说明数组已经有序可以提前结束排序。以下是优化后的冒泡排序代码
void bubbleSortOptimized(int arr[], int n) {int swapped; // 标记是否发生交换for (int i 0; i n - 1; i) {swapped 0; // 每次遍历前重置标记for (int j 0; j n - i - 1; j) {if (arr[j] arr[j 1]) {swap(arr[j], arr[j 1]);swapped 1; // 发生交换标记为1}}if (swapped 0) { // 如果没有发生交换说明数组已经有序break;}}
}时间复杂度
最坏情况O(n²)当数组完全逆序时最好情况O(n)当数组已经有序时优化版本可以达到平均情况O(n²) 空间复杂度
O(1)原地排序不需要额外空间 冒泡排序虽然简单但在实际应用中效率较低通常用于教学或小规模数据的排序。对于大规模数据更高效的排序算法如快速排序、归并排序等更为适用。
插入排序
插入排序Insertion Sort是一种简单直观的排序算法。它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。以下是使用C语言实现数组的插入排序的代码 插入排序代码实现
#include stdio.h// 插入排序函数
void insertionSort(int arr[], int n) {int i, j, key;for (i 1; i n; i) {key arr[i]; // 当前需要插入的元素j i - 1;// 将比key大的元素向后移动while (j 0 arr[j] key) {arr[j 1] arr[j];j--;}arr[j 1] key; // 插入key到正确位置}
}// 打印数组
void printArray(int arr[], int size) {for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);
}// 主函数
int main() {int arr[] {12, 11, 13, 5, 6};int n sizeof(arr) / sizeof(arr[0]);printf(原始数组: \n);printArray(arr, n);insertionSort(arr, n);printf(排序后的数组: \n);printArray(arr, n);return 0;
}代码说明
insertionSort函数 从第二个元素开始i 1将当前元素key插入到已排序部分的正确位置。使用while循环将比key大的元素向后移动直到找到key的正确位置。将key插入到正确位置。 printArray函数用于打印数组的内容。main函数测试插入排序的实现。 运行结果
原始数组:
12 11 13 5 6
排序后的数组:
5 6 11 12 13 时间复杂度
最坏情况O(n²)当数组完全逆序时最好情况O(n)当数组已经有序时平均情况O(n²) 空间复杂度
O(1)原地排序不需要额外空间 插入排序的特点
适合小规模数据对于小规模数据或部分有序的数据插入排序的效率较高。稳定排序插入排序是稳定的排序算法相同元素的相对顺序不会改变。简单直观实现简单易于理解和实现。 优化版本
插入排序可以通过二分查找来优化查找插入位置的过程将查找时间从O(n)优化到O(log n)但整体时间复杂度仍然是O(n²)。
// 使用二分查找优化插入排序
void insertionSortOptimized(int arr[], int n) {int i, j, key, low, high, mid;for (i 1; i n; i) {key arr[i];low 0;high i - 1;// 使用二分查找找到插入位置while (low high) {mid (low high) / 2;if (arr[mid] key) {high mid - 1;} else {low mid 1;}}// 将元素向后移动for (j i - 1; j low; j--) {arr[j 1] arr[j];}arr[low] key; // 插入key到正确位置}
}插入排序在实际应用中常用于小规模数据排序或作为其他排序算法如快速排序、归并排序的辅助排序方法。
选择排序
选择排序Selection Sort是一种简单直观的排序算法。它的工作原理是每次从未排序部分中选择最小或最大的元素将其放到已排序部分的末尾。以下是使用C语言实现数组的选择排序的代码 选择排序代码实现
#include stdio.h// 交换两个元素的值
void swap(int* a, int* b) {int temp *a;*a *b;*b temp;
}// 选择排序函数
void selectionSort(int arr[], int n) {int i, j, min_idx;for (i 0; i n - 1; i) {min_idx i; // 假设当前索引i是最小元素的索引// 在未排序部分中找到最小元素的索引for (j i 1; j n; j) {if (arr[j] arr[min_idx]) {min_idx j;}}// 将找到的最小元素与当前元素交换if (min_idx ! i) {swap(arr[min_idx], arr[i]);}}
}// 打印数组
void printArray(int arr[], int size) {for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);
}// 主函数
int main() {int arr[] {64, 25, 12, 22, 11};int n sizeof(arr) / sizeof(arr[0]);printf(原始数组: \n);printArray(arr, n);selectionSort(arr, n);printf(排序后的数组: \n);printArray(arr, n);return 0;
}代码说明
swap函数用于交换两个元素的值。selectionSort函数 外层循环从第一个元素开始依次选择未排序部分的最小元素。内层循环在未排序部分中找到最小元素的索引。将找到的最小元素与当前元素交换。 printArray函数用于打印数组的内容。main函数测试选择排序的实现。 运行结果
原始数组:
64 25 12 22 11
排序后的数组:
11 12 22 25 64 时间复杂度
最坏情况O(n²)无论数组是否有序都需要进行完整的比较和交换最好情况O(n²)即使数组已经有序仍然需要进行完整的比较平均情况O(n²) 空间复杂度
O(1)原地排序不需要额外空间 选择排序的特点
简单直观实现简单易于理解和实现。不稳定排序选择排序是不稳定的排序算法可能会改变相同元素的相对顺序。适合小规模数据对于小规模数据选择排序的效率尚可但对于大规模数据效率较低。 优化版本
选择排序的优化空间较小但可以通过同时选择最小和最大元素来减少外层循环的次数。
// 优化版本同时选择最小和最大元素
void selectionSortOptimized(int arr[], int n) {int i, j, min_idx, max_idx;for (i 0; i n / 2; i) {min_idx i;max_idx i;// 在未排序部分中找到最小和最大元素的索引for (j i 1; j n - i; j) {if (arr[j] arr[min_idx]) {min_idx j;}if (arr[j] arr[max_idx]) {max_idx j;}}// 将最小元素放到前面if (min_idx ! i) {swap(arr[min_idx], arr[i]);}// 如果最大元素的位置被影响需要更新max_idxif (max_idx i) {max_idx min_idx;}// 将最大元素放到后面if (max_idx ! n - i - 1) {swap(arr[max_idx], arr[n - i - 1]);}}
}选择排序虽然简单但在实际应用中效率较低通常用于教学或小规模数据的排序。对于大规模数据更高效的排序算法如快速排序、归并排序等更为适用。
归并排序
归并排序Merge Sort是一种高效的排序算法采用分治法Divide and Conquer策略。它的核心思想是将数组分成两个子数组分别对子数组进行排序然后将排序后的子数组合并成一个有序数组。以下是使用C语言实现数组的归并排序的代码 归并排序代码实现
#include stdio.h
#include stdlib.h// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {int i, j, k;int n1 mid - left 1; // 左子数组的大小int n2 right - mid; // 右子数组的大小// 创建临时数组int* L (int*)malloc(n1 * sizeof(int)); // 左子数组int* R (int*)malloc(n2 * sizeof(int)); // 右子数组// 将数据复制到临时数组for (i 0; i n1; i) {L[i] arr[left i];}for (j 0; j n2; j) {R[j] arr[mid 1 j];}// 合并临时数组到原数组i 0; // 左子数组的索引j 0; // 右子数组的索引k left; // 合并后数组的索引while (i n1 j n2) {if (L[i] R[j]) {arr[k] L[i];i;} else {arr[k] R[j];j;}k;}// 复制左子数组剩余的元素while (i n1) {arr[k] L[i];i;k;}// 复制右子数组剩余的元素while (j n2) {arr[k] R[j];j;k;}// 释放临时数组的内存free(L);free(R);
}// 归并排序的递归函数
void mergeSort(int arr[], int left, int right) {if (left right) {int mid left (right - left) / 2; // 计算中间位置// 递归地对左子数组和右子数组进行排序mergeSort(arr, left, mid);mergeSort(arr, mid 1, right);// 合并两个有序子数组merge(arr, left, mid, right);}
}// 打印数组
void printArray(int arr[], int size) {for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);
}// 主函数
int main() {int arr[] {12, 11, 13, 5, 6, 7};int n sizeof(arr) / sizeof(arr[0]);printf(原始数组: \n);printArray(arr, n);mergeSort(arr, 0, n - 1);printf(排序后的数组: \n);printArray(arr, n);return 0;
}代码说明
merge函数 合并两个有序子数组L和R到原数组arr中。使用临时数组存储子数组的数据然后按顺序合并到原数组。 mergeSort函数 递归地将数组分成两个子数组分别对子数组进行排序。调用merge函数合并两个有序子数组。 printArray函数用于打印数组的内容。main函数测试归并排序的实现。 运行结果
原始数组:
12 11 13 5 6 7
排序后的数组:
5 6 7 11 12 13 时间复杂度
最坏情况O(n log n)最好情况O(n log n)平均情况O(n log n) 空间复杂度
O(n)需要额外的临时数组存储数据 归并排序的特点
稳定排序归并排序是稳定的排序算法相同元素的相对顺序不会改变。适合大规模数据归并排序的时间复杂度为O(n log n)适合处理大规模数据。分治法思想通过递归将问题分解为更小的子问题然后合并结果。 优化版本
归并排序可以通过以下方式优化
小规模数据使用插入排序当子数组规模较小时插入排序的效率更高。避免频繁的内存分配可以预先分配一个临时数组避免在每次合并时分配内存。
// 优化版本预先分配临时数组
void mergeSortOptimized(int arr[], int left, int right, int* temp) {if (left right) {int mid left (right - left) / 2;// 递归地对左子数组和右子数组进行排序mergeSortOptimized(arr, left, mid, temp);mergeSortOptimized(arr, mid 1, right, temp);// 合并两个有序子数组merge(arr, left, mid, right);}
}归并排序是一种非常高效的排序算法尤其适用于需要稳定排序的场景或处理大规模数据。
堆排序
堆排序Heap Sort是一种基于二叉堆Binary Heap数据结构的排序算法。它的核心思想是将数组构建成一个最大堆或最小堆然后逐步将堆顶元素最大值或最小值与堆的最后一个元素交换并调整堆直到整个数组有序。以下是使用C语言实现数组的堆排序的代码 堆排序代码实现
#include stdio.h// 交换两个元素的值
void swap(int* a, int* b) {int temp *a;*a *b;*b temp;
}// 调整堆使其满足最大堆的性质
void heapify(int arr[], int n, int i) {int largest i; // 初始化最大值的索引为根节点int left 2 * i 1; // 左子节点的索引int right 2 * i 2; // 右子节点的索引// 如果左子节点比根节点大更新最大值的索引if (left n arr[left] arr[largest]) {largest left;}// 如果右子节点比当前最大值大更新最大值的索引if (right n arr[right] arr[largest]) {largest right;}// 如果最大值不是根节点交换根节点和最大值并递归调整堆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); // 调整堆使其满足最大堆的性质}
}// 打印数组
void printArray(int arr[], int size) {for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);
}// 主函数
int main() {int arr[] {12, 11, 13, 5, 6, 7};int n sizeof(arr) / sizeof(arr[0]);printf(原始数组: \n);printArray(arr, n);heapSort(arr, n);printf(排序后的数组: \n);printArray(arr, n);return 0;
}代码说明
swap函数用于交换两个元素的值。heapify函数 调整堆使其满足最大堆的性质。从根节点开始比较根节点与其左右子节点找到最大值。如果最大值不是根节点交换根节点和最大值并递归调整堆。 heapSort函数 构建最大堆从最后一个非叶子节点开始逐步调整堆。逐步将堆顶元素最大值与堆的最后一个元素交换并调整堆。 printArray函数用于打印数组的内容。main函数测试堆排序的实现。 运行结果
原始数组:
12 11 13 5 6 7
排序后的数组:
5 6 7 11 12 13 时间复杂度
建堆过程O(n)每次调整堆O(log n)总时间复杂度O(n log n) 空间复杂度
O(1)原地排序不需要额外空间 堆排序的特点
不稳定排序堆排序是不稳定的排序算法可能会改变相同元素的相对顺序。适合大规模数据堆排序的时间复杂度为O(n log n)适合处理大规模数据。基于二叉堆利用二叉堆的性质实现排序。 优化版本
堆排序的优化空间较小但可以通过以下方式改进
使用最小堆如果需要升序排序可以使用最小堆。减少交换次数在调整堆时可以减少不必要的交换操作。 堆排序是一种高效的排序算法尤其适用于需要原地排序的场景或处理大规模数据。
计数排序
计数排序Counting Sort是一种非比较型整数排序算法。它的核心思想是通过统计数组中每个元素的出现次数然后根据统计结果将元素放回正确的位置。计数排序适用于元素范围较小且已知的情况。以下是使用C语言实现数组的计数排序的代码 计数排序代码实现
#include stdio.h
#include stdlib.h// 计数排序函数
void countingSort(int arr[], int n) {// 找到数组中的最大值int max arr[0];for (int i 1; i n; i) {if (arr[i] max) {max arr[i];}}// 创建计数数组并初始化为0int* count (int*)calloc(max 1, sizeof(int));// 统计每个元素的出现次数for (int i 0; i n; i) {count[arr[i]];}// 将计数数组转换为前缀和数组for (int i 1; i max; i) {count[i] count[i - 1];}// 创建输出数组int* output (int*)malloc(n * sizeof(int));// 从后向前遍历原数组将元素放入输出数组的正确位置for (int i n - 1; i 0; i--) {output[count[arr[i]] - 1] arr[i];count[arr[i]]--;}// 将输出数组的内容复制回原数组for (int i 0; i n; i) {arr[i] output[i];}// 释放动态分配的内存free(count);free(output);
}// 打印数组
void printArray(int arr[], int size) {for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);
}// 主函数
int main() {int arr[] {4, 2, 2, 8, 3, 3, 1};int n sizeof(arr) / sizeof(arr[0]);printf(原始数组: \n);printArray(arr, n);countingSort(arr, n);printf(排序后的数组: \n);printArray(arr, n);return 0;
}代码说明
countingSort函数 找到数组中的最大值确定计数数组的大小。创建计数数组统计每个元素的出现次数。将计数数组转换为前缀和数组表示每个元素在输出数组中的位置。从后向前遍历原数组将元素放入输出数组的正确位置。将输出数组的内容复制回原数组。 printArray函数用于打印数组的内容。main函数测试计数排序的实现。 运行结果
原始数组:
4 2 2 8 3 3 1
排序后的数组:
1 2 2 3 3 4 8 时间复杂度
时间复杂度O(n k)其中n是数组长度k是数组中元素的最大值。空间复杂度O(n k)需要额外的计数数组和输出数组。 计数排序的特点
非比较排序计数排序不直接比较元素的大小而是通过统计元素的出现次数进行排序。稳定排序计数排序是稳定的排序算法相同元素的相对顺序不会改变。适合小范围整数排序计数排序适用于元素范围较小且已知的情况。 优化版本
计数排序的优化可以通过以下方式实现
减少空间占用如果元素范围较大可以使用哈希表或其他方法减少计数数组的大小。处理负数如果需要处理负数可以将数组中的元素统一加上一个偏移量使其变为非负数。
以下是处理负数的优化版本
void countingSortWithNegative(int arr[], int n) {// 找到数组中的最小值和最大值int 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];}}// 计算偏移量int range max - min 1;// 创建计数数组并初始化为0int* count (int*)calloc(range, sizeof(int));// 统计每个元素的出现次数for (int i 0; i n; i) {count[arr[i] - min];}// 将计数数组转换为前缀和数组for (int i 1; i range; i) {count[i] count[i - 1];}// 创建输出数组int* output (int*)malloc(n * sizeof(int));// 从后向前遍历原数组将元素放入输出数组的正确位置for (int i n - 1; i 0; i--) {output[count[arr[i] - min] - 1] arr[i];count[arr[i] - min]--;}// 将输出数组的内容复制回原数组for (int i 0; i n; i) {arr[i] output[i];}// 释放动态分配的内存free(count);free(output);
}计数排序是一种高效的排序算法尤其适用于元素范围较小的情况。对于元素范围较大的情况可以考虑使用其他排序算法如快速排序或归并排序。
基数排序
基数排序Radix Sort是一种非比较型整数排序算法。它的核心思想是将整数按位数切割成不同的数字然后按每个位数分别进行排序通常使用计数排序或桶排序作为子排序算法。基数排序适用于整数或字符串的排序。以下是使用C语言实现数组的基数排序的代码 基数排序代码实现
#include stdio.h
#include stdlib.h// 获取数组中的最大值
int getMax(int arr[], int n) {int max arr[0];for (int i 1; i n; i) {if (arr[i] max) {max arr[i];}}return max;
}// 使用计数排序对数组按指定位数进行排序
void countingSort(int arr[], int n, int exp) {int* output (int*)malloc(n * sizeof(int)); // 输出数组int count[10] {0}; // 计数数组初始化为0// 统计每个数字出现的次数for (int i 0; i n; i) {count[(arr[i] / exp) % 10];}// 将计数数组转换为前缀和数组for (int i 1; i 10; i) {count[i] count[i - 1];}// 从后向前遍历原数组将元素放入输出数组的正确位置for (int i n - 1; i 0; i--) {output[count[(arr[i] / exp) % 10] - 1] arr[i];count[(arr[i] / exp) % 10]--;}// 将输出数组的内容复制回原数组for (int i 0; i n; i) {arr[i] output[i];}// 释放动态分配的内存free(output);
}// 基数排序函数
void radixSort(int arr[], int n) {int max getMax(arr, n); // 获取数组中的最大值// 对每个位数进行计数排序for (int exp 1; max / exp 0; exp * 10) {countingSort(arr, n, exp);}
}// 打印数组
void printArray(int arr[], int size) {for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);
}// 主函数
int main() {int arr[] {170, 45, 75, 90, 802, 24, 2, 66};int n sizeof(arr) / sizeof(arr[0]);printf(原始数组: \n);printArray(arr, n);radixSort(arr, n);printf(排序后的数组: \n);printArray(arr, n);return 0;
}代码说明
getMax函数获取数组中的最大值用于确定需要排序的位数。countingSort函数 对数组按指定位数exp进行计数排序。使用计数数组统计每个数字出现的次数并将其转换为前缀和数组。从后向前遍历原数组将元素放入输出数组的正确位置。 radixSort函数 获取数组中的最大值确定需要排序的位数。对每个位数调用countingSort函数进行排序。 printArray函数用于打印数组的内容。main函数测试基数排序的实现。 运行结果
原始数组:
170 45 75 90 802 24 2 66
排序后的数组:
2 24 45 66 75 90 170 802 时间复杂度
时间复杂度O(d * (n k))其中d是最大数字的位数n是数组长度k是基数通常为10。空间复杂度O(n k)需要额外的计数数组和输出数组。 基数排序的特点
非比较排序基数排序不直接比较元素的大小而是通过按位数排序。稳定排序基数排序是稳定的排序算法相同元素的相对顺序不会改变。适合整数或字符串排序基数排序适用于整数或固定长度的字符串排序。 优化版本
基数排序的优化空间较小但可以通过以下方式改进
使用桶排序在某些情况下可以使用桶排序代替计数排序作为子排序算法。处理负数如果需要处理负数可以将数组分为正数和负数两部分分别进行基数排序。 基数排序是一种高效的排序算法尤其适用于整数或字符串的排序场景。
桶排序
桶排序Bucket Sort是一种分布式排序算法它将数组分到有限数量的桶中每个桶再分别排序通常使用插入排序或其他排序算法最后将各个桶中的元素合并成有序数组。以下是使用C语言实现数组的桶排序的代码 桶排序代码实现
#include stdio.h
#include stdlib.h// 定义桶的数量
#define BUCKET_SIZE 10// 定义链表节点
typedef struct Node {float data;struct Node* next;
} Node;// 插入节点到链表中按升序插入
Node* insert(Node* head, float value) {Node* newNode (Node*)malloc(sizeof(Node));newNode-data value;newNode-next NULL;if (head NULL || head-data value) {newNode-next head;head newNode;} else {Node* current head;while (current-next ! NULL current-next-data value) {current current-next;}newNode-next current-next;current-next newNode;}return head;
}// 桶排序函数
void bucketSort(float arr[], int n) {// 创建桶数组Node* buckets[BUCKET_SIZE] {NULL};// 将元素分配到桶中for (int i 0; i n; i) {int bucketIndex (int)(arr[i] * BUCKET_SIZE); // 计算桶的索引buckets[bucketIndex] insert(buckets[bucketIndex], arr[i]);}// 将桶中的元素合并到原数组int index 0;for (int i 0; i BUCKET_SIZE; i) {Node* current buckets[i];while (current ! NULL) {arr[index] current-data;current current-next;}}
}// 打印数组
void printArray(float arr[], int size) {for (int i 0; i size; i) {printf(%.2f , arr[i]);}printf(\n);
}// 主函数
int main() {float arr[] {0.42, 0.32, 0.75, 0.12, 0.89, 0.63, 0.25, 0.55};int n sizeof(arr) / sizeof(arr[0]);printf(原始数组: \n);printArray(arr, n);bucketSort(arr, n);printf(排序后的数组: \n);printArray(arr, n);return 0;
}代码说明
Node结构体定义链表节点用于存储桶中的元素。insert函数 将元素按升序插入到链表中。如果链表为空或当前元素小于链表头节点则插入到链表头部。否则遍历链表找到合适的插入位置。 bucketSort函数 创建桶数组每个桶是一个链表。将数组中的元素分配到对应的桶中。对每个桶中的元素进行排序通过插入排序实现。将各个桶中的元素合并到原数组。 printArray函数用于打印数组的内容。main函数测试桶排序的实现。 运行结果
原始数组:
0.42 0.32 0.75 0.12 0.89 0.63 0.25 0.55
排序后的数组:
0.12 0.25 0.32 0.42 0.55 0.63 0.75 0.89 时间复杂度
平均情况O(n k)其中n是数组长度k是桶的数量。最坏情况O(n²)当所有元素都分配到同一个桶时。最好情况O(n)当元素均匀分布在各个桶中时。 空间复杂度
O(n k)需要额外的桶数组和链表节点。 桶排序的特点
分布式排序将元素分配到多个桶中分别排序后再合并。适合均匀分布的数据当元素均匀分布在各个桶中时桶排序的效率较高。稳定排序如果使用的子排序算法是稳定的桶排序也是稳定的。 优化版本
桶排序的优化可以通过以下方式实现
动态调整桶的数量根据数据的分布动态调整桶的数量避免所有元素都分配到同一个桶中。使用更高效的子排序算法例如使用快速排序或归并排序代替插入排序。 桶排序是一种高效的排序算法尤其适用于数据分布均匀的场景。对于非均匀分布的数据桶排序的性能可能会下降。
希尔排序
希尔排序Shell Sort是插入排序的一种改进版本也称为缩小增量排序。它的核心思想是通过将数组分成若干个子序列对每个子序列进行插入排序然后逐步缩小子序列的间隔最终对整个数组进行一次插入排序。希尔排序的时间复杂度优于普通的插入排序。以下是使用C语言实现数组的希尔排序的代码 希尔排序代码实现
#include stdio.h// 希尔排序函数
void shellSort(int arr[], int n) {// 初始间隔gap为数组长度的一半逐步缩小间隔for (int gap n / 2; gap 0; gap / 2) {// 对每个子序列进行插入排序for (int i gap; i n; i) {int temp arr[i]; // 当前需要插入的元素int j;// 将比temp大的元素向后移动for (j i; j gap arr[j - gap] temp; j - gap) {arr[j] arr[j - gap];}arr[j] temp; // 插入temp到正确位置}}
}// 打印数组
void printArray(int arr[], int size) {for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);
}// 主函数
int main() {int arr[] {12, 34, 54, 2, 3};int n sizeof(arr) / sizeof(arr[0]);printf(原始数组: \n);printArray(arr, n);shellSort(arr, n);printf(排序后的数组: \n);printArray(arr, n);return 0;
}代码说明
shellSort函数 初始间隔gap为数组长度的一半逐步缩小间隔。对每个子序列进行插入排序。将比当前元素大的元素向后移动直到找到当前元素的正确位置。 printArray函数用于打印数组的内容。main函数测试希尔排序的实现。 运行结果
原始数组:
12 34 54 2 3
排序后的数组:
2 3 12 34 54 时间复杂度
最坏情况O(n²)取决于间隔序列的选择。平均情况O(n log n) 到 O(n^(3/2))。最好情况O(n log n)。 空间复杂度
O(1)原地排序不需要额外空间。 希尔排序的特点
改进的插入排序通过分组插入排序减少了元素的移动次数。不稳定排序希尔排序是不稳定的排序算法可能会改变相同元素的相对顺序。适合中等规模数据希尔排序的效率高于普通的插入排序适合中等规模的数据排序。 优化版本
希尔排序的性能取决于间隔序列的选择。常见的间隔序列有
希尔原始序列gap n / 2, gap / 2。Hibbard序列gap 2^k - 1。Sedgewick序列gap 9 * 4^i - 9 * 2^i 1 或 gap 4^i 3 * 2^i 1。
以下是使用Hibbard序列的优化版本
// 使用Hibbard序列的希尔排序
void shellSortHibbard(int arr[], int n) {// 计算Hibbard序列的最大值int k 1;while ((1 k) - 1 n) {k;}// 使用Hibbard序列作为间隔for (int gap (1 k) - 1; gap 0; gap (1 (--k)) - 1) {for (int i gap; i n; i) {int temp arr[i];int j;for (j i; j gap arr[j - gap] temp; j - gap) {arr[j] arr[j - gap];}arr[j] temp;}}
}希尔排序是一种高效的排序算法尤其适用于中等规模数据的排序。通过选择合适的间隔序列可以进一步提高其性能。
总结
以下是常见排序算法的比较表格包括时间复杂度、空间复杂度、稳定性以及适用场景等信息
排序算法平均时间复杂度最坏时间复杂度最好时间复杂度空间复杂度是否稳定适用场景QuickO(n log n)O(n²)O(n log n)O(log n)不稳定大规模数据通用排序BubbleO(n²)O(n²)O(n)O(1)稳定小规模数据教学用途InsertO(n²)O(n²)O(n)O(1)稳定小规模或部分有序数据SelectO(n²)O(n²)O(n²)O(1)不稳定小规模数据简单实现MergeO(n log n)O(n log n)O(n log n)O(n)稳定大规模数据稳定排序需求HeapO(n log n)O(n log n)O(n log n)O(1)不稳定大规模数据原地排序需求CountO(n k)O(n k)O(n k)O(n k)稳定小范围整数排序RadixO(d(n k))O(d(n k))O(d(n k))O(n k)稳定整数或字符串排序位数较小BucketO(n k)O(n²)O(n)O(n k)稳定均匀分布的数据ShellO(n log n)O(n²)O(n log n)O(1)不稳定中等规模数据改进的插入排序 表格说明
时间复杂度 平均算法在大多数情况下的性能。最坏算法在最差情况下的性能。最好算法在最优情况下的性能。 空间复杂度算法所需的额外空间。稳定性排序后相同元素的相对顺序是否保持不变。适用场景算法最适合的应用场景。 总结
Quick Sort通用高效适合大规模数据但不稳定。Bubble Sort简单但效率低适合小规模数据或教学用途。Insertion Sort适合小规模或部分有序数据稳定。Selection Sort简单但效率低适合小规模数据。Merge Sort稳定且高效适合大规模数据但需要额外空间。Heap Sort原地排序适合大规模数据但不稳定。Counting Sort适合小范围整数排序稳定。Radix Sort适合整数或字符串排序稳定。Bucket Sort适合均匀分布的数据稳定。Shell Sort改进的插入排序适合中等规模数据。
根据具体需求选择合适的排序算法可以提高程序的效率。
