网站源码平台,在意派建设好网站后,wordpress小说网站模板下载地址,wordpress 索引插件冒泡排序#xff08;Bubble Sort#xff09;是最简单和最通用的排序方法#xff0c;其基本思想是#xff1a;在待排序的一组数中#xff0c;将相邻的两个数进行比较#xff0c;若前面的数比后面的数大就交换两数#xff0c;否则不交换#xff1b;如此下去#xff0c;直… 冒泡排序Bubble Sort是最简单和最通用的排序方法其基本思想是在待排序的一组数中将相邻的两个数进行比较若前面的数比后面的数大就交换两数否则不交换如此下去直至最终完成排序 。由此可得在排序过程中大的数据往下沉小的数据往上浮就像气泡一样于是将这种排序算法形象地称为冒泡排序 冒泡排序_百度百科 (baidu.com) 冒泡排序适用于小规模数据和部分排序数据的情况同时也常用于教学和理解排序算法的基本原理。
1. 算法步骤
比较相邻的元素。如果第一个比第二个大就交换他们两个。
对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元素会是最大的数。
之后针对所有的元素重复以上的步骤除了最后一个。
持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。
2. 动图演示 3.代码实现
#include stdio.h
void bubble_sort(int arr[], int len) {int i, j, temp;for (i 0; i len - 1; i)for (j 0; j len - 1 - i; j)if (arr[j] arr[j 1]) {temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}
}
int main() {int arr[] { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };int len sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, len);int i;for (i 0; i len; i)printf(%d , arr[i]);return 0;
} 4.函数封装
升序排列
void Bubble_Sort(uint16_t *Data,uint8_t Count)
{uint8_t i0,j0;uint16_t temp;for(i0;iCount-1;i){for(j0;jCount-1-i;j){if(Data[j]Data[j1]){tempData[j];Data[j]Data[j1];Data[j1]temp;}}}
}
降序排列
void Bubble_Sort(uint16_t *Data,uint8_t Count)
{uint8_t i0,j0;uint16_t temp;for(i0;iCount-1;i){for(j0;jCount-1-i;j){if(Data[j]Data[j1])//改变符号{tempData[j];Data[j]Data[j1];Data[j1]temp;}}}
} 5.函数讲解
核心代码如下 for(i0;iCount-1;i){for(j0;jCount-1-i;j){if(Data[j]Data[j1]){tempData[j];Data[j]Data[j1];Data[j1]temp;}}} 外循环讲解
外循环其实就是已经排好的数据的个数累加过程. i0:一个也没有被确定所以从0开始累加。 icount-1:冒泡排序有Count个数要从小到大排内循环结束一次就有一个数被确定,只要其中Count-1个较高位数的位置排好了那么最小的数就排好了比如三个大小不同的数只要确定2个数哪个最大哪个第二大那么第三个数就是最小。所以知道Count-1个较高位数的位置被确定循环就结束。 i已知冒泡排序高位向后排每一轮比较内循环都确定了一个最高位这个最高位如果放在没有被排序的数里是最高位这个最高位在已经确定位置的数里是最低位。 内循环讲解 j0:从数组的第0个数开始遍历数组 jcount-i-1:Count个数据,需要比较Count-1次而i是整个排序中被确定的数一开始为0每一次内结束循环结束就确定一个就少比较i个数所以在确定i个数的位置时内循环需要比较的数据有Count-i个数据要比较的次数为Count-1-i次 j:相邻的相比较所以加一 if条件语句为了升序比较第一个与第二个第二个与第三个…
if的花括号内就是C语言常用的交换位置的三个语句。
7.冒泡排序flag优化算法
冒泡排序还有一种优化算法就是立一个 flag当在一次数组遍历中元素没有发生交换则证明该数组已经有序。但这种改进对于提升性能来说并没有什么太大作用。
解决方式可以通过一个标志位来打断循环
void Bubble_Sort(uint16_t *Data,uint8_t Count)
{uint8_t i0,j0,Flag0;uint16_t temp;for(i0;iCount-1;i){for(j0;jCount-1-i;j){if(Data[j]Data[j1]){tempData[j];Data[j]Data[j1];Data[j1]temp;Flag1;}}if(Flag0){break;}elseFlag0;}
}
8.时间复杂度分析
冒泡排序的时间复杂度分析是衡量算法效率的重要指标。我们来分析最好情况、最坏情况和平均情况下的时间复杂度
最好情况如果待排序的数组已经有序即元素无需交换位置那么只需要进行一次遍历时间复杂度为 O(n)。最坏情况如果待排序的数组是逆序的即每次比较都需要交换位置那么需要进行 n-1 轮遍历每轮遍历需要比较 n-i-1 次时间复杂度为 O(n^2)。平均情况在平均情况下需要进行 n/2 轮遍历每轮遍历需要比较 n-i-1 次时间复杂度也为 O(n^2)。 冒泡排序的时间复杂度为 O(n^2)其中 n 表示待排序数组的长度。这说明随着数据规模的增大冒泡排序的执行时间呈二次增长效率较低。
9.性能分析
优点
简单易懂冒泡排序是一种非常简单的排序算法它的思想容易理解代码实现也相对容易。稳定排序冒泡排序是一种稳定的排序算法即在排序过程中相同大小的元素不会相互交换位置。空间复杂度低冒泡排序的空间复杂度为 O(1)即它只需要使用固定的额外空间来存储交换的元素而不依赖于输入数组的大小。
缺点
时间复杂度高冒泡排序的时间复杂度为 O(n^2)在处理大规模数据时效率较低。不适合大规模数据由于冒泡排序需要进行多次比较和交换操作对于大规模数据集其性能可能会较差。排序不彻底在最坏情况下冒泡排序可能无法将数组完全排序例如当数组已经基本有序时。
10.总结
冒泡排序是最基础的排序算法之一通过相邻元素的比较和交换逐渐将最大或最小的元素冒泡到数列的一端。尽管冒泡排序的效率相对较低但它的实现简单易懂是理解排序算法的入门之选。
然而在实际应用中对于大规模数据集我们更倾向于选择时间复杂度较低的排序算法如快速排序、归并排序和堆排序等。这些算法能够在更短的时间内完成排序任务提高程序的执行效率。因此在实际开发中我们需要根据具体情况选择合适的排序算法。 参考博客
JS-Sorting-Algorithm/1.bubbleSort.md at master · hustcc/JS-Sorting-Algorithm · GitHub
【干货】深入剖析冒泡排序算法原理、步骤与复杂度分析_冒泡算法-CSDN博客
