冒泡排序

原理:每次比较相邻的两个元素,然后在满足一定条件情况交换相邻两个元素

53142

一趟冒泡(当前区间内,最大的一定会排在最后)

第一趟冒泡

ii+1

35142

31542

31452

31425

第二趟冒泡

31425

13425

13245

第三趟冒泡

13245

12345

第四趟冒泡

ii+1

12345

冒泡排序

时间复杂度(取决于运算的次数):O(n^2)

空间复杂度(取决于额外开辟的空间):O(1)

稳定性:稳定

void bubbleSort(inta[], intn) {//外层j控制的每次需要冒泡的长度(每趟过后都会排好一个,长度--)for (intj = n - 1; j >= 1; j--) {//优化:当某一趟冒泡的时候已经有序,提前跳出循环boolflag = true;//假设当前序列已经有序了//内层i遍历当前区间,进行冒泡操作(当前区间的最后一个元素一定会排好)for (inti = 0; i  a[i + 1]) {//冒泡操作(如果前者大于后者)swap(a[i], a[i + 1]);//交换两个元素flag = false;//证明此时序列可能还是无序的}}if (flag == true) break;//证明此时序列是真的有序}}