东莞如何建网站费用,盐城滨海建设局网站,荆门市网站建设,dw网页制作过程本专栏内容为#xff1a;八大排序汇总 通过本专栏的深入学习#xff0c;你可以了解并掌握八大排序以及相关的排序算法。 #x1f493;博主csdn个人主页#xff1a;小小unicorn ⏩专栏分类#xff1a;八大排序汇总 #x1f69a;代码仓库#xff1a;小小unicorn的代码仓库… 本专栏内容为八大排序汇总 通过本专栏的深入学习你可以了解并掌握八大排序以及相关的排序算法。 博主csdn个人主页小小unicorn ⏩专栏分类八大排序汇总 代码仓库小小unicorn的代码仓库 关注我带你学习编程知识 无论你学习哪种编程语言在学到循环和数组时通常都会介绍一种排序算法来作为例子而这个算法一般就是冒泡排序。并不是它的名称很好听而是说这个算法的思路最简单最容易理解。因此哪怕大家可能都已经学过冒泡排序了我们还是从这个算法开始我们的排序之旅。 冒泡排序 最简单排序的实现冒泡排序算法冒泡排序优化冒泡排序复杂度分析 最简单排序的实现
冒泡排序(Bubble Sort)是一种交换排序它的基本思想是两两比较相邻记录的关键字如果反序则交换直到没有反序的记录为止。
冒泡的实现在细节上可以有很多种变化我们将分别就3种不同的冒泡实现代码来讲解冒泡排序的思想。这里我们就先来看看比较容易理解的一段。
注意排序用到的结构与函数在第一部分排序的基本概念与分类。我们已经实现。详情请点击八大排序一--------排序的基本概念与分类 //对顺序表L作交换排序冒泡排序初级版本
void BubbleSort0(SqList* L)
{int i 0, j 0;for (i 1; i L-length; i){for (j i1; j L-length; j){if (L -r[i] L-r[j]){swap(L, i, j); //交换L-r[i]与r-[j]}}}
}
这段代码严格意义上说不算是标准的冒泡排序算法因为它不满足“两两比较相邻记录”的冒泡排序思想它更应该是最简单的交换排序而已。它的思路就是让每一个关键字都和它后面的每一个关键字比较如果大则交换这样第一位置的关键字在一次循环后一定变成最小值。
如下图所示假设我们待排序的关键字序列是{9,1,5,8,3,7,4,6,2} 当i1时9与1交换后在第一位置的1与后面的关键字比较都小因此它就是最小值。
当i2时第二位置先后由9换成5换成3换成2完成了第二小的数字交换。后面的数字变换类似这里不再介绍。
这应该算是最容易写出的排序代码了不过这个简单易懂的代码却是有缺陷的。观察后发现在排序好1和2的位置后对其余关键字的排序没有什么帮助(数字3反而还被换到了最后一位)。也就是说这个算法的效率是非常低的。
冒泡排序算法
我们来看看正宗的冒泡算法有没有什么改进的地方。 //对顺序表L作冒泡排序
void BubbleSort(SqList* L)
{int i 0, j 0;for (i 1; i L-length; i){for (j L-length-1; j i; j--) //j从后往前循环{if (L-r[i] L-r[j1]) //若前者大于后者{swap(L, i, j1); //交换L-r[i]与r-[j1]的值}}}
}
依然假设我们待排序的关键字序列是{9,1,5,8,3,7,4,6,2}
当i1时变量j由8反向循环到1逐个比较将较小值交换到前面直到最后找到最小值放置在了第1的位置。
如下图所示当i1,j8时我们发现62因此交换了它们的位置j7时42所以交换……直到2时因为12所以不交换。j1时91交换最终得到最小值1放置第1的位置。
事实上在不断循环的过程中除了将关键字1放到第1的位置我们还将关键字2从第9位置提到了第3的位置显然这一算法比前面的要有进步在上十万条数据的排序过程中这种差异会体现出来。图中较小的数字如同气泡般慢慢浮到上面因此就将此算法命名为冒泡算法。 后面的数字变换就很简单这里就不在叙述了。
冒泡排序优化
这样的冒泡程序是否还可以优化呢答案是肯定的。试想一下如果我们待排序的序列是{2,1,3,4,5,6,7,8,9}也就是说除了第1和第2的关键字需要交换外别的都已经是正常的顺序。
当i1时交换了2和1此时序列已经有序但是算法仍然不依不饶地将i29以及每个循环中的循环都执行了一遍尽管并没有交换数据但是之后的大量比较还是大大地多余了如下图所示。 当i2时我们已经对9与88与7…3与2作了比较没有任何数据交换这就说明此序列已经有序不需要再继续后面的循环判断工作了。为了实现这个想法我们需要改进一下代码增加一个标记变量flag来实现这一算法的改进。
//对顺序表L作冒泡排序改进版本
void BubbleSort(SqList* L)
{int i 0, j 0;status flag 1; //用flag进行标记for (i 1; i L-length flag; i) //若flag为1则有效数据交换{flag 0;for (j L-length-1; j i; j--) //j从后往前循环{if (L-r[i] L-r[j1]) //若前者大于后者{swap(L, i, j1); //交换L-r[i]与r-[j1]的值flag 1; //如果有数据交换则flag为1}}}
}代码改动的关键就是在变量的for循环中增加了对flag是否为1的判断。
经过这样的改进冒泡排序在性能上就有了一些提升可以避免已经有序的情况下的无意义循环判断。
冒泡排序复杂度分析
分析一下它的时间复杂度。
当最好的情况也就是要排序的表本身就是有序的那么我们比较次数根据最后改进的代码可以推断出就是n-1次的比较没有数据交换时间复杂度为O(n)。
当最坏的情况即待排序表是逆序的情况此时需要比较之 ∑ i 2 n ( i − 1 ) 1 2 3 … ( n − 1 ) n ( n − 1 ) / 2 \sum_{i2}^n (i-1)123…(n-1)n(n-1)/2 ∑i2n(i−1)123…(n−1)n(n−1)/2次并作等数量级的记录移动。因此总的时间复杂度为O(n2)。
