冒泡排序的基本思想

每次比较两个相邻的元素，如果它们的顺序错误，就把它们的交换过来。

举例分析

对 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)

重拾算法Day02-冒泡排序