冒泡排序算法(思路分析) [数据结构][Java]

冒泡排序算法(思路分析)

基本介绍:

冒泡排序(Bubble Sorting)的基本思想是: 通过对 “待排序序列” 从前向后一次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐移向数组的后部 — > 就像是水底下的气泡一样逐渐上冒

冒泡排序是可以进行优化的:

因为在排序的过程中,各个元素不断的接近自己的位置,如果一趟比较下来元素的值没有进行交换,就说明序列是有序的,因此要在排序的过程中设置一个boolean类型的标志flag,判断在一趟排序中元素是否进行过交换,从而减少不必要的比较

• 关于冒泡排序的优化我们可以在完善了冒泡排序之后进行
  • 我们将冒泡排序的优化放到了后续的另一篇文章中进行讲解,这里就不进行细说了

冒泡排序的过程:(图解)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VJnumeVp-1660872849282)(E:\非凡英才\数据结构(java)]\数据结构图解\冒泡排序过程图解.png)

在冒泡排序中的第几趟就会排好倒数第几个位置的元素(这里是以升序排序为例 : 如果是降序, 那么每次排序好的也肯定是最后一个元素, 但是肯定是每次都排好待排序元素中的最小的元素)

• 就比如我们如果是执行第一趟冒泡排序,那么当我们执行完这一趟冒泡排序之后最后一个位置的元素就确定了
  • 也就是我们的冒泡排序就是一次一次都找最大的,如果你大那么你就往后面走,第一趟排序就是找最大的,第二趟冒泡排序就是找第二大的,那么为什么我们的第二趟冒泡排序就是找第二大的?
    • 因为我们第一趟冒泡排序已经找出了最大的元素了,这个时候我们执行第二趟冒泡排序的时候就不需要排最后一个位置上的元素了,这个时候我们就是在除了最大的元素中找新的最大的元素 —> 其实也就是找倒数第二大的元素

冒泡排序的思路分析:

冒泡排序就是依次两个相邻元素之间进行比较大小(就比如第一个元素和第二个元素比较),如果小的元素在前面,大的元素在后面,那么就不需要交换位置,就进行下一个位置的比较(第一个和第二个比较完了,这个时候就是比较第二个和第三个),然后开始重复,如果是前面的元素比后面的元素大,那么就交换两个位置上的数值,然后一直向下比较,知道比较完倒数第二个元素和倒数第一个元素,那么我们的第一趟才算是比较完毕了,而第一趟比较完毕之后我们的最后一个元素的值已经是数组中的最大值了,那么为什么这个时候最后一个元素的值已经是最大值了?

• 因为第一趟排序中我们一直都是相邻的元素进行比较,让大的值往后移,知道比较完第一趟的最后一次,那么这个时候最大的元素自然就移动到了数组中的最后一个位置上

  • 那么当第一趟排序过后数组中最后一个位置的值已经是确定的了,那么接下来的第二趟排序的时候我们完全就不用考虑对最后一个位置的元素的比较了 --> 所以这就是为什么我们说冒泡排序一趟比一趟执行的次数少的原因

交换两个位置上的数值的时候要注意: 我们要交换两个位置上的数值,那么我们要使用到一个辅助变量

• 那么为什么要使用一个辅助变量?
  • 因为如果没有这个辅助变量的时候,那我们要交换两个位置的元素值,那么肯定是要将一个位置的值赋给另一个位置,再将另一个位置的值赋给这个位置,但是是错误的 —> 因为我们一旦将一个位置的值赋给另一个位置之后,那么另一个位置的数值就已经被替代了,这个时候另一个位置的数据值就 " 失真 "了
    • 失真: 就是另一个位置的值已经不是原来的值了
      • 而我们为了防止失真的发生,我们可以先将要失真的主句提前存放到一个临时变量中,这样即使我们的这个位置的数据值失真了,但是我们已经将失真的值提前保存到了一个临时变量中,我们只要进这个临时变量的值赋给另一个位置即可 —> 那么就完成了两个位置元素的交换

冒泡排序规则的小结:

1. 冒泡排序一共要执行数组长度减一次的大循环
   • 也即是要执行数组长度减一趟
2. 每一趟排序中比较的次数逐渐减小(第一次要比较数组长度 - 1次, 最后一次比较1次)
3. 如果我们发现在某趟排序中没有发生过一次变换,我们就可以提前结束冒泡排序,因为这个时候已经是排序完成了
   • 这样的操作其实其实就是对冒泡排序的优化

补充:

对于冒泡排序中每一趟执行的次数的问题,我们可以将数组中没有排序的元素都认为是一堵墙,我们的冒泡排序就是相邻的两堵墙要进行一次比较,我们可以认为响铃的两个元素之间进行一次比较就是相邻的两堵墙之间有一个空隙,那么n堵墙之间就有n-1个空隙,所以我们就可以类比出我们如果数组中有n个元素待排序,这个时候就相当于有n堵墙,这个时候就要比较n-1次

• 而我们最开始的时候肯定是由数组中的n个元素都没有排序,这个时候第一趟我们肯定是要执行n-1次,当我们执行了第一趟之后我们的数组中最后一个位置的元素就是最大的了,那么第二趟我们排序的时候数组中就只有n-1个元素没有排序,那么我们在第二趟中就要执行n-1-1次
  • 而通过这种方式我们也可以推算出我们的冒泡排序只执行n-1趟,因为我们执行n-1趟之后数组中n-1个元素就是有序的了,这个时候如果我们执行第n趟,那么在第n趟中我们只有一个元素是没有排序的,所以我们在第n次的排序中我们要执行1-1次,也就是执行0次,那么执行0次就相当于没有执行

冒泡排序中:

排序的趟数 = 第一趟中比较的次数 = 数组长度 - 1;

最后一趟排序的次数 = 1;

在我们的排序算法中
①外层循环执行的次数就是对应的排序算法要执行的趟数
②内层循环执行的次数就是对应的每趟排序要执行的次数

• 如果循环是for循环,那么就是执行一个"固定次数"
  • 这里的固定次数并不是指次数就是一个常数,而是指这个固定次数可以使用含有变量的代数式推算出来
    • 这个固定次数会根据待排序数组的长度的确定而确定
• 如果是while循环,那么就是执行不固定的的次数了
  • 如果是while循环,那么我们无法使用一个含有变量的表达式推算出while循环的执行次数
    • while循环当我们知道了数组长度之后也不能推算出执行了多少次,要根据具体的数组中的元素来确定