冒泡排序的基本思想
每次比較兩個相鄰的元素镊绪，如果它們的順序錯誤惰蜜，就把它們的交換過來蝴蜓。
舉例分析
對 12 35 99 18 76 按從大到小排序仅颇，排序方式：冒泡排序
原始數(shù)據(jù)
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比較粱年， 不交換
轉(zhuǎn)化為代碼
#include <stdio.h>
int main(int argc, const char * argv[]) {
int a[5];
int t;
//數(shù)據(jù)初始化
for (int i=0; i<5; i++) {
scanf("%d", &t);
a[i] = t;
}
int temp;
for (int i=0; i<4; i++) { //趟數(shù)售滤，共4趟
for (int j=1; j<5-i; j++) { //比較次數(shù)，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個數(shù)台诗，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;
}
姓名拉队，分數(shù)排序
5個人的名字和分數(shù)：huhu 5分弊知，哈哈 3分， xixi 5分粱快，hengheng 5分秩彤， river 8分。請按照分數(shù)從高到低皆尔，輸入他們的名字呐舔。
#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;
}
總結(jié)
如果n個數(shù)排序，需要n-1趟操作慷蠕。而每一趟都需要從第一次開始進行相鄰比較珊拼，將小的數(shù)放在后面，比較完畢后向后挪一位繼續(xù)比較流炕，如此重復(fù)澎现，知道最后。時間復(fù)雜度：(n-1)+(n-2)+....+1 = O(N^2)
