问题描述:冒泡排序法的名字由来,排序步骤是什么,最坏情况下的排序次数如何计算得来的呢?
问题解答:
冒泡排序法的名字来源于排序过程中较大的元素会像气泡一样逐渐“冒”到序列的顶端,而较小的元素则会逐渐沉到序列的底部。
排序步骤如下:
- 从序列的起始位置开始,依次比较相邻的两个元素。
- 如果前一个元素大于后一个元素,则交换这两个元素的位置。
- 继续比较下一对相邻元素,直到到达序列的末尾。
- 重复以上步骤,直到整个序列都是有序的。
在最坏情况下,也就是待排序序列是逆序的情况下,每次内循环都要将当前最大的元素交换到最右侧。对于一个长度为 n 的序列,第一次遍历需要 n−1 次比较和交换,第二次遍历需要 n−2 次比较和交换,以此类推,直到最后一次遍历只需要一次比较。因此,总的比较和交换次数为:
最差的情况下第一个数比较了n-1次,接下来,重复操作,总共进行了n-1次比大小。形成了等差数列,首项是(n-1),末项是1,总共有n-1项,利用公式便求出来了。