中心思想
通过无序区中的相邻的记录的比较和位置的交换,使记录较小的的数有如气泡一样逐渐往上“漂浮”直至“浮出水面”。
代码实现
public int[] sort(int[] sourceArray) {
// 1.遍历多少次(i)[1,sourceArray.length)
for (int i = 1; i < sourceArray.length; i++) {
// 2.每次遍历多少个[0,sourceArray.length - i)
for (int j = 0; j < sourceArray.length - i; j++) {
// 3.判断是否需要交换位置
if (sourceArray[j] > sourceArray[j + 1]) {
int temp = sourceArray[j];
sourceArray[j] = sourceArray[j + 1];
sourceArray[j + 1] = temp;
}
}
}
return sourceArray;
}
时间复杂度
- 最好情况: 正序有序,则只需要比较 n 次。故 为 O(n)
- 最坏情况: 逆序有序,则需要比较(n-1)+(n-2)+ ….+ 1次。故为O(N*N)
稳定性
排序过程中只交换相邻的两个元素的位置。因此,当两个数相等时,是没必要交换两个数的位置。他们的相对位置并没有改变。 冒泡排序 算法是稳定的!