画图标网站,wordpress幻灯片源码,中国移动网上商城,100种迷你小手工成长路上不孤单#x1f60a;#x1f60a;#x1f60a;#x1f60a;#x1f60a;#x1f60a;
【#x1f60a;///计算机爱好者#x1f60a;///持续分享所学#x1f60a;///如有需要欢迎收藏转发///#x1f60a;】
今日分享关于C中常用的排序方法之——冒泡排序的相关… 成长路上不孤单
【///计算机爱好者///持续分享所学///如有需要欢迎收藏转发///】
今日分享关于C中常用的排序方法之——冒泡排序的相关内容 关于【C中常用的排序方法之——冒泡排序】 目录 一、 冒泡排序的定义二、冒泡排序的算法原理三、冒泡排序的算法示例四、冒泡排序的算法分析五、冒泡排序的特点六、冒泡排序的优点七、冒泡排序的缺点 冒泡排序Bubble Sort
一、冒泡排序的定义
冒泡排序的英文Bubble Sort是一种最基础的交换排序。 大家一定都喝过汽水汽水中常常有许多小小的气泡哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻所以小气泡可以一点一点向上浮动。而我们的冒泡排序之所以叫做冒泡排序正是因为这种排序算法的每一个元素都可以像小气泡一样根据自身大小一点一点向着数组的一侧移动。 二、冒泡排序的算法原理
假定序列中有n个数要进行从小到大的排序。若参与排序的数组元素共有n个则需要n-1轮排序。在第í轮排序中从左端开始相邻两数比较大小若反序则将两者交换位置直到比较第n1-i个数为止。第1个数与第2个数比较第2个数和第3个数比较一直到第n-i个数与第n1-i个数比较一共处理 n-i次。此时第n1-i个位置上的数已经有序后续就不需要参加以后的排序。
1第1轮冒泡排序先从第1个数和第2个数开始比较若第1个数大于第2个数则需要交换两者的位置否则保持不变。重复这一过程直到处理完本轮数列中最后两个数。
2第2轮冒泡排序与第1轮冒泡排序进行相同的排序使大的数交换到n-2的位置上。
3重复以上过程共需经过n-1轮冒泡排序后数据实现升序排序。
三、冒泡排序的算法示例
对于序列[26282411]采用非递减规则进行排序排序过程如下所示。 (1) 比较相邻的元素。如果第一个比第二个大就交换他们两个。
(2) 对每一对相邻元素做同样的工作从开始第一对到结尾的最后一对。在这一点最后的元素应该会是最大的数。
(3) 针对所有的元素重复以上的步骤除了最后一个。
(4) 持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。
四、冒泡排序的算法分析
1、时间复杂度
若文件的初始状态是正序的一趟扫描即可完成排序。所需的关键字比较次数 若初始文件是反序的需要进行n-1趟排序。每趟排序要进行n-i 次关键字的比较(1≤i≤n-1)且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下比较和移动次数均达到最大值 2、算法稳定性
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较交换也发生在这两个元素之间。所以如果两个元素相等是不会再交换的如果两个相等的元素没有相邻那么即使通过前面的两两交换把两个相邻起来这时候也不会交换所以相同元素的前后顺序并没有改变所以冒泡排序是一种稳定排序算法。
五、冒泡排序的特点
时间复杂度冒泡排序的时间复杂度为O(n^2)。在最坏的情况下即初始序列完全逆序需要进行n(n-1)/2次比较和3n(n-1)/2次移动时间复杂度为O(n^2)。在最好的情况下即初始序列已经有序时间复杂度为O(n)但这种情况较为罕见。
空间复杂度冒泡排序是一种就地排序算法不需要额外的存储空间因此空间复杂度为O(1)。
稳定性冒泡排序是一种稳定的排序算法即相同元素的相对位置不会改变。
适用场景由于冒泡排序的时间复杂度较高它适用于数据量较小的情况。对于大量数据的排序效率较低。
算法原理冒泡排序通过重复遍历待排序的数列比较两个相邻的元素如果它们的顺序错误就交换过来。遍历工作是重复进行的直到没有再需要交换的元素为止。
优化方法可以通过设置一个标志位来优化冒泡排序。如果在一次完整的遍历中没有发生交换说明数组已经有序可以直接结束排序过程。这种方法可以在某些情况下将时间复杂度降低到O(n)。
六、冒泡排序优点
1、 实现简单冒泡排序的算法逻辑非常简单容易理解和实现。它只需要通过重复遍历要排序的数列比较相邻元素的值并在必要时交换它们的位置。
2、代码简洁冒泡排序的代码非常简洁不需要复杂的操作和额外的存储空间。
3、原地排序冒泡排序是一种原地排序算法不需要额外的内存空间来存储排序结果。它直接在原始数组上进行元素的比较和交换操作。
4、稳定性冒泡排序是一种稳定的排序算法即相等元素的相对顺序在排序前后保持不变。只有当两个相邻元素进行交换时才会改变它们的相对顺序。
5、适用于小规模数据在数据规模较小的情况下冒泡排序的性能还是可以接受的。对于小规模的数据集冒泡排序可能比其他复杂的排序算法更快。
七、冒泡排序的缺点 1、时间复杂度高冒泡排序的时间复杂度为O(n^2)在数据量较大时效率较低尤其是当数据完全逆序时时间复杂度达到O(n^2)。 2、不适合大规模数据由于其较高的时间复杂度冒泡排序不适合处理大规模数据集。
