冒泡排序的基本思想
每次比较两个相邻的元素，如果它们的顺序错误，就把它们的交换过来。
举例分析
对 12 35 99 18 76 按从大到小排序，排序方式：冒泡排序
原始数据
12 35 99 18 76
第一趟—12 35 99 18 76
35 12 99 18 76 // 12 与 35比较， 交换
35 99 12 18 76 // 12 与 99比较， 交换
35 99 18 12 76 // 12 与 18比较， 交换
35 99 18 76 12 // 12 与 76比较， 交换
第二趟—35 99 18 76 12
99 35 18 76 12 // 35 与 99比较， 交换
99 35 18 76 12 // 35 与 18比较， 不交换
99 35 76 18 12 // 18 与 76比较， 交换
第三趟—99 35 76 18 12
99 35 76 18 12 //99 与 35比较， 不交换
99 76 35 18 12 //35 与 76比较， 交换
第四趟—99 76 35 18 12
99 76 35 18 12 //99 与 76比较， 不交换
转化为代码
#include <stdio.h>
int main(int argc, const char * argv[]) {
int a[5];
int t;
//数据初始化
for (int i=0; i<5; i++) {
scanf("%d", &t);
a[i] = t;
}
int temp;
for (int i=0; i<4; i++) { //趟数，共4趟
for (int j=1; j<5-i; j++) { //比较次数，5-第i趟
if (a[j-1]<a[j]) { //如果小于就交换位置
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
for (int i=0; i<5; i++) {
printf("%d", a[i]);
}
printf("\n");
return 0;
}
变形
输入n个数，n<100,使用冒泡排序，按从大到小的方式进行排序。
#include <stdio.h>
int main(int argc, const char * argv[]) {
// insert code here...
int a[100], n;
scanf("%d", &n);
for (int i=0; i<n; i++) {
scanf("%d", &a[i]);
}
for (int i=0; i<n-1; i++) {
for (int j=1; j<n-i; j++) {
int temp;
if (a[j-1]<a[j]) {
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
for (int i=0; i<n; i++) {
printf("%d", a[i]);
}
printf("\n");
return 0;
}
姓名，分数排序
5个人的名字和分数：huhu 5分，哈哈 3分， xixi 5分，hengheng 5分， river 8分。请按照分数从高到低，输入他们的名字。
#include <stdio.h>
int main(int argc, const char * argv[]) {
// insert code here...
struct student {
char name[21];
int score;
};
int n;
scanf("%d", &n);
struct student stu[100];
for (int i=0; i<n; i++) {
scanf("%s %d", stu[i].name, &stu[i].score);
}
for (int i=0; i<n-1; i++) {
for (int j=1; j<n-i; j++) {
struct student temp;
if (stu[j-1].score < stu[j].score) {
temp = stu[j-1];
stu[j-1] = stu[j];
stu[j] = temp;
}
}
}
for (int i=0; i<n; i++) {
printf("%s\n", stu[i].name);
}
return 0;
}
总结
如果n个数排序，需要n-1趟操作。而每一趟都需要从第一次开始进行相邻比较，将小的数放在后面，比较完毕后向后挪一位继续比较，如此重复，知道最后。时间复杂度：(n-1)+(n-2)+....+1 = O(N^2)
