冒泡排序讲解
1、何为冒泡
形象来说就是大的上浮，小的下沉；或者小的上浮，大的下沉
冒泡排序的内在逻辑
假设有数组 int arr[5] = {12,23,1,55,34};
我们有规则：相邻的数两两比较，若arr[j] > arr[j+1]，则swap，反之则不改变
举例：
待排序数组：3，9， - 1，10，20
第一轮排序：
（1）3，9， - 1，10，20—-3跟9比较，不交换
（2）3， - 1，9，10，20—-9比 - 1大，所以9跟 - 1交换
（3）3， - 1，9，10，20—-9跟10比较，不交换
（4）3， - 1，9，10，20—-10跟20比较，不交换
第一轮过后，将20这个最大的元素固定到了最后的位置
第二轮排序：
因为20的位置已经固定，所以只对前4个进行排序即可：
（1） - 1，3，9，10，20—-3比 - 1大，进行交换
（2） - 1，3，9，10，20—-3跟9比较，不交换
（3） - 1，3，9，10，20—-9跟10比较，不交换
第二轮过后，将第二大的元素固定到了倒数第二个位置
第三轮排序：
10和20的位置已经确定，只需对前三个进行排序
（1） - 1，3，9，10，20—-3和 - 1比较，不交换
（2） - 1，3，9，10，20—-3和9比较，不交换
第三轮过后，将第三大的元素位置确定
第四轮排序：
只对前两个元素进行排序
（1） - 1，3，9，10，20—-3和 - 1比较，不交换
第四轮过后，将第四大的元素位置确定，此时总共5个元素，已经排序好4个，从而最后一个自然而然就是排好序的了
冒泡排序次数:n*(n-1)/2
算法时间复杂度O(n*n)
2、考点：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int main() {
int temp, arr[SIZE] = { 0 };
for (int m = 0; m < SIZE; m++) {
scanf("%d", &arr[m]);
}
for (int i = 0; i < SIZE - 1; i++) {
for (int j = 0;j < SIZE - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
for (int m = 0; m < SIZE; m++) {
printf("%d ", arr[m]);
}
return 0;
}
|
3、几种常见的冒泡写法
第一种写法 (输出为升序)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int main() {
int temp, arr[SIZE] = { 0 };
for (int m = 0; m < SIZE; m++) {
scanf("%d", &arr[m]);
}
for (int i = 0; i < SIZE - 1; i++) {
for (int j = 0;j < SIZE - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
for (int m = 0; m < SIZE; m++) {
printf("%d ", arr[m]);
}
return 0;
}
|
第二种写法(输出为降序）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int main() {
int temp, arr[SIZE] = { 0 };
for (int m = 0; m < SIZE; m++) {
scanf("%d", &arr[m]);
}
for (int i = 0; i < SIZE ; i++) {
for (int j = 0; j < SIZE - i ; j++) {
if (arr[j] < arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
for (int m = 0; m < SIZE; m++) {
printf("%d ", arr[m]);
}
return 0;
}
|
第三种写法(输出为降序）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int main() {
int temp, arr[SIZE] = { 0 };
for (int m = 0; m < SIZE; m++) {
scanf("%d", &arr[m]);
}
for (int i = 0; i < SIZE - 1; i++) {
for (int j = SIZE - 1; j > i; j--) {
if (arr[j] > arr[j - 1]) {
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
for (int m = 0; m < SIZE; m++) {
printf("%d ", arr[m]);
}
return 0;
}
|
第四种写法(输出为升序）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int main() {
int temp, arr[SIZE] = { 0 };
for (int m = 0; m < SIZE; m++) {
scanf("%d", &arr[m]);
}
for (int i = 0; i < SIZE - 1; i++) {
for (int j = SIZE - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
for (int m = 0; m < SIZE; m++) {
printf("%d ", arr[m]);
}
return 0;
}
|
冒泡排序的优化
我们在一些例子中其实可以看出从某一轮过后，数组已经是有序的了，但是按照算法步骤来走的话，即使已经排好序了，但仍是会进行后边的比较，知道全部比较完成
因此，我们可以对代码进行优化，如果发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序。
解决方式：可以通过一个标志位 >= flag 来进行判断
具体代码如下：
加入头文件<stdbool.h>
#include <stdbool.h>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| int main() {
int temp, arr[SIZE] = { 0 };
bool flag = false;
for (int m = 0; m < SIZE; m++) {
scanf("%d", &arr[m]);
}
for (int i = 0; i < SIZE - 1; i++) {
for (int j = 0;j < SIZE - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
flag = true;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
if (!flag) {
break;
}
else {
flag = false;
}
}
for (int m = 0; m < SIZE; m++) {
printf("%d ", arr[m]);
}
return 0;
}
|
wechat
alipay
