C语言实现冒泡排序算法的示例详解

目录
  • 1. 问题描述
  • 2. 问题分析
  • 3. 算法设计
    • 动图演示
  • 4. 程序设计
    • 设计一
    • 设计二
    • 结论
  • 5. 流程框架
  • 6. 代码实现
  • 7. 问题拓展

1. 问题描述

对N个整数(数据由键盘输入)进行升序排列。

2. 问题分析

对于N个数因其类型相同,我们可利用 数组 进行存储。

冒泡排序是在 两个相邻元素之间进行比较交换的过程将一个无序表变成有序表。

冒泡排序的思想:首先,从表头开始往后扫描数组,在扫描过程中逐对比较相邻两个元素的大小。

若相邻两个元素中,前面的元素大于后面的元素,则将它们互换,称之为消去了一个逆序。

在扫描过程中,不断地将两相邻元素中的大者往后移动,最后就将数组中的最大者换到了表的最后,这正是数组中最大元素应有的位置。

然后,在剩下的数组元素中(n-1个元素),重复上面的过程,将次小元素放到倒数第 2 个位置。

不断重复上述过程,直到剩下的数组元素为 0 为止,此时的数组就变为了有序。

假设数组元素的个数为 n nn,在最坏情况下需要的比较总次数为:((n−1)+(n−2)+...+2+1)=n(n−1)/2。

3. 算法设计

冒泡排序的过程我们用示意图简单的表示,从整个排序过程中寻找规律,n个元素只需比较n−1次即可。

假设一个数组中有 7 个元素,现在对这 7 个元素进行排序,只需比较 6 轮即可得到所要的有序序列。

示意图中最后加粗的数字即为经过一轮交换位置固定的数字。示意图如下:

动图演示

清楚了冒泡排序的过程,我们再来看一个动态图

4. 程序设计

设计一

数组名用 a 表示、数组下标用 j 表示,数组中相邻两个元素的下标可表示为 a[j]、a[j+1] 或 a[j-1]、a[j]。

在利用数组解决问题时需要注意数组下标不要越界。

假如定义一个整形数组 int a[n],则数组元素下标的取值范围是0~(n−1),下标小于0或者大于n−1 都视为下标越界。

如果相邻元素采用 a[j]、a[j+1] 表示的话,则下标取值范围是0~(n−2);

若采用 a[j-1]、a[j] 表示,下标取值范围则是1~(n−1)

设计二

数组元素互换 也是经常遇到的一类题型,一般这种情况我们需要 借助一个中间变量 才可以完成,对于许多初学者来说经常犯的一个错误是:对两个元素直接相互赋值,而不借助中间变量。

我们先来看生活中的一个例子:

在蓝墨水瓶中装有蓝墨水,红墨水瓶中装有红墨水;现在我们要把蓝墨水放到红墨水瓶中,红墨水放到蓝墨水瓶中。

做法是先找一个白色空瓶(作用相当于程序中的中间变量):

首先将蓝墨水倒入白色空瓶: t=a[i] 或 t=a[i+1];

接着将红墨水倒入蓝墨水瓶:a[i]=a[i+1] 或 a[i+1]=a[i];

最后将白瓶中的蓝墨水倒入红墨水瓶:a[i+1]=t 或 a[i]=t;

经过这 3 步就完成了红墨水与蓝墨水的互换。如果不借助白色空瓶,直接把蓝墨水倒入红墨水瓶,或把红墨水倒入蓝墨水瓶,这样必将破坏原来所存储的内容。

第一轮的交换过程可以用简单的程序段进行表示:

第二轮交换过程(最后一个元素经过第一轮比较已经确定,不需要再次进行比较):

第三轮交换过程(最后两个元素已经确定,不需要再次进行比较):

结论

由上面的程序段发现,第一轮比较的判定条件为 j < n-1;

第二轮为 j < n-2;

第三轮为 j < n-3;

依次类推,第 i 轮的循环判定条件必为 j < n-i。

在编程过程中我们可以用两层循环来控制,第一层循环控制交换的轮数,第二层循环控制每轮需要交换的次数。

5. 流程框架

6. 代码实现

假设有下面一组无序数组,我们要对它进行升序排序

完整代码

#include <stdio.h>

//冒泡排序函数
void BubbleSort(int arr[], int len)
{
	int i;
	int j;
	int temp;
	for (i = 0; i < len - 1; i++) //控制比较的轮数
	{
		for (j = 0; j < len - 1 - i; j++) //控制每轮比较的次数
		{
			if (arr[j] > arr[j + 1]) //数组相邻两个元素进行交换
			{
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;

			}
		}

	}

}

//输出函数
void print(int arr[], int len)
{
	int i;
	for (i = 0; i < len; i++)
	{
		printf("%3d ", arr[i]);
	}
}

int main()
{

	int arr[10] = { 5,8,6,3,9,2,1,7,12,4 };

	BubbleSort(arr, 10);

	printf("The data after sorted:\n");
	print(arr, 10);

	printf("\n");

	return 0;
}

运行结果

代码贴图

7. 问题拓展

常用的排序方法除了上述的冒泡排序外,还有选择排序、插入排序、快速排序和堆排序等,下面简单介绍一下 选择排序。

选择排序思想:

扫描整个线性表,第一轮比较拿数组中的第一个元素与其他元素进行比较,遇到比第一个元素小的则进行交换;

再拿着交换之后的第一个元素接着上次比较的位置与后面的元素进行比较,直到扫描到线性表的最后,从中选出最小的元素,将它交换到表的最前面(这是它应有的位置)。

第二轮比较的时候从第二个元素开始,依次与第三个、第四个直到最后一个比较,在比较过程中有比第二个元素小的进行交换,接着与后面的元素比较;

对剩下的子表采用同样的方法,直到子表为空。在最坏情况下需要比较n(n−1)/2 次。

选择排序如下

#include <stdio.h>

//选择排序
void selectSort(int arr[], int len)
{
	int i;
	int j;
	for (i = 0; i < len - 1; i++)
	{
		int min = i;//假设第一个元素是最小的
		for (j = i + 1; j < len; j++)
		{
			if (arr[j] < arr[min])
			{
				min = j;//保存最小元素的下标
			}
		}
		//交换
		int temp = arr[min];
		arr[min] = arr[i];
		arr[i] = temp;
	}
}

//输出
void print(int arr[], int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%3d ", arr[i]);
	}
}

int main()
{
	int arr[10] = { 5,8,6,3,9,2,1,7,12,4 };

	selectSort(arr, 10);

	printf("The data after sorted:\n");
	print(arr, 10);

	printf("\n");

	return 0;
}

运行结果

代码贴图

不同排序法的效率是不同的,不同需求情况下可选择不同的方法。

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

(0)

相关推荐

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

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

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

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

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

    今天我们来用C语言实现一下冒泡排序 首先我们来了解一下什么叫做冒泡排序,冒泡顾名思义把质量轻的气体(如二氧化碳一样)浮到水面上(如可乐中的二氧化碳),因此冒泡排序的原理就是N个元素在一个周期中,微观上依次进行两两元素的比较,小的元素就被放在前面,大的元素放在后面,以此来进行N-1个周期,来完成冒泡排序. 上文中的一个周期,即外循环,依次进行比较,即内循环. 文字看着很迷糊?没事儿,上图 如图所示,两两元素依次进行比较,小的元素往前移动,大的元素往后移动,直至元素顺序是升序的形式,即移动了 元素-

  • C语言实现冒泡排序算法

    BubblSort.c #include<stdio.h> void BubbleSort(int a[],int len) { int i; int j; int h; int temp; for(i=0;i<len-1;++i) { for(j=len-1;j>i;--j) { if(a[j]<a[j-1]) { temp=a[j]; a[j]=a[j-1]; a[j-1]=temp; } } for(h=0;h<len;h++) { printf(" %

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

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

  • C语言实现冒泡排序算法的示例详解

    目录 1. 问题描述 2. 问题分析 3. 算法设计 动图演示 4. 程序设计 设计一 设计二 结论 5. 流程框架 6. 代码实现 7. 问题拓展 1. 问题描述 对N个整数(数据由键盘输入)进行升序排列. 2. 问题分析 对于N个数因其类型相同,我们可利用 数组 进行存储. 冒泡排序是在 两个相邻元素之间进行比较交换的过程将一个无序表变成有序表. 冒泡排序的思想:首先,从表头开始往后扫描数组,在扫描过程中逐对比较相邻两个元素的大小. 若相邻两个元素中,前面的元素大于后面的元素,则将它们互换,

  • Go语言使用对称加密的示例详解

    目录 介绍 AES 算法 实践 总结 介绍 在项目开发中,我们经常会遇到需要使用对称密钥加密的场景,比如客户端调用接口时,参数包含手机号.身份证号或银行卡号等. 对称密钥加密是一种加密方式,其中只有一个密钥用于加密和解密数据.通过对称加密进行通信的实体必须共享该密钥,以便可以在解密过程中使用它.这种加密方法与非对称加密不同,非对称加密使用一对密钥(一个公钥和一个私钥)来加密和解密数据. AES 算法 常见的对称密钥加密算法有 AES (Advanced Encryption Standard),

  • JavaScript实现基础排序算法的示例详解

    目录 前言 正文 1.冒泡排序 2.选择排序 3.插入排序 4.快速排序 前言 文本来总结常见的排序算法,通过 JvavScript  来实现 正文 1.冒泡排序 算法思想:比较相邻两个元素的大小,如果第一个比第二个大,就交换它们.从头遍历到尾部,当一轮遍历完后,数组最后一个元素是最大的.除去最后一个元素,对剩下的元素重复执行上面的流程,每次找出剩余元素中最大的,遍历完后,数组是升序的 算法分析:总共需要进行length * (length - 1) / 2 次比较,所以时间复杂度为O(n^2)

  • Go语言数据结构之希尔排序示例详解

    目录 希尔排序 算法思想 图解算法 Go 代码实现: 总结 希尔排序 在插入排序中,在待排序序列的记录个数比较少,而且基本有序,则排序的效率较高. 1959 年,Donald Shell 从“减少记录个数” 和 “基本有序” 两个方面对直接插入排序进行了改进,提出了希尔排序算法. 希尔排序又称为“缩小增量排序”.即将待排序记录按下标的一定增量分组(减少记录个数),对每组记录使用直接插入排序算法排序(达到基本有序): 随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1,整个序列基本有序,再对

  • Go语言数据结构之选择排序示例详解

    目录 选择排序 动画演示 Go 代码实现 总结 选择排序 选择排序(selection sort)是一种原地(in-place)排序算法,适用于数据量较少的情况.由于选择操作是基于键值的且交换操作只在需要时才执行,所以选择排序长用于数值较大和键值较小的文件. 思想: 对一个数组进行排序,从未排序的部分反复找到最小的元素,并将其放在开头. 给定长度为 nnn 的序列和位置索引i=0 的数组,选择排序将: 遍历一遍序列,寻找序列中的最小值.在 [i...n−1] 范围内找出最小值 minValue

  • Go语言题解LeetCode455分发饼干示例详解

    目录 题目描述 思路分析 AC 代码 分发饼干 贪心算法 解题思路 代码 题目描述 原题链接 : 455. 分发饼干 - 力扣(LeetCode) (leetcode-cn.com) 假设你是一位很棒的家长,想要给你的孩子们一些小饼干.但是,每个孩子最多只能给一块饼干. 对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸:并且每块饼干 j,都有一个尺寸 s[j] .如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足.你的目标

  • C语言中的正则表达式使用示例详解

    正则表达式,又称正规表示法.常规表示法(英语:Regular Expression,在代码中常简写为regex.regexp或RE).正则表达式是使用单个字符串来描述.匹配一系列符合某个句法规则的字符串. 在c语言中,用regcomp.regexec.regfree 和regerror处理正则表达式.处理正则表达式分三步: 编译正则表达式,regcomp: 匹配正则表达式,regexec: 释放正则表达式,regfree. 函数原型 /* 函数说明:Regcomp将正则表达式字符串regex编译

  • VSCode各语言运行环境配置方法示例详解

    系统环境变量的配置 如:将F:\mingw64\bin添加到系统环境变量Path中 VSCode软件语言json配置C语言 创建个.vscode文件夹,文件夹内创建以下两个文件 launch.json 文件配置 { "version": "0.2.0", "configurations": [ { "name": "(gdb) Launch", "type": "cppdbg&

  • c语言左移和右移的示例详解

    逻辑移位,简单理解就是物理上按位进行的左右移动,两头用0进行补充,不关心数值的符号问题. 算术移位,同样也是物理上按位进行的左右移动,两头用0进行补充,但必须确保符号位不改变. 算术移位指令 算术移位指令有:算术左移SAL(ShiftAlgebraic Left)和算术右移SAR(ShiftAlgebraic Right).算术移位指令的功能描述如下: (1)算术左移SAL把目的操作数的低位向高位移,空出的低位补0: (2)算术右移SAR把目的操作数的高位向低位移,空出的高位用最高位(符号位)填

  • R语言时间序列TAR阈值自回归模型示例详解

    为了方便起见,这些模型通常简称为TAR模型.这些模型捕获了线性时间序列模型无法捕获的行为,例如周期,幅度相关的频率和跳跃现象.Tong和Lim(1980)使用阈值模型表明,该模型能够发现黑子数据出现的不对称周期性行为. 一阶TAR模型的示例: σ是噪声标准偏差,Yt-1是阈值变量,r是阈值参数, {et}是具有零均值和单位方差的iid随机变量序列. 每个线性子模型都称为一个机制.上面是两个机制的模型. 考虑以下简单的一阶TAR模型: #低机制参数 i1 = 0.3 p1 = 0.5 s1 = 1

随机推荐