[排序算法] 双向冒泡排序 (C++)
2024-10-21 03:39:17
前言
本文章是建立在冒泡排序的基础上写的，如还有对 冒泡排序 不了解的童鞋，可以看看这里哦~ 冒泡排序 C++
双向冒泡排序原理
双向冒泡排序 的基本思想与 冒泡排序还是一样的。冒泡排序 每次将相邻的两个数进行比较，将较大的放到后面，每一趟比较都将当前最大的数字排到最后面，然后从头再开始进行下一趟比较。(若有 n 个数字，当完成 n - 1 趟比较后，便完成了排序)
双向冒泡排序 只不过进行了一点小小的优化。其是从左右二路并行操作，进行比较和交换。从左路进行比较的过程与冒泡排序一致，从右路进行比较则是将当前最小的数字交换到数组的最左侧。然后 (我自己是将每做一次双向冒泡视为一趟) 每一趟比较都处理掉当前最小数字和最大数字，使其完成归位，下一趟比较只需要处理中间部分就可以啦~。
虽然进行了小小的优化，但是只是稍微提高了排序的效率，只是单纯地进行双向并行比较而已，并没有大幅度缩短排序的时间。
双向冒泡排序动态演示
我们以 [8, 4, 7, 2, 5, 1] 为例进行动态演示
第一趟 向右将当前范围内最大元素放到最右侧
第一趟 向左将当前范围内最小元素放到最左侧
第二趟 向右将中间部分最大放到最右侧
第二趟 向左将中间部分最小放到最左侧
第三趟 向右 发现已经左右部分都已经有序 左右比较都不执行 left与right相等
双向冒泡排序核心代码
#include<iostream>
#include<vector>
#include<ctime>
using namespace std;
void TwoBubbleSort(vector<int> &v){
int left = 0, right = v.size() - 1, flag = 1;
//分别从左开始(将最大放到最右) 从右开始(将最小放到最左)
//flag用于记录左右已排序位置
while(left < right){
//向右
for(int i = left; i < right; i++){
if(v[i] > v[i + 1]){
swap(v[i], v[i + 1]);
flag = i;
}
}
right = flag;
//向左
for(int i = right; i > left; i--){
if(v[i] < v[i - 1]){
swap(v[i], v[i - 1]);
flag = i;
}
}
left = flag;
}
//当left==right时,即完成了排序
}
完整程序源代码
#include<iostream>
#include<vector>
#include<ctime>
using namespace std;
void TwoBubbleSort(vector<int> &v){
int left = 0, right = v.size() - 1, flag = 1;
//分别从左开始(将最大放到最右) 从右开始(将最小放到最左)
//flag用于记录左右已排序位置
while(left < right){
//向右
for(int i = left; i < right; i++){
if(v[i] > v[i + 1]){
swap(v[i], v[i + 1]);
flag = i;
}
}
right = flag;
//向左
for(int i = right; i > left; i--){
if(v[i] < v[i - 1]){
swap(v[i], v[i - 1]);
flag = i;
}
}
left = flag;
}
//当left==right时,即完成了排序
}
void show(vector<int> &v){
for(auto &x : v)
cout<<x<<" ";
cout<<endl;
}
main(){
vector<int> v;
srand((int)time(0));
int n = 50; //随机生成50个数字
while(n--)
v.push_back(rand() % 100 + 1); //数字范围[1, 100]
show(v);
TwoBubbleSort(v);
cout<<endl<<endl;
show(v);
}
程序运行结果图
最新文章
- ReactJS入门（二）—— 组件的生命周期
- 理解tcp协议的3次握手和面向连接
- ABAP程序相互调用--SUBMIT
- 2016年1月编程语言排行榜：Java荣获2015年度冠军
- iBatis系列之三
- Php Laravel框架 多表关系处理 之 Eloquent一对多关系处理
- http协议说明
- 编写javascript的基本技巧
- html分析器——jericho-html-3.3分解table
- 用编程的方式定义UI界面
- python 库安装笔记
- JAVAEE——SSH项目实战01：SVN介绍、安装和使用方法
- 【前端】深入浅出Javascript中的数值转换
- lua元表
- VS 2008 开发WinCE程序 编译部署速度慢的解决办法
- 存储那些事儿（二）: 下一代Linux文件系统BTRFS简介
- logging模块--日志文件
- Linux 的 OOM 终结者(Out Of Memory killer)
- lenet-5
- Linux服务器---流量监控bandwidthd