记得以前在大学里学习c语言的时候,刚开始是很吃力的.
入门级别的算法中有个叫冒泡排序法,也有称为气泡排序法.那时候刚接触它就对它的名字特别感兴趣,因为觉得很有意思.好了,废话不多说了,我们先一起简单回忆下这个冒泡排序法.
一.打印行和列一般是这样的一个简单代码,输出4行4列*:
|
1
2
3
4
5
6
|
for(int i = 1,i < 5,i++){
for(int j = 1,j < 5,j++){
printf("*");
}
printf("n\");
}
|
二.打印"上三角":
|
1
2
3
4
5
6
|
for(int i = 1,i < 5,i++){
for(int j = 1,j < i,j++){
printf("*");
}
printf("n\");
}
|
三.打印"下三角":
|
1
2
3
4
5
6
|
for(int i = 1,i < 5,i++){
for(int j = i,j < 5,j++){
printf("*");
}
printf("n\");
}
|
四.看官莫急,关键的地方等会就来了.冒泡排序其实就是一个"下三角"打印原理,因为在一个数组中排序每次都是从第一个元素开始和后面的元素比一轮,确定一个最值,最值就"沉"到最后一个了,每轮比较都会少一个数,所以冒泡排序原理就要用到打印"下三角原理了":
|
1
2
3
4
5
6
7
8
9
10
|
for (int i = 0; i < 4; i++) {
for (int j = i; j < 4; j++) {
if (nums[j] < nums[j+1]) {
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
|
细心的朋友应该会发现,这样排序一个数组后结果并不会预期的结果,可是我明明用的是"打印下三角"啊!记得当时老师给我们这样一个作业,让大家回去想想,提示用"下三角"原理打印,当时感觉好坑爹啊!(所以对这个冒泡排序法印象到现在还印象挺深的)
五.是的,这个是有一些小细节的,我当时琢磨了好一阵,后来终于发现了问题了,是因为下一轮每次比较都要从最前面的数开始与后面的数比较,如果改变初始化的值,第一个数只能与第2个数比较一次后就不会参与下一轮的比较了.所以我们应该把这个换一种形式
|
1
2
3
4
5
6
7
8
9
10
|
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4-i; j++) {
if (nums[j] < nums[j+1]) {
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
|
六.哈哈,原理是不错的,换了一种形式后就输出没问题了.
七.补充一点,一般都回把4替换为一个变量,比如length,或者使用宏定义的方法,个人感觉宏定义更好点. 当使用length的时候,要把length-1,这样有一个好处,就是防止越界问题,而且排序比大小的时候最后一个剩下的本来也不用去比较.所以length-1是没问题的.