东莞企业制作网站,网站的seo如何优化,深圳高端设计公司名单,宜城网站建设哪家好题目:C语言实现排序算法
冒泡排序
思路#xff1a;
依次比较相邻的元素#xff0c;如果顺序不对则交换#xff0c;直到整个数组有序。
实现代码#xff1a;
#include stdio.hvoid bubbleSort(int arr[], int n) {for (int i 0; i n - 1; i) {for (int j…题目:C语言实现排序算法
冒泡排序
思路
依次比较相邻的元素如果顺序不对则交换直到整个数组有序。
实现代码
#include stdio.hvoid 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]) {int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}}
}int main() {int arr[] {64, 34, 25, 12, 22, 11, 90, 87, 10, 5};int n sizeof(arr) / sizeof(arr[0]);bubbleSort(arr, n);printf(排序后的数组: );for (int i 0; i n; i)printf(%d , arr[i]);return 0;
}优缺点
优点实现简单。缺点对于大规模数据排序效率低时间复杂度为O(n^2)。
选择排序
思路
从未排序的部分选择最小元素与未排序部分的第一个元素交换位置。重复这个过程直到整个数组有序。
实现代码
#include stdio.hvoid selectionSort(int arr[], int n) {int i, j, min_idx, temp;for (i 0; i n - 1; i) {min_idx i;for (j i 1; j n; j)if (arr[j] arr[min_idx])min_idx j;temp arr[min_idx];arr[min_idx] arr[i];arr[i] temp;}
}int main() {int arr[] {64, 34, 25, 12, 22, 11, 90, 87, 10, 5};int n sizeof(arr) / sizeof(arr[0]);selectionSort(arr, n);printf(排序后的数组: );for (int i 0; i n; i)printf(%d , arr[i]);return 0;
}优缺点
优点实现简单。缺点对于大规模数据排序效率低时间复杂度为O(n^2)。
插入排序
思路
将数组分为已排序和未排序两部分逐步将未排序的元素插入到已排序的部分直到整个数组有序。
实现代码
#include stdio.hvoid insertionSort(int arr[], int n) {int i, key, j;for (i 1; i n; i) {key arr[i];j i - 1;while (j 0 arr[j] key) {arr[j 1] arr[j];j j - 1;}arr[j 1] key;}
}int main() {int arr[] {64, 34, 25, 12, 22, 11, 90, 87, 10, 5};int n sizeof(arr) / sizeof(arr[0]);insertionSort(arr, n);printf(排序后的数组: );for (int i 0; i n; i)printf(%d , arr[i]);return 0;
}优缺点
优点简单对小规模数据或接近有序的数据排序效率高。缺点对于大规模数据排序效率低时间复杂度为O(n^2)。
归并排序
思路
将数组递归分成子数组然后合并这些子数组合并过程中保持有序。
实现代码
#include stdio.h
#include stdlib.hvoid merge(int arr[], int left, int middle, int right) {int n1 middle - left 1;int n2 right - middle;int L[n1], R[n2];for (int i 0; i n1; i)L[i] arr[left i];for (int j 0; j n2; j)R[j] arr[middle 1 j];int 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;}
}void mergeSort(int arr[], int left, int right) {if (left right) {int middle left (right - left) / 2;mergeSort(arr, left, middle);mergeSort(arr, middle 1, right);merge(arr, left, middle, right);}
}int main() {int arr[] {64, 34, 25, 12, 22, 11, 90, 87, 10, 5};int n sizeof(arr) / sizeof(arr[0]);mergeSort(arr, 0, n - 1);printf(排序后的数组: );for (int i 0; i n; i)printf(%d , arr[i]);return 0;
}优缺点
优点稳定时间复杂度为O(n log n)。缺点需要额外的内存空间。
快速排序
思路
选择一个基准元素将数组分为小于基准和大于基准的两部分然后递归地对这两部分进行排序。
实现代码
#include stdio.hvoid swap(int* a, int* b) {int t *a;*a *b;*b t;
}int partition(int arr[], int low, int high) {int pivot arr[high];int i low - 1;for (int j low; j high; 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) {int pi partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi 1, high);}
}int main() {int arr[] {64, 34, 25, 12, 22, 11, 90, 87, 10, 5};int n sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);printf(排序后的数组: );for (int i 0; i n; i)printf(%d , arr[i]);return 0;
}优缺点
优点效率高时间复杂度平均情况下为O(n log n)。缺点不稳定。
希尔排序
思路
将数组按一定间隔分组对每组使用插入排序。缩小间隔重复上述步骤直到间隔为1进行最后一次插入排序。
实现代码
#include stdio.hvoid shellSort(int arr[], int n) {for (int gap n / 2; gap 0; gap / 2) {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;}}
}int main() {int arr[] {64, 34, 25, 12, 22, 11, 90, 87, 10, 5};int n sizeof(arr) / sizeof(arr[0]);shellSort(arr, n);printf(排序后的数组: );for (int i 0; i n; i)printf(%d , arr[i]);return 0;
}优缺点
优点相对于简单排序算法有较高的效率时间复杂度受增量序列的影响。缺点不稳定。
堆排序
思路
构建最大堆或最小堆将堆顶元素与最后一个元素交换然后将堆的大小减一并重新维护堆的性质。重复此过程直到堆为空得到有序数组。
实现代码
#include stdio.hvoid 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) {int temp arr[i];arr[i] arr[largest];arr[largest] temp;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--) {int temp arr[0];arr[0] arr[i];arr[i] temp;heapify(arr, i, 0);}
}int main() {int arr[] {64, 34, 25, 12, 22, 11, 90, 87, 10, 5};int n sizeof(arr) / sizeof(arr[0]);heapSort(arr, n);printf(排序后的数组: );for (int i 0; i n; i)printf(%d , arr[i]);return 0;
}优缺点
优点高效的原地排序算法时间复杂度为O(n log n)。缺点不稳定。
计数排序
思路
统计数组中每个元素的出现次数然后根据元素值和出现次数重新构建数组。
实现代码
#include stdio.h
#include stdlib.hvoid countSort(int arr[], int n) {int max arr[0];for (int i 1; i n; i) {if (arr[i] max)max arr[i];}int* count (int*)malloc((max 1) * sizeof(int));int* output (int*)malloc(n * sizeof(int));for (int i 0; i max; i)count[i] 0;for (int i 0; i n; i)count[arr[i]];for (int i 1; i max; i)count[i] count[i - 1];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);
}int main() {int arr[] {4, 2, 2, 8, 3, 3, 1, 5, 9};int n sizeof(arr) / sizeof(arr[0]);countSort(arr, n);printf(排序后的数组: );for (int i 0; i n; i)printf(%d , arr[i]);return 0;
}优缺点
优点适用于元素范围不大的情况时间复杂度为O(n k)k为最大元素值。缺点对于元素范围很大的数据效率较低。
总结和推荐
推荐的排序算法归并排序和快速排序归并排序和快速排序都是高效的排序算法时间复杂度为O(n log n)适用于各种规模的数据集。归并排序是稳定的但需要额外的内存空间适用于所有数据类型。快速排序是不稳定的但在实践中通常比归并排序更快适用于大规模数据集。
这里推荐归并排序作为首选因为它是稳定的且不会对原始数据造成修改。如果在内存受限的情况下考虑可以选择快速排序。Bubble Sort、Selection Sort 和 Insertion Sort 适用于小规模数据集或教学目的不推荐用于实际应用。
