C语言实现:排序算法详解——冒泡、选择与快速排序

需积分: 9 5 下载量 165 浏览量 更新于2024-11-19 收藏 34KB DOC 举报
"这篇文档汇总了三种经典的排序算法在C语言中的实现,包括冒泡排序、简单选择排序和快速排序。这些排序算法都是用于对数组或列表进行升序排列的常用方法,通过比较元素间的值并进行必要的交换来达到排序的目的。" **冒泡排序** 冒泡排序的核心思想是通过多次遍历列表,每次比较相邻的两个元素,如果它们的顺序错误(即前者大于后者),则交换这两个元素的位置。这个过程会不断重复,直到没有更多的交换操作,即列表已经完全排序。冒泡排序的时间复杂度为O(n^2),空间复杂度为O(1)。在C语言中的实现如下: ```c bubblesort(struct rec r[], int n) { int i, j; struct rec w; unsigned long int compare = 0, move = 0; // 遍历并交换 for (i = 1; i <= n - 1; i++) { for (j = n; j >= i + 1; j--) { if (r[j].key < r[j - 1].key) { w = r[j]; r[j] = r[j - 1]; r[j - 1] = w; move += 3; } compare++; } } printf("\nBubbleSort compare=%ld, move=%ld\n", compare, move); } ``` **简单选择排序** 简单选择排序的工作原理是每次从未排序的元素中找到最小的元素,然后将其与未排序部分的第一个元素交换。这个过程会持续到所有元素都有序。简单选择排序的时间复杂度也为O(n^2),空间复杂度为O(1)。C语言实现如下: ```c selectsort(struct rec r[], int n) { unsigned long int compare = 0, move = 0; int i, j, k; struct rec w; // 搜索最小元素并交换 for (i = 1; i <= n - 1; i++) { k = i; for (j = i + 1; j <= n; j++) { if (r[j].key < r[k].key) { k = j; compare++; } } w = r[i]; r[i] = r[k]; r[k] = w; move += 3; } printf("\nSelectSort compare=%ld, move=%ld\n", compare, move); } ``` **快速排序** 快速排序是一种分治策略的排序算法,它选取一个“分割点”将列表分为两部分,一部分的所有元素都小于另一部分。然后对这两部分递归地进行快速排序。快速排序的平均时间复杂度为O(n log n),最坏情况下为O(n^2),但实际应用中性能通常优于冒泡排序和简单选择排序。C语言实现如下: ```c void q(struct rec r[], int s, int t) { int i = s, j = t; if (s < t) { r[0] = r[s]; // 分割点 // 分割并交换 do { while (j > i && r[j].key >= r[0].key) { j--; // ... } // ... } while (/* ... */); // ... } } ``` 快速排序的完整实现通常还包括交换元素、分割点的选择以及递归调用等步骤,这里仅给出了部分代码片段。 这三种排序算法各有优缺点,冒泡排序和简单选择排序实现简单,但效率较低;快速排序在大多数情况下表现出较好的性能,但最坏情况下的效率较低。在实际编程中,根据具体应用场景和数据特性,可以选择合适的排序算法。
手机看
程序员都在用的中文IT技术交流社区

程序员都在用的中文IT技术交流社区

专业的中文 IT 技术社区,与千万技术人共成长

专业的中文 IT 技术社区,与千万技术人共成长

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

客服 返回
顶部