[数据结构 -- 手撕排序第三篇] 冒泡排序

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

目录

1、常见的排序算法

1.1 交换排序基本思想

2、冒泡排序的实现

2.1 基本思想

2.2 单趟排序

2.2.1 单趟排序分析

2.2.2 单趟排序实现代码

3、冒泡排序完整代码实现

3.1 思路分析

3.2 代码实现

4、时间复杂度

5、优化算法

5.1 优化算法思路

5.2 优化算法代码实现

6、冒泡排序的特性总结


1、常见的排序算法

1.1 交换排序基本思想

冒泡排序属于交换排序之一,我们先来了解以下冒泡排序思想。

基本思想:所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。

[数据结构 -- 手撕排序第三篇] 冒泡排序,排序算法,算法,排序算法,c语言

2、冒泡排序的实现

2.1 基本思想

我们本篇冒泡排序以排升序来举例

基本思想:对比数组前一个数字与后一个数组的大小,当前一个数大于后一个数,我们就交换两个数字,遍历整个数组,不断判断,进行交换。

[数据结构 -- 手撕排序第三篇] 冒泡排序,排序算法,算法,排序算法,c语言

2.2 单趟排序

2.2.1 单趟排序分析

单趟排序时,第一趟排序就将最大数排到了数组尾。

[数据结构 -- 手撕排序第三篇] 冒泡排序,排序算法,算法,排序算法,c语言

2.2.2 单趟排序实现代码

for (int j = 1; j < n; j++)
{
    if (a[j - 1] > a[j])
    {
        int tmp = a[j - 1];
        a[j - 1] = a[j];
        a[j] = tmp;
    }
}

3、冒泡排序完整代码实现

3.1 思路分析

我们看到单趟排序第一趟时,就将最大值排到了数组尾部,按照这样的分析,我们排n-1趟就可以实现将整个数组完全排序。

这里为什么是 n-1 趟,当倒数第二小的数字排好序后,倒数第一小的数字自然就排好。

3.2 代码实现

void bubble_sort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 1; j < n - i; j++)
		{
			if (a[j - 1] > a[j])
			{
				int tmp = a[j - 1];
				a[j - 1] = a[j];
				a[j] = tmp;
			}
		}
	}
}

4、时间复杂度

冒泡排序时间复杂度:O(N^2)。

无论是数组有序或者无序都是O(N^2),因为无论是否有序我们都需要比大小,而比大小正好是在内层循环里面,所以时间复杂度是与数组是否有序无关。

5、优化算法

5.1 优化算法思路

其实我们不难想到,如果数组是有序的,那么就不用循环那么多次了。

Q:那我们如何才能判断出数组是有序的呢?

A:其实不难,当我们数组是有序的时候就不发生交换,这就是优化算法的关键。

那么我们如何写呢?我们在内层循环外定义一个 flag = 1,假设是有序,在交换语句里我们将 flag 改为 0,当内层循环完后我们判断flag是否为1,为1就说明数组是有序的,此时就break,跳出了整个循环。

5.2 优化算法代码实现

void bubble_sort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int flag = 1;
		for (int j = 1; j < n - i; j++)
		{
			if (a[j - 1] > a[j])
			{
				flag = 0;
				int tmp = a[j - 1];
				a[j - 1] = a[j];
				a[j] = tmp;
			}
		}
		if (1 == flag)
			break;
	}
}

优化后最优的时间复杂度:O(N)此时只是第一趟循环,判断是否有序。

6、冒泡排序的特性总结

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度:O(N^2)
3. 空间复杂度:O(1)
4. 稳定性:稳定文章来源地址https://www.toymoban.com/news/detail-543672.html

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

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

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

相关文章

  • 【数据结构】排序(2)—冒泡排序 & 快速排序

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

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

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

    2024年01月19日
    浏览(50)
  • 【数据结构】手撕排序NO.1----排序初识

    目录  一. 前言 二. 排序的概念及运用         2.1 排序的概念         2.2 排序的运用         2.3 常见的排序算法 三. 冒泡and选择排序         3.1 冒泡排序         3.2 选择排序 四. 各大排序算法的复杂度和稳定性        从本期开始,我们的数据结构将迎来一个新的

    2024年02月16日
    浏览(57)
  • [数据结构 -- 手撕排序第一篇] 插入排序

    目录 1、常见的排序算法 2、插入排序的思路 2.1 基本思想 2.2 直接插入排序 2.2.1 单趟排序的思路 2.2.2 单趟排序代码实现 3、插入排序代码 4、插入排序+打印测试 5、插入排序的时间复杂度 5.1 最坏情况 5.2 最好情况 6、直接插入排序的特性总结   直接插入排序是一种简单的插入

    2024年02月12日
    浏览(56)
  • 【数据结构】排序之交换排序(冒泡 | 快排)

    在之前的博客中介绍了插入排序,有需要的可以点这个链接: link,这次来介绍交换排序,包括冒泡和快排。 话不多说,正文开始。 基本思想 :所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。 交换排序的特点是:将键值较大的记录向序

    2024年02月03日
    浏览(38)
  • 数据结构算法练习 插入排序 冒泡排序

    插入排序 代码如下  package main import \\\"fmt\\\" func main() {     a := []int{4, 5, 6, 1, 3, 2}         b := insert(a)     for i := 0; i len(b); i++ {         fmt.Println(b[i])     } } func insert(a []int) []int {     if len(a) = 1 {                   如果数组长度小于等于1 不用排序直接返回          retur

    2024年02月08日
    浏览(58)
  • 数据结构算法--2 冒泡排序,选择排序,插入排序

    思想就是将相邻元素两两比较,当一个元素大于右侧相邻元素时,交换他们的位置,小于右侧元素时,位置不变,最终序列中的最大元素,像气泡一样,到了最右侧。 这时冒泡排序第一轮结束,数列最右侧元素9的位置可认为是一个有序区,有序区目前有一个元素. 第二轮排序

    2024年02月13日
    浏览(64)
  • (搞定)排序数据结构(1)插入排序 选择排序+冒泡排序

    目录 本章内容如下    一:插入排序                               1.1插入排序                   1.2希尔排序     二:选择排序                    2.1选择排序  三:交换排序                    3.1冒泡排序         1.1直接插入排序   

    2024年02月07日
    浏览(65)
  • 【数据结构--八大排序】之冒泡排序+选择排序+插入排序

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 🔸每次从a]0]开始,

    2024年02月07日
    浏览(259)
  • 数据结构(c)冒泡排序

     本文除了最下面的代码是我写的,其余是网上抄写的。   冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排

    2024年01月17日
    浏览(29)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包