动静图结合——冒泡排序

动静图结合——冒泡排序

每博一文案

世上不是所有人，都可以掏心掏肺，苦诉衷肠。
路过的都是缘，擦肩而过的都是客，相识的人，无数交心的人，却
很少，真心在乎你过得好不好，关心你累不累的人，更是寥寥无几。
每次需要人陪，才发现，有的人，不能找，有的人，不该找，
一段路没人，陪你热闹同行，你要对独行的自己说，走过这段就好，
前方有更好的风景和更好的人等着。
徐志摩曾说过，我懂你，像懂自己一样深刻，简简单单的一句话，
却触碰到了，我们心中的涟漪。
听过这样一句话，希望能遇见一个读懂自己的人，因为一辈子太长了，
我不想将就，总有一个人会心甘情愿地对你好，会不远万里的来见你，
知你冷暖，懂你悲欢，它会熬夜陪你，下雨接你，你会卸下所有的防备，
接受这个世界，给予你的温柔。所以，不要着急，因为最好的总是压箱底的。
                                    ——————   一禅心灵庙语
1
2
3
4
5
6
7
8
9
10
11
12
13

---

---

冒泡排序

冒泡排序 的基本思想：通过对待排序列 从前向后 (从下标较小的元素开始)，依次比较相邻的元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的泡泡一样逐渐向上冒出。

优化点: 因为排序过程中，每个元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明该序列已经有序了，不用在排序了。因此要在排序过程中设置一个标记判断元素是否进行过交换。从而减少不必要的比较。

动图

静态图演示，升序

首先我们给定一个无序的数组，将其升序排序

---

第一趟排序： 从 下标 0 数值 3 开始，向后走

 3 和相邻的 9 比较 3 小,不用交换
1

---

继续走，下标 1 数值 9 与相邻的下标 2 ，比较判断

9 比 -1 大，交换，把 9 放到后面
1

---

继续走，下标2 数值 9 与相邻的下标 3 的数值，比较判断

9 比 10 小，不用交换
1

---

再继续走，下标为 3 的数值 10 与相邻的下标 4 的数值，比较判断

10 比 20 小 不用交换
1

---

到达了数组 下标 4 的位置，是数组最后一个下标位置，不可以再向后访问了，不然就是越界了，第一趟的冒泡完成了，我们这一趟中最大的数值 20排序好了，放到了最后面

---

第 2 趟冒泡排序 ： 从第一趟，排序好的结果，从下标 0 开始，比较判断，注意：这里我们需要减少一趟排序，因为，第一趟排序，我们已经排序好一个数值了，只需要将剩下没有排序好的数值排序好，就可以了

---

同样我们从 下标 0 开始 比较相邻的下标 1 的数值

 3 比 -1 大，需要交换
1

---

继续走，下标 1与相邻的下标 2 的数值，比较

 3 比 9 小 不用交换
1

---

继续走下标 2 与相邻的下标 3 的数值，比较

9 比 10 小，不要交换，因为 20 是已经排序好了的，不用，比较了，停止
1

第 2 趟 排序好 了，又将一个数值排序好了

---

第三趟排序 ： 发现一次都没有，发生交换，说明已经是有序的了。不用再排序了

---

---

---

冒泡排序小结:

1. 共进行数组大小 -1 次 的循环
2. 每一趟排序的次数在逐渐的减少的，因为每一趟下来都会将一个数值排序好，而排序好的数值就不要动了
3. 如果发现在某一趟排序中，没有发生一次交换 ，则说明已经有序了，可以提前结束冒泡排序。
   如上图那样，在第 2 趟排序完 ，就已经有序了 ，在 第 3 趟 的时候走完了，都没有发现交换，就可以提前结束排序了。
4. 注意 ： 不要发生，数组越界的情况，导致报错。

---

冒泡排序：升序

升序，相邻下标数值，比较，将大的数值，放到后面去，把比较判断改为 >

// 打印
void playPrint(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}

	printf("\n");
}



// 交换数值
void swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}



// 冒泡排序,升序
void bubbleSortAsc(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		int exchange = 0;     // 标记是否进行了交换

		for (int j = 1; j < n - i; j++)    // n-i 排序的趟数是逐渐减少的,每一趟都可以排序好一个数值
		{
			if (arr[j - 1] > arr[j])    // 前后相邻下标比较
			{
                exchange = 1;     // 标记发生了交换
                
				swap(&arr[j - 1], &arr[j]);   // 数值交换
			}
		}

		if (0 == exchange)     // 如果一趟下来,没有发生交换就说明,已经有序了,可以提前结束排序了
		{
			break;
		}
	}
}
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

---

冒泡排序：降序

降序，相邻下标元素数值，比较，将小的数值，放到后面，把 比较判断的 改为 <

// 冒泡排序,降序
void bubbleSortDesc(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		int exchange = 0;    // 标识是否交换了

		for (int j = 1; j < n - i; j++)
		{

			if (arr[j - 1] < arr[j])  // 相邻下标比较判断
			{
                exchange = 1;    // 标记发生了交换
                
				swap(&arr[j - 1], &arr[j]);  // 交换
			}
		}

		if (0 == exchange)   // 判断一趟下来,是否发生交换
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

另外一种方式的，冒泡排序

我们以，升序为例，请看如下代码

// 冒泡排序的另一种方式
void bubbleSort(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		int exchange = 0;

		for (int j = 0; j < n - i - 1; j++) // 不同点 n - i -1;
		{      

			if (arr[j] > arr[j + 1])   // j 和 j+1 的相邻比较
			{
				exchange = 1;

				swap(&arr[j], &arr[j + 1]);
			}
		}

		if (0 == exchange)
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

不同点 和 注意事项

上述代码内循环，判断条件是: for (int j = 0; j < n - i - 1; j++), 是 j < n - i - 1,

多了一个 -1 ，是因为判断相邻下标位置是 ：if (arr[j] > arr[j + 1]), 当 i = 0 时，没有 -1 的话，

判断条件就变成了 j < n - i = j < n 了，如果再出现 arr[j] 为最后一个下标时，那么 arr[j+1] 就是越界了，超过数组的大小访问了。报错了，这是使用这种方式的，注意事项；

---

冒泡排序，完整实现代码

下面是冒泡排序的完整实现代码，大家可以直接粘贴复制就可以直接运行的

#define  _CRT_SECURE_NO_WARNINGS  1

#include


// 打印
void playPrint(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}

	printf("\n");
}



// 交换数值
void swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}



// 冒泡排序,升序
void bubbleSortAsc(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		int exchange = 0;     // 标记是否进行了交换

		for (int j = 1; j < n - i; j++)    // n-i 排序的趟数是逐渐减少的,每一趟都可以排序好一个数值
		{

			if (arr[j - 1] > arr[j])    // 前后相邻下标比较
			{
				exchange = 1;     // 标记发生了交换

				swap(&arr[j - 1], &arr[j]);   // 数值交换
			}
		}

		if (0 == exchange)     // 如果一趟下来,没有发生交换就说明,已经有序了,可以提前结束排序了
		{
			break;
		}
	}
}



// 冒泡排序,降序
void bubbleSortDesc(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		int exchange = 0;

		for (int j = 1; j < n - i; j++)
		{

			if (arr[j - 1] < arr[j])
			{
				exchange = 1;

				swap(&arr[j - 1], &arr[j]);
			}
		}

		if (0 == exchange)
		{
			break;
		}
	}
}




// 冒泡排序的另一种方式
void bubbleSort(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		int exchange = 0;

		for (int j = 0; j < n - i - 1; j++) // 不同点 n - i -1;
		{      

			if (arr[j] > arr[j + 1])   // j 和 j+1 的相邻比较
			{
				exchange = 1;

				swap(&arr[j], &arr[j + 1]);
			}
		}

		if (0 == exchange)
		{
			break;
		}
	}
}




// 测试
void test()
{
	int arr[] = { 5,1,2,4,3,6,9,7,10,8 };
	bubbleSort(arr, sizeof(arr) / sizeof(int));   // 冒泡排序,另外一种方式
	//bubbleSortDesc(arr, sizeof(arr) / sizeof(int));  // 冒泡排序,降序
	//bubbleSortAsc(arr, sizeof(arr) / sizeof(int));   // 冒泡排序,升序
	playPrint(arr, sizeof(arr) / sizeof(int));         // 打印数组
	
	/*
	* sizeof(arr)/sizeof(int)  数组的大小
	* sizeof(arr)  数组所占的大小 单位字节
	* sizeof(int)  数组元素类型所占的大小，单位字节
	*/
}

int main()
{
	test();
	
	return 0;
}
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

---

最后:

限于自身水平，其中存在的错误，希望大家给予指教，韩信点兵——多多益善，谢谢大家，后会有期，江湖再见 ！！！

---