C语言中冒泡排序算法详解

目录
  • 一、算法描述
  • 二、算法分析
  • 三、完整代码
  • 总结

一、算法描述

比较相邻两个元素，如果第一个比第二个大则交换两个值。遍历所有的元素，每一次都会将未排序序列中最大的元素放在后面。假设数组有 n 个元素，那么需要遍历 n - 1 次，因为剩下的一个元素一定是最小的，无需再遍历一次。因此需要两层循环，第一层是遍历次数，第二层是遍历未排序数组。

动图如下：

黄色部分表示已排好序的数组，蓝色部分表示未排序数组

核心代码如下：

/**
 * @brief 冒泡排序
 *
 * @param arr 待排序的数组
 * @param size 数组大小
 */
static void bubble_sort(int *arr, int size)
{
	for (int i = 0; i < size - 1; i++) {
		bool swapped = false; // 设置标记，用于检查是否已排好序
		for (int j = 0; j < size - i; j++)
			if (arr[j] > arr[j + 1]) {
				swap(arr + j, arr + j + 1);
				swapped = true;
			}
		if (!swapped) // 未交换则排序完毕，跳出循环
			break;
	}
}

布尔值 swapped 是一种优化手段，在每次遍历未排序数组之前将其设置为 false 表示还未交换。如果遍历完未排序数组之后其值还是 false 则表示遍历过程种没有发生交换，也就是说数组已经有序，无需再次遍历，跳出循环。

二、算法分析

时间复杂度：O(N2)，两层循环

空间复杂度：O(1)，交换元素时只用了一个临时变量

最好情况：O(N)，有序数组遍历一次后 swapped 为 false 退出循环

最坏情况：O(N2)，数组倒序

稳定性：稳定，比较两个元素大小时不包括元素相等的情况，故相等元素的相对位置不变

三、完整代码

/**
 * @file bubble_sort.c
 * @date 2022-01-16
 * @author Pineapple (pineapple_cpp@163.com)
 *
 * @brief 冒泡排序
 */

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/**
 * @brief 交换函数
 *
 * @param left 左边的元素
 * @param right 右边的元素
 */
static inline void swap(int *left, int *right)
{
	int temp = *left;
	*left = *right;
	*right = temp;
}

/**
 * @brief 冒泡排序
 *
 * @param arr 待排序的数组
 * @param size 数组大小
 */
static void bubble_sort(int *arr, int size)
{
	for (int i = 0; i < size - 1; i++) {
		bool swapped = false; // 设置标记，用于检查是否已排好序
		for (int j = 0; j < size - i; j++)
			if (arr[j] > arr[j + 1]) {
				swap(arr + j, arr + j + 1);
				swapped = true;
			}
		if (!swapped) // 未交换则排序完毕，跳出循环
			break;
	}
}

/**
 * @brief 测试函数
 *
 */
static void test()
{
	const int size = rand() % 500; // 生成随机数组大小
	int *arr = (int *)calloc(size, sizeof(int));

	// 生成范围 -50 到 49 的随机数组
	for (int i = 0; i < size; i++)
		arr[i] = rand() % 100 - 50;

	bubble_sort(arr, size);

	for (int i = 0; i < size - 1; i++)
		assert(arr[i] <= arr[i + 1]);

	free(arr);
}

int main(void)
{
	srand(time(NULL));
	test();
	return 0;
}

总结

到此这篇关于C语言中冒泡排序算法详解的文章就介绍到这了,更多相关C语言冒泡排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言每日练习之冒泡排序

    C语言每日练习之冒泡排序

    目录 分析 代码实现 运行结果 总结 分析 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法. 冒泡排序(这里只讨论从小到大排序)可以通过二种方式实现,分别是将最小值依次移动到头部和将最大值依次移动到尾部. 代码实现 代码采用从数组头部轮询的方式: #include <stdio.h> #define INTEGER_RANGE 10 //数字范围 void bubule_sort(int *array, int len); int main() { int i =

  • C语言对数组元素进行冒泡排序的实现

    在实际开发中,有很多场景需要我们将数组元素按照从大到小(或者从小到大)的顺序排列,这样在查阅数据时会更加直观,例如: 一个保存了班级学号的数组,排序后更容易分区好学生和坏学生: 一个保存了商品单价的数组,排序后更容易看出它们的性价比. 对数组元素进行排序的方法有很多种,比如冒泡排序.归并排序.选择排序.插入排序.快速排序等,其中最经典最需要掌握的是「冒泡排序」. 以从小到大排序为例,冒泡排序的整体思想是这样的: 从数组头部开始,不断比较相邻的两个元素的大小,让较大的元素逐渐往后移动(交换两个元素

  • 深入了解C语言冒泡排序优解

    深入了解C语言冒泡排序优解

    目录 1:直接冒泡 2:函数冒泡 3:冒泡优化 总结: 1:直接冒泡 #include<stdio.h> int main() { int i,j; int t; int a[]={10,9,8,7,6,5,4,3,2,1};//此排序实现顺序排序 int s=sizeof(a)/sizeof(a[0]);//求数组元素个数 for(i=0;i<s-1;i++)//确定排序的趟数 { //下面为每趟冒泡排序 for(j=0;j<s-1-i;j++) { if(a[j]>a[j

  • C语言冒泡排序算实现代码

    冒泡排序是排序算法的一种,思路清晰,代码简洁,常被用在大学生计算机课程中. "冒泡"这个名字的由来是因为越大的元素会经由交换慢慢"浮"到数列的顶端,故名. 这里以从小到大排序为例进行讲解. 基本思想及举例说明 冒泡排序的基本思想就是不断比较相邻的两个数,让较大的元素不断地往后移.经过一轮比较,就选出最大的数:经过第2轮比较,就选出次大的数,以此类推. 下面以对 3  2  4  1 进行冒泡排序说明. 第一轮 排序过程 3  2  4  1    (最初) 2  3

  • C语言 冒泡排序算法详解及实例

    C语言 冒泡排序算法详解及实例

    C语言 冒泡排序算法 冒泡排序(Bubble Sort)是一种简单的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 冒泡排序对n个项目需要O(n2)的比较次数,且可以原地排序.尽管这个算法是最简单了解和实作的排序算法之一,但它对于少数元素之外的数列排序是很没有效率的. 冒泡排序是与插入排序拥有相等的执

  • C语言实现冒泡排序的思路以及过程

    C语言实现冒泡排序的思路以及过程

    目录 C语言实现<冒泡排序> 整体思路 代码实现 C语言实现<冒泡排序> 你们好!我是飞人!此篇文章是我进入IT行业第一篇博客,若有不妥之处,欢迎指点. 此篇讲解冒泡排序的原理,以及如何用C语言去实现.希望能够给各位读者带来一定的认识. 整体思路 例子:以一个整形数组为例 int arr[10]={1,2,3,4,5,6,7,8,9,10}; 我们如何进行"降序"的排序方式?? 确定躺数 总共需要排序10个数,而当我们实际去进行安排怎么去比较大小时,总共只组合了

  • C语言中冒泡排序算法详解

    C语言中冒泡排序算法详解

    目录 一.算法描述 二.算法分析 三.完整代码 总结 一.算法描述 比较相邻两个元素,如果第一个比第二个大则交换两个值.遍历所有的元素,每一次都会将未排序序列中最大的元素放在后面.假设数组有 n 个元素,那么需要遍历 n - 1 次,因为剩下的一个元素一定是最小的,无需再遍历一次.因此需要两层循环,第一层是遍历次数,第二层是遍历未排序数组. 动图如下: 黄色部分表示已排好序的数组,蓝色部分表示未排序数组 核心代码如下: /** * @brief 冒泡排序 * * @param arr 待排序的数

  • java 中归并排序算法详解

    java 中归并排序算法详解

    java 中归并排序算法详解 归并排序算法,顾名思义,是一种先分再合的算法,其算法思想是将要排序的数组分解为单个的元素,每个元素就是一个单个的个体,然后将相邻的两个元素进行从小到大或从大到小的顺序排序组成一个整体,每个整体包含一到两个元素,然后对相邻的整体继续"合"并,因为每个整体都是排过序的,因而可以采用一定的算法对其进行合并,合并之后每个整体包含三到四个元素,继续对相邻的整体进行合并,直到所有的整体都合并为一个整体,最终得到的整体就是将原数组进行排序之后的结果. 对于相邻的整体,其

  • C语言中自定义类型详解

    C语言中自定义类型详解

    目录 结构大小 offsetof 结构体对齐规则 存在原因 总结 结构大小 我们先随便给出一个结构体,为了计算他的大小,我给出完整的打印方案: typedef struct num { char c; int n; char cc; }num; int main() { printf("%d\n", sizeof(num)); return 0; } 好了,按道理来说我计算一个结构体大小就看他的各个成员需要消耗多大的空间, num 结构体中三个成员分别是 char ,int ,char

  • C语言 选择排序算法详解及实现代码

    选择排序是排序算法的一种,这里以从小到大排序为例进行讲解. 基本思想及举例说明 选择排序(从小到大)的基本思想是,首先,选出最小的数,放在第一个位置:然后,选出第二小的数,放在第二个位置:以此类推,直到所有的数从小到大排序. 在实现上,我们通常是先确定第i小的数所在的位置,然后,将其与第i个数进行交换. 下面,以对 3  2  4  1 进行选择排序说明排序过程,使用min_index 记录当前最小的数所在的位置. 第1轮 排序过程 (寻找第1小的数所在的位置) 3  2  4  1(最初, m

  • C语言 奇偶排序算法详解及实例代码

    C语言 奇偶排序算法详解及实例代码

    C语言奇偶排序算法 奇偶排序,或奇偶换位排序,或砖排序,是一种相对简单的排序算法,最初发明用于有本地互连的并行计算.这是与冒泡排序特点类似的一种比较排序.该算法中,通过比较数组中相邻的(奇-偶)位置数字对,如果该奇偶对是错误的顺序(第一个大于第二个),则交换.下一步重复该操作,但针对所有的(偶-奇)位置数字对.如此交替进行下去. 使用奇偶排序法对一列随机数字进行排序的过程 处理器数组的排序 在并行计算排序中,每个处理器对应处理一个值,并仅有与左右邻居的本地互连.所有处理器可同时与邻居进行比较.交

  • Go语言中你不知道的Interface详解

    前言 最近在看Go语言的面向对象的知识点时,发现它的面向对象能力全靠 interface 撑着,而且它的 interface 还与我们以前知道的 interface 完全不同.故而整个过程不断的思考为什么要如此设计?这样设计给我们带来了什么影响? interface 我不懂你 Rob Pike 曾说: 如果只能选择一个Go语言的特 性移植到其他语言中,他会选择接口 被Go语言设计者如此看重,想来 interface 一定是资质不凡,颜值爆表.但是说实话,当我第一次读这部分内容的时候,我产生了以下

  • Go语言中的函数详解

    Go语言中的函数详解

    1.函数的声明定义 //func关键字 //getStudent函数名 //(id int, classId int) 参数列表 //(name string,age int) 返回值列表 func getStudent(id int, classId int)(name string,age int) { //函数体 if id==1&&classId==1{ name = "BigOrange" age = 26 } //返回值 return name, age /

  • C语言中的常量详解

    目录 C语言中的常量 字面常量 #define定义的标识符常量 枚举常量 C语言中的常量 C编程中的常量是一些固定的值,它在整个程序运行过程中无法被改变. 字面常量 字面常量是直接写出的固定值,它包含C语言中可用的数据类型,可分为整型常量,字符常量等.如:9.9,"hello"等就属于这一类常量. ##const修饰的常变量 有的时候我们希望定义这么一种变量:值不能被修改,在整个作用域中都维持原值.为了满足用户需求,C语言标准提供了const关键字.在定义变量的同时,在变量名之前加上c

  • Go语言中的闭包详解

    一.函数的变量作用域和可见性 1.全局变量在main函数执行之前初始化,全局可见 2.局部变量在函数内部或者if.for等语句块有效,使用之后外部不可见 3.全局变量和局部变量同名的情况下,局部变量生效. 4.可见性: 包内任何变量或函数都是能访问的. 包外的话,首字母大写是可以访问的,首字母小写的表示私有的不能被外部调用. 二.匿名函数 1.Go语言中函数也是一种类型,所以可以用一个函数类型的变量进行接收. func anonyTest1(){ fmt.Println("anonyTest1&

随机推荐