经典排序算法(1)——冒泡排序算法详解

经典排序算法(1)——冒泡排序算法详解冒泡排序(BubbleSort)是一种典型的交换排序算法,通过交换数据元素的位置进行排序。一、算法基本思想(1)基本思想冒泡排序的基本思想就是:从无序序列头部开始,进行两两比较,根据大小交换位置,直到最后将最大(小)的数据元素交换到了无序队列的队尾,从而成为有序序列的一部分;下一次继续这个过程,直到所有数据元素都排好序。算法的核心在于每次通过两两比较交换位置,选出

大家好,又见面了,我是你们的朋友全栈君。

冒泡排序(Bubble Sort)是一种典型的交换排序算法,通过交换数据元素的位置进行排序。


一、算法基本思想

(1)基本思想

冒泡排序的基本思想就是:从无序序列头部开始,进行两两比较,根据大小交换位置,直到最后将最大(小)的数据元素交换到了无序队列的队尾,从而成为有序序列的一部分;下一次继续这个过程,直到所有数据元素都排好序。

算法的核心在于每次通过两两比较交换位置,选出剩余无序序列里最大(小)的数据元素放到队尾。


(2)运行过程

冒泡排序算法的运作如下:

1、比较相邻的元素。如果第一个比第二个大(小),就交换他们两个。

2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大(小)的数。

3、针对所有的元素重复以上的步骤,除了最后已经选出的元素(有序)。

4、持续每次对越来越少的元素(无序元素)重复上面的步骤,直到没有任何一对数字需要比较,则序列最终有序。


(3)示例

经典排序算法(1)——冒泡排序算法详解


二、算法实现(核心代码)

C++实现:

void bubble_sort(int arr[], int len) {
	int i, j;
	for (i = 0; i < len - 1; i++)
		for (j = 0; j < len - 1 - i; j++)
			if (arr[j] > arr[j + 1])
				swap(arr[j], arr[j + 1]);
}


Java实现:

public static void bubble_sort(int[] arr) {
		int i, j, temp, len = arr.length;
		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;
				}
}

三、算法改进和变种

(1)设置标志变量change

标志变量用于记录每趟冒泡排序是否发生数据元素位置交换。如果没有发生交换,说明序列已经有序了,不必继续进行下去了。

void bubble_sort(int arr[], int len) {
	int i, j, change=1;
        
	for (i = 0; i < len - 1 && change!=0; i++)
        {
                change=0;
		for (j = 0; j < len - 1 - i; j++)
			if (arr[j] > arr[j + 1])
                        {
				swap(arr[j], arr[j + 1]);
                                change = 1;
                         }
        }
}

(2)鸡尾酒排序

鸡尾酒排序又叫定向冒泡排序,搅拌排序、来回排序等,是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

鸡尾酒排序在于排序过程是先从低到高,然后从高到低;而冒泡排序则仅从低到高去比较序列里的每个元素。它可以得到比冒泡排序稍微好一点的效能,原因是冒泡排序只从一个方向进行比对(由低到高),每次循环只移动一个项目。

以序列(2,3,4,5,1)为例,鸡尾酒排序只需要从低到高,然后从高到低就可以完成排序,但如果使用冒泡排序则需要四次。

但是在乱数序列的状态下,鸡尾酒排序与冒泡排序的效率都很差劲。

void cocktail_sort(int arr[], int len) {
	int j, left = 0, right = len - 1;
	while (left < right) {
		for (j = left; j < right; j++)
			if (arr[j] > arr[j + 1])
				swap(arr[j], arr[j + 1]);
		right--;
		for (j = right; j > left; j--)
			if (arr[j - 1] > arr[j])
				swap(arr[j - 1], arr[j]);
		left++;
	}
}

四、性能(算法时间、空间复杂度、稳定性)分析

(1)时间复杂度

在设置标志变量之后:

当原始序列“正序”排列时,冒泡排序总的比较次数为n-1,移动次数为0,也就是说冒泡排序在最好情况下的时间复杂度为O(n)

当原始序列“逆序”排序时,冒泡排序总的比较次数为n(n-1)/2,移动次数为3n(n-1)/2次,所以冒泡排序在最坏情况下的时间复杂度为O(n^2)

当原始序列杂乱无序时,冒泡排序的平均时间复杂度为O(n^2)


(2)空间复杂度

冒泡排序排序过程中需要一个临时变量进行两两交换,所需要的额外空间为1,因此空间复杂度为O(1)


(3)稳定性

冒泡排序在排序过程中,元素两两交换时,相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法



版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/157063.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • UICollectionView的单选

    UICollectionView的单选//点击选定-(void)collectionView:(UICollectionView*)collectionViewdidSelectItemAtIndexPath:(NSIndexPath*)indexPath{    JFCollectionViewCell*cell=(JFCollectionViewCell*)[collection

  • Intellij IDEA 查找接口实现类的快捷键「建议收藏」

    Intellij IDEA 查找接口实现类的快捷键「建议收藏」查找接口的实现类:IDEA风格ctrl+alt+B在按F2查看详细文档注解查看类或接口的继承关系:ctrl+h1、IDEA_查找接口的实现的快捷键 个人分类管理http://blog.csdn.net/u010003835/article/details/790366662、intellijidea8.1.2中找到实现一个类或者接口子类的快捷键 https://zhidao.ba…

  • spring cloud和dubbo的区别,各自优缺点「建议收藏」

    spring cloud和dubbo的区别,各自优缺点「建议收藏」区别:————————–来源(背景):Dubbo,是阿里巴巴服务化治理的核心框架,并被广泛应用于阿里巴巴集团的各成员站点。SpringCloud,从命名我们就可以知道,它是SpringSource的产物,Spring社区的强大背书可以说是Java企业界最有影响力的组织了,除了SpringSource之外,还有Pivotal和Netfix是其强大的后盾与技术输…

  • STM32F103学习笔记三 串口通信

    STM32F103学习笔记三 串口通信本文参照正点原子STM32F1xx官方资料:《STM32中文参考手册V10》-第25章通用同步异步收发器(USART)及【STM32】串口通信基本原理(超基础、详细版)单片机入门学习十STM32单片机学习七串口通讯-风水月的专栏](https://blog.csdn.net/fengshuiyue/article/details/79095389)1、串口通信背景知识1.1、…

  • 二元logistic回归模型——spss步骤

    二元logistic回归模型——spss步骤二元:因变量为二分类变量,且两个分类整合在一起的概率为1.(有效/无效;是/否)分析——回归——二元logistic——结果作为因变量——自变量作为协变量分类——设置分类变量(非连续变量)——变化量、第一个保存——概率、组成员选项:霍斯默-莱梅肖拟合优度、Exp(B)置信区间——在每一个步骤结果分析:(1)看霍斯默检验的显著性:sig/p>0.05表示拟合良好。(2)方程中的变量:B——系数sig——p值——显著性Exp(B)——OR值——优势比(高出一个单位,发生的概率高出多少

    2022年10月25日
  • 免备案cdn_cdn贝安装

    免备案cdn_cdn贝安装免备案CDN,符码CDN应该是使用CDN贝搭建,该CDN系统相对来说比较成熟,功能支持比较丰富。今天对符码免备案CDN进行简单的测试,仅供大家参考。首先,就是简单粗暴的多地区PING大法,简单看下CDN延迟效果:如果要是对比那么多免备案CDN延迟来说,符码CDN平均可以做到45ms的延迟,无疑是测试的所有免备案CDN中多地区PING平均延迟最小的一个,甚至一些国内CDN也达不到这个低延迟效果,延迟…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号