冒泡排序

原理

冒泡排序算法的原理如下：

比较相邻的元素,如果第一个比第二个大,就交换他们两个.对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数.针对所有的元素重复以上的步骤,除了最后一个.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较.

示例

int[] arr={7,3,4,2,1,6}; 7 3 4 2 1 6 3 4 2 1 6 [7] 3 2 1 4 [6] 2 1 3 [4] 1 2 [3] 1 [2] i表示当前的趟数 j表示当前趟比较的次数; 趟数:arr.length-1; 每次比较的次数:j=arr.length-1-i; arr[j]和arr[j+1]相邻的两个数比较; int temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp;

代码

public static void main(String[] args){ int[] arr={7,3,4,2,1,6}; for(int i = 0;i < arr.length-1; i++){ for(int j = 0;j < arr.length - 1 - i;j++){ if(arr[j]>arr[j+1]){ int temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } System.out.println(Arrays.toString(arr)); }

冒泡排序是原地排序算法吗?

冒泡的过程只涉及相邻数据的交换操作,只需要常量级的临时空间,所以它的空间复杂度为 O(1),是一个原地排序算法.

冒泡排序的稳定的排序算法吗?

在冒泡排序中,只有交换才可以改变两个元素的前后顺序.为了保证冒泡排序算法的稳定性,当有相邻的 两个元素大小相等的时候,我们不做交换,相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法.

冒泡排序的时间复杂度是多少?

O(n²) 最好情况下,要排序的数据已经是有序的了,我们只需要进行一次冒泡操作,就可以结束了,最好情况时间复杂度是O(n).最坏的情况是,要排序的数据刚好是倒序排列的,我们需要进行n次冒泡操作, 所以最坏情况时间复杂度为O(n²).