实现直接排序,冒泡,直接选择,快速,堆,并归排序算法,比较各种算法的运算速度。
3条回答 默认 最新
关注 【以下回答由 GPT 生成】
利用C语言程序解决排序问题 - 比较不同排序算法的运算速度
1. 实现排序算法
直接排序 (Insertion Sort)
直接排序是一种简单的排序算法,通过将数组分为已排序和未排序两部分。每次从未排序部分取出一个元素,插入到已排序部分的正确位置。重复这个过程直到整个数组排序完成。
#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; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } }
冒泡排序 (Bubble Sort)
冒泡排序是一种简单的排序算法,它重复地遍历数组,比较每对相邻元素,如果前一个元素大于后一个元素,则交换它们,直到整个数组排序完成。
#include <stdio.h> void bubbleSort(int arr[], int n) { int i, j, temp; for (i = 0; i < n-1; i++) { for (j = 0; j < n-i-1; j++) { if (arr[j] > arr[j+1]) { temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }
直接选择排序 (Selection Sort)
直接选择排序是一种简单的排序算法,它通过重复选择未排序部分的最小元素,并将其放置在已排序部分的末尾。重复这个过程直到整个数组排序完成。
#include <stdio.h> void selectionSort(int arr[], int n) { int i, j, minIndex, temp; for (i = 0; i < n-1; i++) { minIndex = i; for (j = i+1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } }
快速排序 (Quick Sort)
快速排序是一种常用的基于分治法的排序算法。它通过选择一个"基准"元素,将数组分为两个子数组,小于基准的元素在左边,大于基准的元素在右边。然后递归地对子数组进行排序。
#include <stdio.h> int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low - 1); int j, temp; for (j = low; j <= high - 1; j++) { if (arr[j] < pivot) { i++; temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; 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); } }
堆排序 (Heap Sort)
堆排序是一种基于堆数据结构的排序算法。它通过构建一个最大堆或最小堆,并重复从堆中移除堆顶元素,直到堆为空,被移除的元素按顺序组成已排序数组。
#include <stdio.h> void heapify(int arr[], int n, int i) { int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; int temp; if (l < n && arr[l] > arr[largest]) { largest = l; } if (r < n && arr[r] > arr[largest]) { largest = r; } if (largest != i) { temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, n, largest); } } void heapSort(int arr[], int n) { int i, temp; for (i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } for (i = n - 1; i >= 0; i--) { temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } }
归并排序 (Merge Sort)
归并排序是一种基于分治法的排序算法。它通过将数组递归地分为两个子数组,然后对子数组排序,并合并子数组以获得排序的数组。
#include <stdio.h> void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n2]; for (i = 0; i < n1; i++) { L[i] = arr[l + i]; } for (j = 0; j < n2; j++) { R[j] = arr[m + 1 + j]; } i = 0; j = 0; k = l; 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 l, int r) { if (l < r) { int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } }
2. 算法库和示例代码
对于这些排序算法,有很多开源的算法库和示例代码可供使用。
- 标准库:C语言的标准库(stdlib.h)提供了qsort函数,可以用于快速排序。
- GNU Scientific Library (GSL):GSL是一个开源的数学和科学计算库,提供了包括排序算法在内的许多常见算法。你可以在GSL官方网站找到更多信息和示例代码。
- 其他开源库:还有其他许多开源算法库可供选择,比如Algorithmia、ACM Collected Algorithms等。你可以通过搜索引擎找到更多选项。
3. 比较排序算法的运算速度
要比较不同排序算法的运算速度,可以使用计时函数测量它们的执行时间。下面是一个示例代码,用于比较直接排序和快速排序的运行时间。
#include <stdio.h> #include <time.h> // 直接排序 void insertionSort(int arr[], int n) { // 排序代码 } // 快速排序 void quickSort(int arr[], int low, int high) { // 排序代码 } // 测量运行时间 double measureTime(void (*sortFunction)(int[], int), int arr[], int n) { clock_t start, end; double cpu_time_used; start = clock(); sortFunction(arr, n); end = clock(); cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC; return cpu_time_used; } int main() { int arr1[] = {5, 4, 3, 2, 1}; int arr2[] = {5, 4, 3, 2, 1}; int n = sizeof(arr1) / sizeof(arr1[0]); double time1, time2; time1 = measureTime(insertionSort, arr1, n); time2 = measureTime(quickSort, arr2, 0, n-1); printf("直接排序的运行时间: %lf\n", time1); printf("快速排序的运行时间: %lf\n", time2); return 0; }
运行以上示例代码,将会输出直接排序和快速排序的运行时间。
请注意,排序算法的运行时间可能会受到多种因素的影响,如输入数组的大小和元素的分布情况。因此,为了得到更准确的结果,应该进行多次运行,并计算平均运行时间。
希望以上信息对解决你的问题有所帮助!如果还有其他问题,请随时提问。
【相关推荐】
- 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7667520
- 我还给你找了一篇非常好的博客,你可以看看是否有帮助,链接:【数据结构之排序系列】直接插入排序,冒泡排序,直接选择排序,堆排序,希尔排序
- 除此之外, 这篇博客: [ C语言 ] 还不懂指针的一定要进来,带你初始指针,简单使用指针,它没有你想的那么难。中的 部分也许能够解决你的问题。
如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^解决 1无用
悬赏问题
- ¥15 为啥画版图在Run DRC会出现Connect Error?可我Calibre的hostname和计算机的hostname已经设置成一样的了。
- ¥20 网站后台使用极速模式非常的卡
- ¥20 Keil uVision5创建project没反应
- ¥15 mmseqs内存报错
- ¥15 vika文档如何与obsidian同步
- ¥15 华为手机相册里面的照片能够替换成自己想要的照片吗?
- ¥15 陆空双模式无人机飞控设置
- ¥15 sentaurus lithography
- ¥100 求抖音ck号 或者提ck教程
- ¥15 关于#linux#的问题:子进程1等待子进程A、B退出后退出(语言-c语言)