🔥码云GVP开源项目 12k star Uniapp+ElementUI 功能强大 支持多语言、二开方便! 广告
### **冒泡排序算法思想** 两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位。 > 依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。重复第一趟步骤,直至全部排序完成。 > > 第一趟比较完成后,最后一个数一定是数组中最大的一个数,所以第二趟比较的时候最后一个数不参与比较; > > 第二趟比较完成后,倒数第二个数也一定是数组中第二大的数,所以第三趟比较的时候最后两个数不参与比较; > > 依次类推,每一趟比较次数-1; > > …… 冒泡排序算法的运作过程:(从小到大排序) 设数组a\[0..n-1\]长度为n, * 1.比较相邻的前后二个数据,如果前面数据大于后面的数据,就将二个数据交换。 * 2.这样对数组的第0个数据到n-1个数据进行一次遍历后,最大的一个数据就“沉”到数组第n-1个位置。 * 3.n=n-1,如果n不为0就重复前面二步,否则排序完成。 * * * 例子为从小到大排序,原始待排序数组| 7 | 2 | 4 | 1 | 5 | 第一趟排序(外循环) 第一次两两比较7 > 2交换(内循环) 交换前状态| 7 | 2 | 4 | 1 | 5 | 交换后状态| 2 | 7 | 4 | 1 | 5 | 第二次两两比较,7 > 4交换 交换前状态| 2 | 7 | 4 | 1 | 5 | 交换后状态| 2 | 4 | 7 | 1 | 5 | 第三次两两比较,7 > 1交换 交换前状态| 2 | 4 | 7 | 1 | 5 | 交换后状态| 2 | 4 | 1 | 7 | 5 | 第四次两两比较,7 > 5交换 交换前状态| 2 | 4 | 1 | 7 | 5 | 交换后状态| 2 | 4 | 1 | 5 | 7 | 第二趟排序(外循环) 第一次两两比较2 < 4不交换 交换前状态| 2 | 4 | 1 | 5 | 7 | 交换后状态| 2 | 4 | 1 | 5 | 7 | 第二次两两比较,4 > 1交换 交换前状态| 2 | 4 | 1 | 5 | 7 | 交换后状态| 2 | 1 | 4 | 5 | 7 | 第三趟排序(外循环) 第一次两两比较2 > 1交换 交换后状态| 2 | 1 | 4 | 5 | 7 | 交换后状态| 1 | 2 | 4 | 5 | 7 | 第二次两两比较,2 < 4不交换 交换后状态| 1 | 2 | 4 | 5 | 7 | 交换后状态| 1 | 2 | 4 | 5 | 7 | 排序完毕,输出最终结果1 2 4 5 7 * * * 冒泡排序时间复杂度,最好情况:数组已有序O(n);最坏情况:数组反序O(n^2),平均时间复杂度:O(n^2)。空间复杂度,冒泡排序是原地排序,空间复杂度为O(1)。冒泡排序算法是稳定的排序算法。 (1)时间复杂度 冒泡排序算法的最坏情况、最优情况、平均情况下的时间复杂度都是O(n^2) (2)空间复杂度 空间复杂度就是在交换元素时那个临时变量所占的内存空间;最优的空间复杂度就是开始元素顺序已经排好了,则空间复杂度为:O(1);最差的空间复杂度就是开始元素逆序排序了,则空间复杂度为:O(n);平均的空间复杂度为:O(1);