冒泡排序及冒泡排序的优化->鸡尾酒排序

2023-10-28 16:10

本文主要是介绍冒泡排序及冒泡排序的优化->鸡尾酒排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

什么是冒泡排序

冒泡排序的英文Bubble Sort,是一种最基础的交换排序。
大家一定都喝过汽水,汽水中常常有许多小小的气泡,哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻,所以小气泡可以一点一点向上浮动。
冒泡排序(Bubble Sorting)的基本思想是:通过对待排序序列从前向后(从下标较小的元素开始),依次比较 相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就象水底下的气泡一样逐渐向上冒。

演示冒泡过程的例子(图解)

在这里插入图片描述

小结上面的图解过程:
(1) 一共进行 数组的大小-1 次大的循环
(2)每一趟排序的次数在逐渐的减少
(3) 如果我们发现在某趟排序中,没有发生一次交换, 可以提前结束冒泡排序。这个就是优化

冒泡排序第一版

#include <iostream>
#include <string>
using namespace std;
/*数组遍历*/
void ListShow(int list[], int length){for (int i = 0; i < length; i++){cout << list[i] << "  ";}cout << endl;
}
/*==================冒泡排序==========================*/
void BubbleSort(int *list, int length)
{int temp; //定义中间变量cout << "====冒泡排序=====" << endl;for (int i = 0; i < length - 1; i++){ //数组长度为n,冒泡排序比较n-1趟//每趟中,数据两两比较,大的往后移for (int j = 0; j < length - i - 1; j++){if (list[j] > list[j + 1]){ //交换,从小往大,若>从大往小temp = list[j];list[j] = list[j + 1];list[j + 1] = temp;}}cout << "第" << i + 1 << "趟: ";ListShow(list, length);}
}
int main()
{int list[9] = {9, 3, 1, 4, 2, 7, 8, 6, 5};int length = sizeof(list) / sizeof(list[0]); //求数组的长度,C++固定方式cout << "排序前" << endl;ListShow(list, length);BubbleSort(list, length);cout << "排序后" << endl;ListShow(list, length);return 0;
}

冒泡排序第二版

这一版代码做了小小的改动,利用布尔变量flag作为标记。如果在本轮排序中,元素有交换,则说明数列无序;如果没有元素交换,说明数列已然有序,直接跳出大循环。

#include <iostream> //冒泡优化第二版,解决整体有序还在排问题
#include <string>
using namespace std;
void listshow(int list[], int length)
{for (int i = 0; i < length; i++){cout << list[i] << "  ";}cout << endl;
}
void bubblesort(int array[], int length)
{int temp;for (int i = 0; i < length - 1; i++){bool flage = true;for (int j = 0; j < length - i - 1; j++){if (array[j] > array[j + 1]){temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;flage = false;}}if (flage){break;}else{cout << "第" << i + 1 << "次" << endl;listshow(array, length);}}
}int main()
{int a[7] = {3, 4, 1, 5, 6, 7, 8};int b = sizeof(a) / sizeof(a[0]);cout << "排序前" << endl;listshow(a, b);bubblesort(a, b);cout << "排序后" << endl;listshow(a, b);
}

冒泡排序第三版

为了说明这个问题,我们重新选择一个新的数列:
3 4 2 1 5 6 7 8
这个数列的特点是前半部分(3,4,2,1)无序,后半部分(5,6,7,8)升序,并且后半部分
的元素已经是数列最大值。
让我们按照冒泡排序的思路来进行排序,看一看具体效果:
第一轮
元素3和4比较,发现3小于4,所以位置不变。
元素4和2比较,发现4大于2,所以4和2交换。
元素4和1比较,发现4大于1,所以4和1交换。
元素4和5比较,发现4小于5,所以位置不变。
元素5和6比较,发现5小于6,所以位置不变。
元素6和7比较,发现6小于7,所以位置不变。
元素6和7比较,发现6小于7,所以位置不变。
第一轮结束,数列有序区包含一个元素:3 2 1 4 5 6 7 8
第二轮
元素3和2比较,发现3大于2,所以3和2交换。
元素3和4比较,发现3小于4,所以位置不变。
元素4和5比较,发现4小于5,所以位置不变。
元素5和6比较,发现5小于6,所以位置不变。
元素6和7比较,发现6小于7,所以位置不变。
元素7和8比较,发现7小于8,所以位置不变。
第二轮结束,数列有序区包含一个元素:2 1 3 4 5 6 7 8

这个问题的关键点在哪里呢?关键在于对数列有序区的界定。
按照现有的逻辑,有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1,第二轮排序过后的有序区长度是2 …
实际上,数列真正的有序区可能会大于这个长度,比如例子中仅仅第二轮,后面5个元素实际都已经属于有序区。因此后面的许多次元素比较是没有意义的。
如何避免这种情况呢?我们可以在每一轮排序的最后,记录下最后一次元素交换的位置,那个位置也就是无序数列的边界,再往后就是有序区了。

#include <iostream> //冒泡优化第三版,后面部分已经有序
#include <string>
using namespace std;
void ListShow(int list[], int length)
{for (int i = 0; i < length; i++){cout << list[i] << "  ";}cout << endl;
}
void BubbleSort(int array[], int length)
{int t;int lastchange = 0; //记录最后一次交换的位置for (int i = 0; i < length - 1; i++){bool flage = true;				//有序标记,每一轮的初始是trueint sortbuder = length - i - 1; //无序数列的边界,每次比较只需要比到这里为止for (int j = 0; j < sortbuder; j++){if (array[j] > array[j + 1]){t = array[j];array[j] = array[j + 1];array[j + 1] = t;flage = false;		//有元素交换,所以不是有序,标记变为falselastchange = j + 1; //把无序数列的边界更新为最后一次交换元素的位置}}if (flage){break;}else{cout << "第" << i + 1 << "次" << endl;sortbuder = lastchange;ListShow(array, length);}}
}
int main()
{int a[] = {1, 44, 4, 5, 64, 34, 35, 36, 39};int b = sizeof(a) / sizeof(a[0]);cout<<"排序前"<<endl;ListShow(a, b);BubbleSort(a, b);cout<<"排序后"<<endl;ListShow(a, b);
}

这一版代码中,sortBorder就是无序数列的边界。每一轮排序过程中,sortBorder之后的元素就完全不需要比较了,肯定是有序的。

冒泡排序第四版(鸡尾酒排序)

鸡尾酒排序的元素比较和交换过程是双向的。
让我们来举一个栗子:
在这里插入图片描述
有8个数组成一个无序数列:2,3,4,5,6,7,8,1,希望从小到大排序
如果按照冒泡排序的思想,排序的过程是什么样呢?
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

可以看到从2到8已经是有序的了,只有1元素的位置不对,缺还要进行7轮排序,这也太憋屈了吧?
鸡尾酒排序正是解决这种问题

鸡尾酒的详细过程

第一轮(和冒泡排序一样,8和1交换)
在这里插入图片描述
第二轮
此时开始不一样了,我们反过来从右往左比较和交换:
8已经处于有序区,我们忽略掉8,让1和7比较。元素1小于7,所以1和7交换位置:
在这里插入图片描述
接下来1和6比较,元素1小于6,所以1和6交换位置
在这里插入图片描述
接下来1和5比较,元素1小于5,所以1和5交换位置:
在这里插入图片描述
接下来1和4交换,1和3交换,1和2交换,最终成为了下面的结果:
在这里插入图片描述
第三轮(虽然已经有序,但是流程并没有结束)
鸡尾酒排序的第三轮,需要重新从左向右比较和交换:
1和2比较,位置不变;2和3比较,位置不变;3和4比较,位置不变…6和7比较,位置不变。
没有元素位置交换,证明已经有序,排序结束。

这就是鸡尾酒排序的思路。排序过程就像钟摆一样,第一轮从左到右,第二轮从右到左,第三轮再从左到右…

#include <iostream> //鸡尾酒排序,先从左向右,后从右向左
#include <string>
using namespace std;
void ListShow(int list[], int length)
{for (int i = 0; i < length; i++){cout << list[i] << "  ";}cout << endl;
}
void BubbleSort(int array[], int length)
{int t;for (int i = 0; i < length / 2; i++) //因为左右排序所以只需进行一半排序就可以了{cout << "第" << i + 1 << "趟" << endl;//奇数轮,从左向右比较和交换bool flage = true;for (int j = 0; j < length - i - 1; j++){if (array[j] > array[j + 1]){t = array[j];array[j] = array[j + 1];array[j + 1] = t;flage = false;}}if (flage){break;}else{cout << "从左到右第" << i + 1 << "次" << endl;ListShow(array, length);}//偶数轮之前,重新标记为trueflage = true;//偶数轮,从右向左比较和交换for (int j = length - i - 1; j > i; j--){if (array[j] < array[j - 1]){t = array[j];array[j] = array[j - 1];array[j - 1] = t;flage = false;}}if (flage){break;}else{cout << "从右到左第" << i + 1 << "次" << endl;ListShow(array, length);}}
}
int main()
{int a[] = {2, 3, 4, 5, 6, 7, 1, 8};int b = sizeof(a) / sizeof(a[0]);cout << "排序前" << endl;ListShow(a, b);BubbleSort(a, b);cout << "排序后" << endl;ListShow(a, b);
}

这段代码是鸡尾酒排序的原始实现。代码外层的大循环控制着所有排序回合,大循环内包含两个小循环,第一个循环从左向右比较并交换元素,第二个循环从右向左比较并交换元素。

冒泡排序第五版

鸡尾酒排序的优化

对于单向的冒泡排序,我们需要设置一个边界值,对于双向的鸡尾酒排序,我们需要设置两个边界值。请看代码:

#include <iostream> //鸡尾酒排序优化,先从左向右,后从右向左,优化
using namespace std;
void ListShow(int list[], int length)
{for (int i = 0; i < length; i++){cout << list[i] << "  ";}cout << endl;
}
void BubbleSort(int array[], int length)
{int LastRightExchange = 0; //记录右侧最后一次交换的位置int LastLeftExchange = 0;  //记录左侧最后一次交换的位置int LeftSortBorder = 0;	   //无序数列的左边界,每次比较只需要比到这里为止int RightSortBorder;	   //无序数列的右边界,每次比较只需要比到这里为止int t;for (int i = 0; i < length / 2; i++) //因为左右排序所以只需进行一半排序就可以了{cout << "第" << i + 1 << "趟" << endl;bool flage = true; //有序标记,每一轮的初始是trueRightSortBorder = length - i - 1;//奇数轮,从左向右比较和交换for (int j = LeftSortBorder; j < RightSortBorder; j++){if (array[j] > array[j + 1]){t = array[j];array[j] = array[j + 1];array[j + 1] = t;flage = false;LastRightExchange = j + 1;}}RightSortBorder = LastRightExchange;if (flage){break;}else{cout << "从左到右第" << i + 1 << "次" << endl;ListShow(array, length);}//偶数轮之前,重新标记为trueflage = true;//偶数轮,从右向左比较和交换for (int j = RightSortBorder; j > LeftSortBorder; j--){if (array[j] < array[j - 1]){t = array[j];array[j] = array[j - 1];array[j - 1] = t;flage = false;LastLeftExchange = j - 1;}}LeftSortBorder = LastLeftExchange;if (flage){break;}else{cout << "从右到左第" << i + 1 << "次" << endl;ListShow(array, length);}}
}
int main()
{int a[] = {2, 3, 4, 5, 6, 7, 1, 8};int b = sizeof(a) / sizeof(a[0]);cout << "排序前" << endl;ListShow(a, b);BubbleSort(a, b);cout << "排序后" << endl;ListShow(a, b);
}

这篇关于冒泡排序及冒泡排序的优化->鸡尾酒排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/294371

相关文章

Vue3 的 shallowRef 和 shallowReactive:优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉,那么对 shallowRef 和 shallowReactive 是否了解呢? 在编程和数据结构中,“shallow”(浅层)通常指对数据结构的最外层进行操作,而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素,而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层(Shallow) 定义

HDFS—存储优化(纠删码)

纠删码原理 HDFS 默认情况下,一个文件有3个副本,这样提高了数据的可靠性,但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码,采用计算的方式,可以节省约50%左右的存储空间。 此种方式节约了空间,但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件,都会执行此策略。 默认只开启对 RS-6-3-1024k

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

MySQL高性能优化规范

前言:      笔者最近上班途中突然想丰富下自己的数据库优化技能。于是在查阅了多篇文章后,总结出了这篇! 数据库命令规范 所有数据库对象名称必须使用小写字母并用下划线分割 所有数据库对象名称禁止使用mysql保留关键字(如果表名中包含关键字查询时,需要将其用单引号括起来) 数据库对象的命名要能做到见名识意,并且最后不要超过32个字符 临时库表必须以tmp_为前缀并以日期为后缀,备份

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

查看原文>>>全流程SWAP农业模型数据制备、敏感性分析及气候变化影响实践技术应用 SWAP模型是由荷兰瓦赫宁根大学开发的先进农作物模型,它综合考虑了土壤-水分-大气以及植被间的相互作用;是一种描述作物生长过程的一种机理性作物生长模型。它不但运用Richard方程,使其能够精确的模拟土壤中水分的运动,而且耦合了WOFOST作物模型使作物的生长描述更为科学。 本文让更多的科研人员和农业工作者

从状态管理到性能优化:全面解析 Android Compose

文章目录 引言一、Android Compose基本概念1.1 什么是Android Compose?1.2 Compose的优势1.3 如何在项目中使用Compose 二、Compose中的状态管理2.1 状态管理的重要性2.2 Compose中的状态和数据流2.3 使用State和MutableState处理状态2.4 通过ViewModel进行状态管理 三、Compose中的列表和滚动

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In