IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 算法(排序算法之冒泡排序及其变式) -> 正文阅读

[数据结构与算法]算法(排序算法之冒泡排序及其变式)

(此篇实现语言为C语言)

冒泡排序可能是我们在学习谭浩强C语言里面比较痛苦的算法之一了,不少人也因为缺少对于双重循环的把控而出现写不出以及处处出错的问题。今天也是来谈谈作为交换排序之一的冒泡排序究竟是如何实现的。


单向冒泡排序

在这里为大家准备一个待排序的数组:

?而我们的冒泡排序是如何将这个无序的数组转化为有序的呢?

首先要明白,冒泡排序是两个数之间进行比较,将较大的数字放置在小的数字之后(由小到大排序,由大到小反之,本文全篇探讨由小到大排序),而每次我们的比较完了以后步长为1地往下继续比较,这样便会出现有趣的现象:

?(画的可能有点抽象,大家请自行脑补一下。。。)我们每次进行两两比较,大的元素后置,也就是大的泡泡往上不断往上水面上浮,每次都会将最大的元素后置,也就是最大的泡泡到了最接近水面的地方,而到第一次的排序的最后,我们也会发现,最大的元素被放置到了最后。

?虽然前面仍然是无序的,但我们至少把最大的元素放到了最后不是?于是我们每次将数组遍历的长度减一,把最大的元素放到最后,那么最后不就是一个有序的数组吗?相当于每次最大的泡泡都会冒出水面,第二次的时候,第二大的泡泡直接作为最大的泡泡往上冒出水面,以此类推,直至所有的泡泡冒出水面。

大伙也可以自己尝试脑子里跑一边第二轮的冒泡排序

?九轮之后,我们将九个元素全部置成我们脑海中逻辑数组(也就是每次减少一个遍历长度的所抽象出来的数组)的最大位上,即得到了一个有序数组{ 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9? }

那我们的代码应该如何实现呢,每次比较最大的元素都需要后置,且每次比较完成,数组的遍历长度就需要减一.

void bubble(int* arr, int len)
{
    //控制总的冒泡次数的循环,我们每进行一次就会把最大元素置到最后
	for (int i = 0; i < len; i++) 
        //控制执行一次冒泡的循环,每次遍历长度减一通过len-i-1来控制
		for (int j = 0; j < len - i - 1; j++)
		{
			//简简单单的判断交换啦
			if (arr[j] > arr[j + 1])
			{
				int tem = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tem;
			}
		}
}

通过内外两层循环,外层控制总的冒泡次数,内层控制执行一次的冒泡排序,整个冒泡排序也就在我们的掌握之中咯。

但是,如果我们给出的数组是本身是有序的呢?

是不是那么多次的冒泡其实是没有必要的,小的泡泡完全没必要跟脑袋上的泡泡比较看看是不是要往上浮,我们只需要在第一轮的全遍历中知道这是一个有序数组然后直接出循环即可。

这里,就需要一个flag标志变量了,我们的pro版本也仅需要一个flag就升级成功。

void bubble(int* arr, int len)
{
	int flag = 1;//默认这是一个有序数组
	for (int i = 0; i < len; i++) //控制总的冒泡次数的循环,我们每进行一次就会把最大元素置到最后
	{
        //控制执行一次冒泡的循环,每次遍历长度减一通过len-i-1来控制
		for (int j = 0; j < len - i - 1; j++)
		{
			//简简单单的判断交换啦
			if (arr[j] > arr[j + 1])
			{
				int tem = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tem;
				flag = 0;//出现了一次交换,他不是有序的,修改标志位
			}
		}
		if (flag == 1)//如果为有序数组,直接返回,无需比较
			return;
	}
}

双向冒泡排序

我们的单向冒泡程序完成,但是我们同时需要想到一个问题,我们每一次的冒泡过程是不是已结束我们的索引就需要回到最初的位置重新进行下一遍的冒泡,这就没有实现时间的统筹安排嘛,你想想,我们走一遍过去是一个冒泡,走回来还是一个冒泡,这不就是来回都有事干,这才不浪费时间,我们的计算机打工人也能被完美的调用起来。?

在这里也是对我们循环掌握度提高了更高层次的要求。

接下来是图解流程:

向右迈步,将最大元素右置 ,而接下来:

那我们下一轮呢?自己不妨想一下:

?就这样我们执行双向冒泡 length/2取整?次(length为数组长度)之后我们便能得到有序的数组。

接下来我们来程序实现:

void double_bubble(int* arr, int len)
{
	int i = 0;//提供冒泡遍历所需索引
	//最外侧循环,控制整个双向冒泡循环的次数,以及提供每次的双向循环的起始位置
	for (int t = 0; t < len/2; t++)
	{
		//向右迈步进行冒泡,从t位置开始,相当于去掉已冒泡的最小元素
		for (i = t; i < len - t - 1; i++)
		{
			//简简单单的交换
			if (arr[i] > arr[i + 1])
			{
				int tem = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = tem;
			}
		}
		//向左迈步进行冒泡,从向右迈步后所产生的逻辑最右侧开始,直到逻辑最左侧
		for (; i > t; i--)
		{
			//简简单单的交换
			if (arr[i] < arr[i - 1])
			{
				int tem = arr[i];
				arr[i] = arr[i - 1];
				arr[i - 1] = tem;
			}
		}
	}
}

无独有偶,我们应该也要向之前单向冒泡一样考虑最好的状况,即有序数列,仅需一个标志变量即可,十分的简单,既然在之前已经知道了单向冒泡要去如何添加标志变量,双向冒泡可以自己尝试一下添加标志变量。

void double_bubble(int* arr, int len)
{
	int i = 0;//提供冒泡遍历所需索引
	int flag = 1;//默认这是一个有序数组
	//最外侧循环,控制整个双向冒泡循环的次数,以及提供每次的双向循环的起始位置
	for (int t = 0; t < len/2; t++)
	{
		//向右迈步进行冒泡,从t位置开始,相当于去掉已冒泡的最小元素
		for (i = t; i < len - t - 1; i++)
		{
			//简简单单的交换
			if (arr[i] > arr[i + 1])
			{
				int tem = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = tem;
				flag = 0;
			}
		}
		if (flag == 1)
			return;
		//向左迈步进行冒泡,从向右迈步后所产生的逻辑最右侧开始,直到逻辑最左侧
		for (; i > t; i--)
		{
			//简简单单的交换
			if (arr[i] < arr[i - 1])
			{
				int tem = arr[i];
				arr[i] = arr[i - 1];
				arr[i - 1] = tem;
			}
		}
	}
}

实验全部代码

#include<stdio.h>
#define ARR_LEN 9

//单向冒泡
void bubble(int* arr, int len)
{
	int flag = 1;//默认这是一个有序数组
	for (int i = 0; i < len; i++) //控制总的冒泡次数的循环,我们每进行一次就会把最大元素置到最后
	{
		for (int j = 0; j < len - i - 1; j++)//控制执行一次冒泡的循环,每次遍历长度减一通过len-i-1来控制
		{
			//简简单单的判断交换啦
			if (arr[j] > arr[j + 1])
			{
				int tem = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tem;
				flag = 0;//出现了一次交换,他不是有序的,修改标志位
			}
		}
		if (flag == 1)//如果为有序数组,直接返回,无需比较
			return;
	}
}

//双向冒泡
void double_bubble(int* arr, int len)
{
	int i = 0;//提供冒泡遍历所需索引
	int flag = 1;//默认这是一个有序数组
	//最外侧循环,控制整个双向冒泡循环的次数,以及提供每次的双向循环的起始位置
	for (int t = 0; t < len/2; t++)
	{
		//向右迈步进行冒泡,从t位置开始,相当于去掉已冒泡的最小元素
		for (i = t; i < len - t - 1; i++)
		{
			//简简单单的交换
			if (arr[i] > arr[i + 1])
			{
				int tem = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = tem;
				flag = 0;
			}
		}
		if (flag == 1)
			return;
		//向左迈步进行冒泡,从向右迈步后所产生的逻辑最右侧开始,直到逻辑最左侧
		for (; i > t; i--)
		{
			//简简单单的交换
			if (arr[i] < arr[i - 1])
			{
				int tem = arr[i];
				arr[i] = arr[i - 1];
				arr[i - 1] = tem;
			}
		}
	}
}

void show_bubble(int* arr, int len)
{
	for (int i = 0; i < len; i++)
		printf("%d ", arr[i]);
}

int main()
{
	int arr[] = { 2,3,1,6,7,8,9,4,5 };
	int arr1[] = { 2,3,1,6,7,8,9,4,5 };
	
	//int brr[] = { 1,2,3,4,5,6,7,8,9 };
	printf("this is result of arr bubble\n");
	bubble(arr,ARR_LEN);
	show_bubble(arr, ARR_LEN);

	printf("\nthis is result of arr double_bubble\n");
	double_bubble(arr1, ARR_LEN);
	show_bubble(arr1, ARR_LEN);
	

	return 0;
}

?(如有问题,欢迎指正)

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-11-28 11:32:46  更:2021-11-28 11:33:45 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2025年1日历 -2025/1/9 15:45:23-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码