冒泡排序 算法
算法思路:
- 从第一个元素开始遍历,比较当前元素和下一个元素的大小
- 不符合,则交换
- 结束最后一个元素,则重新遍历
实现:
void bubble_sort(vector<int> &arr) {for (int i = 0;i < arr.size() - 1; ++i) {//交换size - 1次for (int j = 0;j < arr.size() - 1; ++j) {if (arr[j] > arr[j+1]) {swap(arr[j],arr[j+1]);}} }
}
优化一:
每遍历完一次,查看是否已经提前完成排序
void bubble_sort(vector<int> &arr) {bool judge = false;for (int i = 0;i < arr.size() - 1 && !judge; ++i) {judge = true;for (int j = 0;j < arr.size() - 1; ++j) {if (arr[j] > arr[j+1]) {swap(arr[j],arr[j+1]);judge = false;}}}
}
优化二:
每遍历完一次,最后一个元素为最终排序,即每次都可以减少一个元素
void bubble_sort(vector<int> &arr) {for (int i = 0;i < arr.size() - 1; ++i) {//交换size - 1次for (int j = 0;j < arr.size() - i; ++j) {if (arr[j] > arr[j+1]) {swap(arr[j],arr[j+1]);}} }
}
优化三:
正向循环移动最大元素到末尾
逆向循环移动最小元素到开头
void bubble_sort(vector<int>& arr){int beg = 0;int end = arr.size()-1;while(beg<end){int nbeg = beg, nend = end;//正向循环for(int i=beg;i<end;i++){if(arr[i]>arr[i+1]){nend=i;swap(arr[i],arr[i+1]);}}if(nend==end) break;end = nend;//逆向循环for(int i=end; i>beg;i--){if(arr[i]<arr[i-1]){nbeg=i;swap(arr[i], arr[i-1]);}}if(nbeg==beg) break;beg = nbeg;}
}
算法分析
时间复杂度:
逆向排序时最差为 O(n^2),即每个元素都需要交换
空间复杂度:
O(1),swap时的临时变量
相关文章:

5单个编译总会编译全部_5分钟读懂JavaScript预编译
大家都知道JavaScript是解释型语言,既然是解释型语言,就是编译一行,执行一行,那又何来预编译一说呢?脚本执行js引擎都做了什么呢?今天我们就来看看吧。1-JavaScript运行三部曲语法分析预编译解释执行语法分析很简单&a…

2014百度面试题目---“求比指定整数大且最小的不重复数”解答
题目:给定任意一个正整数,求比这个数大且最小的“不重复数”,“不重复数”的含义是相邻两位不相同,例如1101是重复数,而1201是不重复数。 代码: #include <iostream> using namespace std;bool istha…

3DMAX 批量 场景 对象 导出 .X格式 脚本
一、首先你需要下载一个 Total Commader文件管理软件。利用这个软件你可以收集文件夹下包含子文件夹下的max文件(或完整路径)打开TotalCMD后使用查找文件:(如图红框中的操作)1.2.3. 复制文件名和完整路径后粘贴到文本文…

C++复数类面向对象的参考
#include <bits/stdc.h> #include <future> #include <thread>using namespace std;class Complex { public:Complex (double r 0, double i 0): re (r), im (i) {} ///冒号后面是初始化的过程,注意分清初始化和赋值的区别Comp…

快速排序 算法
算法思路 序列终任意选择一个数,把序列分为比这个数大和比这个数小的两个子序列不断重复以上步骤(递归) 代码实现 int partition1(vector<int> &arr, int begin , int end) {int ret arr[begin];int index begin 1;for (int i index;i < end; i…

利用Spring AOP与JAVA注解为系统增加日志功能
Spring AOP一直是Spring的一个比较有特色的功能,利用它可以在现有的代码的任何地方,嵌入我们所想的逻辑功能,并且不需要改变我们现有的代码结构。 鉴于此,现在的系统已经完成了所有的功能的开发,我们需要把系统的操作日…

maven引入hadoop_如何添加Hadoop依赖通过Maven
匿名用户1级2017-09-09 回答Hadoop开发中需要用到至少不下10个的依赖包,它们相互间的依赖关系比较复杂,不同版本的依赖关系也有所不同,而间接依赖导致的程序错误并不会在运行之前报错,因此确定适合一个版本的依赖包,会…

js 闭包作用
2019独角兽企业重金招聘Python工程师标准>>> 一、变量的作用域 要理解闭包,首先必须理解Javascript特殊的变量作用域。 变量的作用域无非就是两种:全局变量和局部变量。 Javascript语言的特殊之处,就在于函数内部可以直接读取全…

vue实用组件——页面公共头部
可伸缩自适应的页面头部,屏幕适应范围更广泛 效果如下: 代码如下: <template> <div class"site-header"> <div class"logo"><img src"/assets/icons/logo.png" alt"">&…

插入排序 算法
算法思路 维护一段有序数列同时遍历待排序数列,在有序数列中找到合适的位置插入元素 基本代码 实现如下: void insertion(vector<int>& arr){for(int i1;i<arr.size();i){int tempi;for(int ji-1;j>0;j--){//有序序列不断得增加if(arr[temp]<…

线段树入门【转】
文章来自 : http://blog.csdn.net/x314542916/article/details/7837276 学习算法,自己收藏着。 线段树的入门级 总结 线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的…

python自动化框架pytest pdf_pytest+python下的UI自动化基础框架
整体设计模式:config目录:存放一些公共的静态文件,如项目名称,配置文件等这些环境变量(可以用其他组件替换,如sql,主要能把配置文件的内容被程序识别)。httptrquest目录:存放接口代码࿰…

ny520 最大素因子 筛选法求素数
最大素因子时间限制:1000 ms | 内存限制:65535 KB难度:2 描述 GreyAnts最近正在学习数论中的素数,但是现在他遇到了一个难题:给定一个整数n,要求我们求出n的最大素因子的序数,例如:2的序数是1,3的序数是2…

JAVA_SE之内部类
内部类分类: 1. 成员内部类 静态内部类 非静态内部类 2. 局部内部类 3. 匿名内部类 1. 成员内部类: package com.atguigu.java; /** 类的第5个成员:内部类* 1.相当于说,我们可以在类的内部再定义类。外面的类:外部类。…

希尔排序 算法
算法思路 插入排序的改进版,选择插入距离远的元素选择一个间距,将序列分成很多子序列并行插入排序降低间距,并重复插入元素,直到间距将为1,完成排序。 算法实现 void shell_sort(vector<int> &arr, int b…

解决Apache CXF 不支持传递java.sql.Timestamp和java.util.HashMap类型问题
在项目中使用Apache开源的Services Framework CXF来发布WebService,CXF能够很简洁与Spring Framework 集成在一起,在发布WebService的过程中,发布的接口的入参有些类型支持不是很好,比如Timestamp和Map。这个时候我们就需要编写一…

python教学上机实验报告怎么写_Python基础(下)
不要忘了冒号啊!!!!!对于基本数据类型的变量,变量传递给函数后,函数会在内存中复制一个新的变量,从而不影响原来的变量。(我们称此为值传递)但是对于表来说,表传递给函数…

比较有用的样式
背景图水平垂直居中 background:#ebebeb url(/Images/BlogHTImg/bkht_jia.jpg) center center no-repeat; 背景图居左垂直居中 background:#ebebeb url(/Images/BlogHTImg/bkht_jia.jpg) left center no-repeat; background:#ebebeb url(/Images/BlogHTImg/bkht_jia.jpg) 5px…
Python:线程之定位与销毁
背景 开工前我就觉得有什么不太对劲,感觉要背锅。这可不,上班第三天就捅锅了。 我们有个了不起的后台程序,可以动态加载模块,并以线程方式运行,通过这种形式实现插件的功能。而模块更新时候,后台程序自身不…

选择排序 算法
算法思路 维护一段有序数列,同时遍历待排序数列,找到最小的元素插入有序数列中重复,直到待排序数列没有剩余元素 代码实现 void select_sort(vector<int> &arr) {for (int i 0;i < arr.size(); i) {int temp arr[i];int in…

hdu2236 无题II 最大匹配 + 二分搜索
中文题目,题意大家都明白。 看到“不同的行和列”就觉得要用二分匹配来做。要求最大值与最小值的差值最小,是通过枚举边的下限和上限来完成。 枚举过程是这样的,在输入的过程可以记录下边权的最大值MAX和最小值MIN。那么他们的边权的差值的最…

python十大标准_python对标准类型的分类
python的标准类型可以按照三种方式分类。一、按存储模型分类按存储模型分可以分为原子(标量)类型和容器类型。原子(标量)类型指对象(这里的对象不是对象数据类型,而是任何可能的值)的值只能含有一种数据类型,比如数值和字符串。容器类型指它们的值可以含…

mysql慢查询开启及分析方法
最近服务维护的公司的DB服务器,总是会出现问题,感觉需要优化一下了,登陆上去,发现慢查询日志都没有开,真是惭愧, 故果断加上慢查询日志,经过分析sql记录,发现问题很多,开…

如何在调试页面的时候清除页面的缓存?
1.按F12,弹出下图 2.点击右上角的三个点: 3.点击settings 4.找到Network,下面的Disable cache(while DevTools is open) 转载于:https://www.cnblogs.com/studybrother/p/10396990.html

JAVA图片处理--缩放,切割,类型转换
import java.io.*; import java.awt.*; import java.awt.image.*; import java.awt.Graphics; import java.awt.color.ColorSpace; import javax.imageio.ImageIO;public class ChangeImageSize {/** *//*** 缩放图像* param srcImageFile 源图像文件地址* param result …

文本框自动提示_Excel办公小技巧,使用艺术字与文本框,就是那么的简单
Excel中的艺术字同时拥有文字和图形两种对象的属性,不仅可以修改其中的内容,还可以调整形状的大小、设置边框以及内部填充等效果,常在编辑表格标题或者输入一些比较有提示性的文本时使用,在突出关键内容的同时美化表格效果添加艺术…

Linux之父盟友分道扬镳 直言开源模式软肋
Linux之父盟友分道扬镳 直言开源模式软肋2005-09-06 12:53:00标签:linux职场开源休闲从1993年起,Larry McVoy就一直是Linux之父Linus Torvalds最忠实的盟友之一。 然而经历了这些年后,McVoy开始相信,开源这种风靡一时、纷纷被…

身份证第18位计算
本文计算方式源自 百度百科,根据计算方式,Java计算代码如下文所示。 计算方法 1、将前面的身份证号码17位数分别乘以不同的系数。从第一位到第十七位的系数分别为:7-9-10-5-8-4&…

归并排序 算法
算法思路 将一个数列不断拆分为子序列,直到只剩下0或者1个元素再将子序列按顺序合并为原来数列的大小,完成排序 代码实现 //合并两个有序数组 vector<int> merge_two_sort(vector<int> &arr1, vector<int> &arr2) {vector&…
DRBD配置参数
用户手册:http://www.drbd.org/users-guide语法及详解参数:http://www.drbd.org/users-guide-emb/re-drbdconf.html官方示例:http://www.drbd.org/users-guidedrbd及其配置文件中的相关名词: failover:失效转移。通俗地…