常见排序算法之冒泡排序及其改进_冒泡排序的改进_Surplus°的博客-程序员秘密
目录
冒泡排序
冒泡排序(BubbleSort)以其“在排序过程中相邻元素不断交换，一些元素慢慢被换到最后，看起来就像是元素在冒泡一样”而得名，是一种简单的基于关键词比较的排序算法。
算法思想
假设有n个数据，依次比较相邻两个元素，如果反序则交换位置，直到没有反序为止。
以递增序为例，每次从头开始依次比较相邻的两个元素，如果后面一个元素比前一个要大，说明顺序不对，则将它们交换，本次循环完毕之后再次从头开始扫描，直到某次扫描中没有元素交换，说明每个元素都不比它后面的元素大，至此排序完成。
时间复杂度
最好时间复杂度O(n)
最坏时间复杂度O(n2)
经典冒泡排序
代码
void MySort::BubbleSort(std::vector<int>& nums) {
int count1 = 0, count2 = 0;
int numsSize = nums.size();
for (int i = 0; i < numsSize - 1; i++) {
for (int j = 0; j < numsSize -1 - i; j++) {
count1++;
if (nums[j] > nums[j+1]){
count2++;
int tmp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = tmp;
}
}
}
std::cout << "比较次数：" << count1 << " 交换次数：" << count2 << std::endl;
}
测试
这里通过对十个随机数进行排序测试冒泡排序的结果。
#include <iostream>
#include <vector>
#include <cstdlib>//rand(),srand
#include <ctime>//time()
#include "print_data.h"
#include "mysort.h"
using namespace std;
int main()
{
srand((int)time(NULL));//随机种子
vector<int> nums,nums1;
print_data printTest;
MySort sortTest;
for (int i = 0; i < 10; i++)
{
nums.push_back(rand() % 100);//生成0-99之间的随机数
}
/*nums.push_back(1);
nums.push_back(0);
nums.push_back(2);
nums.push_back(3);
nums.push_back(4);
nums.push_back(5);
nums.push_back(6);
nums.push_back(7);
nums.push_back(8);
nums.push_back(9);
nums1 = nums;*/
printTest.printVector(nums);
sortTest.BubbleSort(nums);
printTest.printVector(nums);
/*cout << endl;
printTest.printVector(nums1);
sortTest.BubbleSort1(nums1);
printTest.printVector(nums1);*/
system("pause");
return 0;
}
结果
冒泡排序算法的改进
这里对经典冒泡排序进行改进，减少无效比较的次数。所谓无效比较就是当我们已知结果却还要去比较。如果我们多观察冒泡排序的中间过程，我们就会发现，末尾的一些元素在一定次数的扫描后已经到达最终位置了，再比较就会造成无效比较。改进方法是，记录下每次扫描中发生交换的最后一个元素位置，下一次扫描就到这里为止。
代码
void MySort::BubbleSort1(std::vector<int>& nums) {
int count1 = 0, count2 = 0;
int numsSize = nums.size();
bool flag = true;
for (int i = 0; (i < numsSize - 1) && flag; i++) {
flag = false;//标记是否已经有序
for (int j = 0; j < numsSize - 1 - i; j++) {
count1++;
if (nums[j] > nums[j + 1]) {
count2++;
flag = true;
int tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
}
}
}
std::cout << "比较次数：" << count1 << " 交换次数：" << count2 << std::endl;
}
测试
#include <iostream>
#include <vector>
#include <cstdlib>//rand(),srand
#include <ctime>//time()
#include "print_data.h"
#include "mysort.h"
using namespace std;
int main()
{
srand((int)time(NULL));//随机种子
vector<int> nums,nums1;
print_data printTest;
MySort sortTest;
for (int i = 0; i < 10; i++)
{
nums.push_back(rand() % 100);//生成0-99之间的随机数
}
/*nums.push_back(1);
nums.push_back(0);
nums.push_back(2);
nums.push_back(3);
nums.push_back(4);
nums.push_back(5);
nums.push_back(6);
nums.push_back(7);
nums.push_back(8);
nums.push_back(9);
nums1 = nums;*/
/*printTest.printVector(nums);
sortTest.BubbleSort(nums);
printTest.printVector(nums);*/
cout << endl;
printTest.printVector(nums);
sortTest.BubbleSort1(nums);
printTest.printVector(nums);
system("pause");
return 0;
}
结果
改进算法与经典算法的比较
测试
下面用一个基本有序的数组[1,0,2,3,4,5,6,7,8,9]对改进前后的算法进行比较：
#include <iostream>
#include <vector>
#include <cstdlib>//rand(),srand
#include <ctime>//time()
#include "print_data.h"
#include "mysort.h"
using namespace std;
int main()
{
srand((int)time(NULL));//随机种子
vector<int> nums,nums1;
print_data printTest;
MySort sortTest;
//for (int i = 0; i < 10; i++)
//{
// nums.push_back(rand() % 100);//生成0-99之间的随机数
//}
nums.push_back(1);
nums.push_back(0);
nums.push_back(2);
nums.push_back(3);
nums.push_back(4);
nums.push_back(5);
nums.push_back(6);
nums.push_back(7);
nums.push_back(8);
nums.push_back(9);
nums1 = nums;
printTest.printVector(nums);
sortTest.BubbleSort(nums);
printTest.printVector(nums);
cout << endl;
printTest.printVector(nums1);
sortTest.BubbleSort1(nums1);
printTest.printVector(nums1);
system("pause");
return 0;
}
结果
完整代码
mysort.h
#pragma once
#include <vector>
#include <iostream>
class MySort {
public:
void BubbleSort(std::vector<int>& nums);//经典冒泡排序
void BubbleSort1(std::vector<int>& nums);//改进冒泡排序
};
mysort.cpp
#include "mysort.h"
void MySort::BubbleSort(std::vector<int>& nums) {
int count1 = 0, count2 = 0;
int numsSize = nums.size();
for (int i = 0; i < numsSize - 1; i++) {
for (int j = 0; j < numsSize -1 - i; j++) {
count1++;
if (nums[j] > nums[j+1]){
count2++;
int tmp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = tmp;
}
}
}
std::cout << "比较次数：" << count1 << " 交换次数：" << count2 << std::endl;
}
void MySort::BubbleSort1(std::vector<int>& nums) {
int count1 = 0, count2 = 0;
int numsSize = nums.size();
bool flag = true;
for (int i = 0; (i < numsSize - 1) && flag; i++) {
flag = false;
for (int j = 0; j < numsSize - 1 - i; j++) {
count1++;
if (nums[j] > nums[j + 1]) {
count2++;
flag = true;
int tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
}
}
}
std::cout << "比较次数：" << count1 << " 交换次数：" << count2 << std::endl;
}
print_data.h
//#pragma once 两种方式防止重定义
#ifndef PRINT_DATA_H
#define PRINT_DATA_H
#include <iostream>
#include <vector>
class print_data
{
public:
print_data() = default;
~print_data() = default;
void printHello();
void printNum(int num);
void printVector(std::vector<int> nums);
private:
};
#endif // !PRINT_DATA_H
print_data.cpp
#include "print_data.h"
void print_data::printHello() {
std::cout << "print_data function!" << std::endl;
}
void print_data::printNum(int num){
std::cout << num << std::endl;
}
void print_data::printVector(std::vector<int> nums) {
int size = nums.size();
for (int i = 0; i < size; i++)
{
std::cout << nums[i] << " ";
}
std::cout << std::endl;
}
main.cpp
#include <iostream>
#include <vector>
#include <cstdlib>//rand(),srand
#include <ctime>//time()
#include "print_data.h"
#include "mysort.h"
using namespace std;
int main()
{
srand((int)time(NULL));//随机种子
vector<int> nums,nums1;
print_data printTest;
MySort sortTest;
//for (int i = 0; i < 10; i++)
//{
// nums.push_back(rand() % 100);//生成0-99之间的随机数
//}
nums.push_back(1);
nums.push_back(0);
nums.push_back(2);
nums.push_back(3);
nums.push_back(4);
nums.push_back(5);
nums.push_back(6);
nums.push_back(7);
nums.push_back(8);
nums.push_back(9);
nums1 = nums;
//经典冒泡排序
printTest.printVector(nums);
sortTest.BubbleSort(nums);
printTest.printVector(nums);
cout << endl;
//改进冒泡排序
printTest.printVector(nums1);
sortTest.BubbleSort1(nums1);
printTest.printVector(nums1);
system("pause");
return 0;
}
智能推荐
快速部署多台相同配置的linux服务器_linux每台机器都要装相同服务 怎么解决_EasonTG的博客-程序员秘密
以centos6.0 为例，前提是服务器配置基本相同，尤其是磁盘大小需一致，否则还原安装不成功。一 、安装centos6.0操作系统,假设磁盘大小为50G （1）分区布局 类型 大小 挂载点 说明 ext3 10G / 第一个分区作为系统分区，也就是用来做备份的分
基于 SoC 的卷积神经网络车牌识别系统设计（5-3）基于 Verilog 的填充层 First_Fill IP 设计_新芯设计的博客-程序员秘密
NOTES：紧接着缩放操作（Resize）之后，将缩放之后的输入特征图进行边缘填充操作（First_Fill）。输入矩阵大小为 32*32，边缘填充数值为 0，输出矩阵大小为34*34。主要有 Sim_ROM、Sel_Fill、FSM_Timer（FSM + Timer）、Delay_N、Reduce、Extend、AXI4-Stream Data FIFO 的一些 IP 模块。...
秋招复习-同步fifo_addr_width = $clog2(fifo_depth);_数字IC纯小白的博客-程序员秘密
过段时间就要秋招了，打算做一个知识汇总，也算是为秋招做准备吧首先fifo是first in first out，先进先出。可以想象成一根管子，一端往里边压入（push）小球，另一边往外边弹出（pop）小球。同步fifo一般有以下几个必备端口信号名称 端口方向 位宽 说明 clk I 1 时钟，读写端口共用 rst_n I 1 复位 winc I 1...
Android 通过按钮Button更改全部的TextView、EditText、Button的字体大小、字体颜色、背景颜色_android edittext 选中文字字号大小修改_AMinfo的博客-程序员秘密
本文实现的是自定义设置字体大小、字体颜色、背景颜色，然后通过一键全部修改整个视图内所有的TextView、EditText、Button的字体大小、字体颜色、背景颜色。实现的逻辑：通过遍历View的方式，判断View是否是TextView、EditText和Button类型，如果是的话，就修改。http://blog.csdn.net/aminfo/article/details/77
Verilog 异步FIFO设计_8bit异步fifo verilog_嗒曦的博客-程序员秘密
Verilog 异步FIFO设计
AXI2Standard_handshake_bridge 设计_axi2ahb bridge_Starry丶的博客-程序员秘密
此处研究AXI到标准握手的桥接器，实现接口转化，例如下图是的，AHB2HANDSHAKE桥是作为AHB slave呈现的，由此可以得出桥接器的输入输出之后是参数描述
随便推点
CPLD/FPGA/Verilog_FPGA设计的四种常用思想与技巧_weixin_34205076的博客-程序员秘密
转自：http://blog.csdn.net/yangtalent1206/article/details/6422715乒乓操作 “乒乓操作”是一个常常应用于数据流控制的处理技巧，典型的乒乓操作方法如图1所示。 乒乓操作的处理流程为：输入数据流通过“输入数据选择单元”将数据流等时分配到两个数据缓冲区，数据缓冲模块可以为任何存储模块，比较常用的存储单元为双口RAM(D...
FPGA入门学习笔记（二十一）Vivado功能验证FIFO_NonnettaWu的博客-程序员秘密
FPGA入门学习笔记（二十一）Vivado功能验证FIFO
plsql使用方法（主要是sql语句）_plsql怎么写sql语句_e哥的成长录的博客-程序员秘密
PLSQL_Developer使用方法及技巧1、PL/SQL&nbsp;&nbsp;Developer记住登陆密码 在使用PL/SQL&nbsp;Developer时，为了工作方便希望PL/SQL&nbsp;Developer记住登录Oracle的用户名和密码； 设置方法：PL/SQL&nbsp;Developer...
m基于3GPP-LTE通信网络的认知家庭网络Cognitive-femtocell性能matlab仿真_我爱C编程的博客-程序员秘密
本系统所涉及到的几个主要模块，具体有如下几个模块：A. Simulation Flow：仿真流程B. Initialization：初始化C. Mobility Model：移动模型D. Traffic Model：流量模型E. Propagation Model：信号传输模型F. Multipath Model：多径模型G. SINR Calculation：SINR值计算模型H. Link Level Quality Estimation：链路级质量评价。
POJ1177矩形面积并(矩形切割+括号匹配)_一个矩形能分成多个2x1的小矩形编程_ACdreamers的博客-程序员秘密
题目：http://poj.org/problem?id=1177 分析：（括号匹配）首先把矩形的上边界作为“左括号”边，下边界作为“右括号”边，然后上下排序。假定排完序之后是下面的状态：(())()(()()(())) 考虑“最外侧”的括号的数量。显然上面的那个串是(()) & () & (()()(()))有六个最外侧括号，那么边界数量就是6。排序的复杂度O(nlogn
提取视频中的音频 Python只需要三行代码！_叶庭云的博客-程序员秘密
身处数据爆炸增长的信息时代，各种各样的数据都飞速增长，视频数据也不例外。我们可以使用 python 来提取视频中的音频，而这仅仅需要安装一个体量很小的 python 库，然后执行三行代码！语音数据在数据分析领域极为重要。比如可以分析语义、口音、根据人的情绪等等。可以应用于偏好分析、谎话检测等等。一、提取音频需要用到 python 的 moviepy 库moviepy 的 github 地址：https://github.com/Zulko/moviepy命令行 pip 安装上 moviepy 即可