SYSTEM
冒泡排序
src/content/notes/system/冒泡排序.md 排序
冒泡排序
冒泡排序(Bubble Sort):两个数比较大小,较大的数下沉,较小的数冒起来
算法描述:每次从数组的第一个位置开始两两比较,把较大的元素与较小的元素进行层层交换,最终把当前最大的一个元素存入到数组当前的末尾
实现思路:
- 确定总共需要冒几轮:数组的长度-1
- 每轮两两比较几次
// 0 1位置比较,大的放后面,然后1 2位置比较,大的继续放后面,一轮循环最后一位是最大值
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {55, 22, 2, 5, 1, 3, 8, 5, 7, 4, 3, 99, 88};
int flag;//标记本趟排序是否发生了交换
//比较i和i+1,不需要再比最后一个位置
for (int i = 0; i < arr.length - 1; i++) {
flag = 0;
//最后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;
flag = 1;//发生了交换
}
}
//没有发生交换,证明已经有序,不需要继续排序,节省时间
if(flag == 0) {
break;
}
}
System.out.println(Arrays.toString(arr));
}
}
冒泡排序时间复杂度:最坏情况
- 元素比较的次数为:
(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2 - 元素交换的次数为:
(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2 - 总执行次数为:
(N^2/2-N/2)+(N^2/2-N/2)=N^2-N
按照大 O 推导法则,保留函数中的最高阶项那么最终冒泡排序的时间复杂度为 O(N^2)