排序前言&冒泡排序

这篇具有很好参考价值的文章主要介绍了排序前言&冒泡排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

排序应用

常见的排序算法  

BubbleSort冒泡排序

整体思路

图解分析 ​

代码实现

每趟

写法1

写法2

代码NO1

代码NO2优化

时间复杂度


排序概念

排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。

  • 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次 序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排 序算法是稳定的;否则称为不稳定的。
  • 内部排序:数据元素全部放在内存中的排序。
  • 外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。  

排序应用

排序的应用场景很多: 学校医院品牌的排名等等。

算法当中也常用,二分查找,去重算法等等。

排序前言&冒泡排序,初阶数据结构,数据结构,C语言,算法,排序算法

排序前言&冒泡排序,初阶数据结构,数据结构,C语言,算法,排序算法

常见的排序算法  

排序前言&冒泡排序,初阶数据结构,数据结构,C语言,算法,排序算法

  • 冒泡排序
  • 直接插入排序&VS冒泡排序
  • 希尔排序(在插入排序的基础上)
  • 选择排序VS堆排序
  • 快速排序
  • 归并排序
  • 补充:外排序 
  • 排序的OJ题目
  • 排序的思想:先单趟再多趟,注意结束条件❗先局部再整体

BubbleSort冒泡排序

整体思路

  • 通过对待排序序列从前向后(从下标较小的元素开始),依次对相邻两个元素的值进行两两比较,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就如果水底下的气泡一样逐渐向上冒泡。
  • 一趟:两两比较(若顺序则不交换,若逆序则交换)
  • 整体:重复上述过程,直到全部数组元素都每趟完成。
  • 优化:若某一趟发现,数组元素已经顺序不用继续冒泡下去,停止冒泡。(效率提高)

图解分析 

排序前言&冒泡排序,初阶数据结构,数据结构,C语言,算法,排序算法排序前言&冒泡排序,初阶数据结构,数据结构,C语言,算法,排序算法

代码实现

每趟

  • n个数的下标是0~n-1
  • i每次从0开始,则比较的是下标为ii+1的数值
  • i每次从1开始,则比较的是下标为i-1i的数值
  • 注意:i每次从第一个数值开始冒泡,不是第j格数值开始冒泡
写法1
	//写法1
	for (int i = 0; i < n-1; i++)
	{
		if (a[i] > a[i + 1])//i=n-1就越界了
		{
			Swap(&a[i], &a[i + 1]);
		}
	}
写法2
	//写法2
	for (int i = 1; i < n; i++)
	{
		if (a[i - 1] > a[i])//i=n-1没有越界,
		{
			Swap(&a[i - 1], &a[i]);
		}
	}

代码NO1

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		//一趟
		for (int i = 0; i < n - 1 - j; i++)//i要从第一个开始交换
		{
			if (a[i] > a[i + 1])//i=n-1就越界了
			{
				Swap(&a[i], &a[i + 1]);
			}
		}
    }

代码NO2优化

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		//一趟
		bool exchange = false;
		for (int i = 0; i < n - 1 - j; i++)//i要从第一个开始交换
		{
			if (a[i] > a[i + 1])//i=n-1就越界了
			{
				Swap(&a[i], &a[i + 1]);
				exchange = true;
			}
		}
		if (exchange == false)
		{
			break;
		}
    }
}

排序前言&冒泡排序,初阶数据结构,数据结构,C语言,算法,排序算法

时间复杂度

 时间复杂度:经典的O(N^2)

排序前言&冒泡排序,初阶数据结构,数据结构,C语言,算法,排序算法

排序前言&冒泡排序,初阶数据结构,数据结构,C语言,算法,排序算法 

🙂感谢大家的阅读,若有错误和不足,欢迎指正!文章来源地址https://www.toymoban.com/news/detail-826197.html

到了这里,关于排序前言&冒泡排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 『初阶数据结构 • C语言』⑥ - 插入排序&希尔排序

    学习目标 写在前面 1.插入排序 2.插入排序实战  3.插入排序的实现  4.插入排序的效率 5.平均情况 6.希尔排序 7.希尔排序的实现 8.希尔排序的效率 9.总结   之前我们衡量一个算法的效率时,都是着眼于它在最坏情况下需要多少步。原因很简单,连最坏的情况都做足准备了,其

    2024年02月15日
    浏览(40)
  • 『初阶数据结构 • C语言』⑤ - 选择排序

    本文内容借鉴一本我非常喜欢的书——《数据结构与算法图解》。学习之余,我决定把这本书精彩的部分摘录出来与大家分享。     目录 写在前面 1.选择排序 2.选择排序实战 3.选择排序的实现 4.选择排序的效率 5.忽略常数 6.大O的作用 7.总结     大 O 是一种能够比较算法效

    2024年02月14日
    浏览(43)
  • 『初阶数据结构 • C语言』⑬ - 堆排序详解【附完整源码】

     = 目录 0.写在前面 1.什么是堆? 2. 堆排序 2.1 建堆 2.1.1 AdjustUp(向上调整算法) 2.1.2 AdjustDown(向下调整算法) 2.2 两种建堆算法的时间复杂度 2.2.1 AdjustUp建堆的时间复杂度 2.2.2 AdjustDown建堆的时间复杂度 2.3 排序 3.堆排序的时间复杂度 完整源码 你是否对堆排序早有耳闻?身

    2024年02月16日
    浏览(36)
  • 数据结构排序——详解快排及其优化和冒泡排序(c语言实现、附有图片与动图示意)

    上次讲了选择排序和堆排序:数据结构排序——选择排序与堆排序 今天就来快排和冒泡 快速排序(Quick Sort)是一种常用的排序算法,它是由英国计算机科学家Tony Hoare于1959年发明的。快速排序的基本思想是通过分治的策略将一个数组分成两个子数组,然后分别对这两个子数

    2024年01月25日
    浏览(43)
  • 第11章:C语言数据结构与算法初阶之排序

    排序是一种非常重要的算法。 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列中,存在多个具有相同的的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,

    2024年02月12日
    浏览(44)
  • 【数据结构初阶】十、快速排序(比较排序)讲解和实现(三种递归快排版本 + 非递归快排版本 -- C语言实现)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】九、排序的讲解和实现(直接插入 希尔 直接选择 堆 冒泡 -- C语言)

    2024年02月08日
    浏览(45)
  • 『初阶数据结构 • C语言』⑰ - 快速排序(hoare法、挖坑法、前后指针法与非递归实现)

    目录 1. hoare法 方法与步骤 代码实现 2. 挖坑法 方法与步骤 代码实现 3. 前后指针法 方法与步骤 代码实现  4. 快速排序的缺点与优化 1.快速排序的缺点 2.快速排序的优化 ① 三数取中法选 key 代码实现 ② 小区间优化 代码实现 5. 快速排序的非递归实现 附录﹡完整源码 快速排序

    2024年02月13日
    浏览(43)
  • 数据结构——排序之冒泡排序

    hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥 个人主页:大耳朵土土垚的博客 💥 所属专栏:数据结构学习笔记 、排序算法合集 💥对于数据结构顺序表、链表、堆有疑问的都可以在上面数据结构的专栏进行学习哦~ 有问题可以写

    2024年04月12日
    浏览(34)
  • 【数据结构】排序(2)—冒泡排序 & 快速排序

                                      目录 一. 冒泡排序 基本思想 代码实现 时间和空间复杂度 稳定性 二. 快速排序 基本思想 代码实现 hoare法 挖坑法 前后指针法 时间和空间复杂度 稳定性            冒泡排序是一种交换排序。两两比较数组元素,如果是逆序(即排列顺序

    2024年02月08日
    浏览(76)
  • 【数据结构与算法】排序算法:冒泡排序,冒泡排序优化,选择排序、选择排序优化

    目录 一、冒泡排序 1、冒泡排序思想 2、冒泡排序算法的性能分析 代码实现: 二、选择排序 1、选择排序思想 2、选择排序算法的性能分析  代码实现: 1、冒泡排序思想 冒泡排序的基本思想是通过相邻元素之间的比较和交换来逐步将最大(或最小)的元素移到右边(或左边

    2024年01月19日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包