冒泡排序法及其优化

小灰灰 2022-07-13 09:12 192阅读 0赞

本文介绍的是冒泡排序法对数组进行排序  
下面第一个源程序是谭浩强那本书上的冒泡排序法，它的时间时间复杂度是O(n2)  
  
  
源程序：  
\#include <stdio.h>  
int main()  
\{  
int a\[5\];  //定义一个长度为5的数组  
int i, j, t;  
for (i=0; i<5; i++) //人为输入  
\{  
scanf("%d", &a\[i\]);  
\}  
  
for (i=0; i<4; i++)   
\{  
for (j=0; j<4-i; j++)  
\{  
if (a\[j\] > a\[j+1\])  
\{  
t = a\[j\];  
a\[j\] = a\[j+1\];  
a\[j+1\] = t;  
\}  
\}  
\}  
printf("\\n冒泡排序：\\n");  
for (i=0; i<5; i++)  
\{  
printf("%d\\n", a\[i\]);  
\}  
return 0;  
\}

运行后的结果：

![Center][]

下面介绍一下优化后的程序，就是添加一个flag标志变量，检查是否在整个排序的过程中已经提前排序完全了。  
  
  
源代码：  
\#include <stdio.h>  
int main()  
\{  
int a\[5\];  
int i, j, t;  
int flag=1;  
  
  
for (i=0; i<5; i++)  
\{  
scanf("%d", &a\[i\]);  
\}  
  
for (i=0; i<4&&flag; i++)  
\{  
flag = 0;  
for (j=0; j<4-i; j++)  
\{  
if (a\[j\] > a\[j+1\])  
\{  
t = a\[j\];  
a\[j\] = a\[j+1\];  
a\[j+1\] = t;  
flag = 1;  
\}  
\}  
\}  
printf("\\n冒泡排序：\\n");  
for (i=0; i<5; i++)  
\{  
printf("%d\\n", a\[i\]);  
\}  
return 0;  
\}  
  
  
运行后的结果：

![Center 1][]

总结：通过加上flag标志变量后，会使得算法更加的有效率。最好时的时间复杂度是O(n)，而传统的冒泡排序则永远都是O(n2)的时间复杂度。

[Center]: /images/20220713/a5b41a975539451eae4c4adb3f019198.png
[Center 1]: /images/20220713/afdd71760fee42b59bdc0d7dbb2abb15.png

发表评论取消回复

表情：

评论列表（有 0 条评论，192人围观）

还没有评论，来说两句吧...

相关阅读

相关冒泡排序及其优化

偶然看了一篇写的比较好冒泡排序优化的博客，自己整理了一下，分享给大家，一起学习。若有错误，欢迎大家指正~ **冒泡排序(BubbleSort)** ![在这...

深碍√TFBOYSˉ_/ 2024年04月18日 19:51/ 0 赞/ 90 阅读

相关排序算法之冒泡排序及其优化

　　冒泡排序　　思想　　比较相邻两个元素，如果前面的元素比后面的元素大，则交换位置。最后一个元素必定会是最大值。　　排除掉最后一位元素，继续循环，直至没有元素需要比

淩亂°似流年/ 2024年04月03日 13:59/ 0 赞/ 118 阅读

相关【python】实现冒泡排序及其优化

python 实现冒泡排序冒泡排序是一种常见的排序算法，相对来说比较简单。它的基本思想是比较相邻的元素，如果顺序不对就交换它们的位置，这样一轮下来可以确保最大（或最小）

比眉伴天荒/ 2024年03月25日 17:44/ 0 赞/ 100 阅读

相关冒泡排序及其优化

前言本文将简单介绍冒泡排序及其优化版本，`默认从小到大顺序` 什么是冒泡排序冒泡排序是一种简单且经典的排序算法。基本思想：是通过反复交换相邻的未按顺序

╰+哭是因爲堅強的太久メ/ 2024年03月08日 08:46/ 0 赞/ 101 阅读

相关排序算法之冒泡排序及其优化

> 冒泡排序： > 依次取出数组中的每个元素，将此元素与其之后的每个元素比较，若大于其后的元素，则交换位置 > 双重循环： > 外层循

小咪咪/ 2022年11月02日 11:40/ 0 赞/ 224 阅读

相关冒泡排序法

package com.wdl.day07; import java.util.Arrays; / @创建人 wdl @创建时间

r囧r小猫/ 2022年09月04日 01:45/ 0 赞/ 255 阅读

相关冒泡排序算法及其优化

冒泡排序算是排序算法里面的一种较为简单的算法，也是我接触的第一种排序算法，有升序与降序之分，如果面试的时候面试官问道这个题目，一定要问清楚是升序还是降序，这样会给你加分。下

ゞ浴缸里的玫瑰/ 2022年08月22日 15:11/ 0 赞/ 206 阅读

相关冒泡排序法及其优化

本文介绍的是冒泡排序法对数组进行排序下面第一个源程序是谭浩强那本书上的冒泡排序法，它的时间时间复杂度是O(n2) 源程序： \include <std

小灰灰/ 2022年07月13日 09:12/ 0 赞/ 193 阅读

相关冒泡排序法

<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Document</

红太狼/ 2022年05月20日 02:59/ 0 赞/ 302 阅读

相关冒泡排序法

根据冒泡排序法将数组中的数从大到小排列第一次代码： include<stdio.h> include<stdlib.h> / 冒泡排序法 /

亦凉/ 2022年04月15日 00:56/ 0 赞/ 279 阅读