DSA - 冒泡排序(Bubble Sort)_数据结构和算法 - WIKI教程

冒泡排序从前两个元素开始，比较它们以检查哪一个更大。

.现在我们应该研究一下泡沫排序的一些实际方面。

. 我们进一步假设swap函数交换给定数组元素的值。

WIKI教程 首页 WIKI工具 学习敏捷数据科学 学习Apex 学习Arduino 学习汇编 学习Awk C标准库 学习Clojure 学习COBOL 学习计算机编程 学习C++ C++标准库 学习C 学习C＃ 学习dart_programming 学习D. 目录 目录 DSA-教程 DSA-概述 DSA-环境设置(EnvironmentSetup) DSA-算法基础(AlgorithmsBasics) DSA-渐近分析(AsymptoticAnalysis) DSA-贪婪算法(GreedyAlgorithms) DSA-分而治之(DivideandConquer) DSA-动态编程(DynamicProgramming) DSA-数据结构基础(DataStructureBasics) DSA-阵列数据结构(ArrayDataStructure) DSA-链接列表基础知识(LinkedListBasics) DSA-双重链接列表(DoublyLinkedList) DSA-循环链接列表(CircularLinkedList) DSA-Stack DSA-表达式解析(ExpressionParsing) DSA-Queue DSA-线性搜索(LinearSearch) DSA-二进制搜索(BinarySearch) DSA-插值搜索(InterpolationSearch) DSA-哈希表(HashTable) DSA-排序算法(SortingAlgorithms) DSA-冒泡排序(BubbleSort) DSA-插入排序(InsertionSort) DSA-选择排序(SelectionSort) DSA-合并排序(MergeSort) DSA-ShellSort(ShellSort) DSA-快速排序(QuickSort) DSA-图形数据结构(GraphDataStructure) DSA-深度优先遍历(DepthFirstTraversal) DSA-广度优先遍历(BreadthFirstTraversal) DSA-树数据结构(TreeDataStructure) DSA-树遍历(TreeTraversal) DSA-二进制搜索树(BinarySearchTree) DSA-AVLTree DSA-生成树(SpanningTree) DSA-Heap DSA-递归基础(RecursionBasics) DSA-河内塔(TowerofHanoi) DSA-Fibonacci系列(FibonacciSeries) DSA-问题与解答(QuestionsandAnswers) DSA-快速指南 DSA-有用的资源 DSA-讨论 关闭 WIKI教程 数据结构和算法 DSA-冒泡排序(BubbleSort) DSA-冒泡排序(BubbleSort) 冒泡排序是一种简单的排序算法。

该排序算法是基于比较的算法，其中比较每对相邻元素，并且如果元素不按顺序则交换元素。

该算法不适用于大数据集，因为其平均和最差情况复杂度为0（n2），其中n是项目数。

冒泡排序如何工作？我们以一个未排序的数组为例。

冒泡排序花费Ο（n2）时间，因此我们保持简短和精确。

冒泡排序从前两个元素开始，比较它们以检查哪一个更大。

在这种情况下，值33大于14，因此它已经在已排序的位置。

接下来，我们将33与27进行比较。

我们发现27小于33并且必须交换这两个值。

新数组应如下所示-接下来我们比较33和35.我们发现两者都处于已排序的位置。

然后我们转到接下来的两个值，35和10。

我们当时知道10小了35.因此它们没有排序。

我们交换这些值。

我们发现我们已经到了数组的末尾。

一次迭代后，数组应如下所示-确切地说，我们现在展示了每次迭代后数组的外观。

在第二次迭代之后，它应该看起来像这样-请注意，在每次迭代后，至少有一个值在末尾移动。

当不需要交换时，bubblesorts会知道数组是完全排序的。

现在我们应该研究一下泡沫排序的一些实际方面。

算法(Algorithm)我们假设list是n元素的数组。

我们进一步假设swap函数交换给定数组元素的值。

beginBubbleSort(list) forallelementsoflist iflist[i]>list[i+1] swap(list[i],list[i+1]) endif endfor returnlist endBubbleSort 伪代码(Pseudocode)我们在算法中观察到，冒号排序比较每对数组元素，除非整个数组按升序完全排序。

这可能会导致一些复杂性问题，例如，如果所有元素都已经提升，那么数组不需要更多交换。

为了解决问题，我们使用一个swapped标志变量，它将帮助我们查看是否发生了任何交换。

如果没有发生交换，即数组不再需要进行排序处理，它将退出循环。

BubbleSort算法的伪代码可以写成如下-procedurebubbleSort(list:arrayofitems) loop=list.count; fori=0toloop-1do: swapped=false forj=0toloop-1do: /*comparetheadjacentelements*/ iflist[j]>list[j+1]then /*swapthem*/ swap(list[j],list[j+1]) swapped=true endif endfor /*ifnonumberwasswappedthatmeans arrayissortednow,breaktheloop.*/ if(notswapped)then break endif endfor endprocedurereturnlist 实现(Implementation)我们在原始算法及其即兴伪代码中未解决的另一个问题是，在每次迭代之后，最高值在数组末尾处稳定下来。

因此，下一次迭代不需要包括已经排序的元素。

为此，在我们的实现中，我们限制内部循环以避免已经排序的值。

要了解C编程语言中的冒泡排序实现，请单击此处。

DSA-排序算法(SortingAlgorithms) DSA-插入排序(InsertionSort).下一篇> 编程技术 JAVA技术 PYTHON编程 WEB开发 脚本语言 ↑回到顶部↑ WIKI教程@2018