冒泡排序

Bubble Sort

说明

. 小的数据浮上来|到序列前面；大的数据沉下去|到序列后面

. 从0开始，比较相邻的2个数据项

. 如果前者大于后者，就立即交换位置；否则保持不动

. 后移1位，继续比较相邻的2个数据项

. 每趟比较结束后，将最大的数据放到最后

. 第1趟，比较次数为 n - 1；第2趟比较次数为 n - 2；依次类推

. 共需要 n - 1 趟排序

求序列{8,6,9,2,3,7}的冒泡排序过程

冒泡排序过程
原始数据	8 6 9 2 3 7
第1轮比较	6 8 2 3 7 9
第2轮比较	6 2 3 7 8 9
第3轮比较	2 3 6 7 8 9
第4轮比较	2 3 6 7 8 9
第5轮比较	2 3 6 7 8 9

求序列{49,38,65,97,76,13,27,49}的冒泡排序过程

初始序列
0	1	2	3	4	5	6	7
49	38	65	97	76	13	27	49

第1趟冒泡
0	1	2	3	4	5	6	7
38	49	65	76	13	27	49	97

第2趟冒泡
0	1	2	3	4	5	6	7
38	49	65	13	27	49	76	97

第3趟冒泡
0	1	2	3	4	5	6	7
38	49	13	27	49	65	76	97

第4趟冒泡
0	1	2	3	4	5	6	7
38	13	27	49	49	65	76	97

第5趟冒泡
0	1	2	3	4	5	6	7
13	27	38	49	49	65	76	97

第6趟冒泡
0	1	2	3	4	5	6	7
13	27	38	49	49	65	76	97

第7趟冒泡
0	1	2	3	4	5	6	7
13	27	38	49	49	65	76	97

代码实现

. 需要双重循环实现

冒泡排序

#include <stdio.h>
void swap(int *a, int *b){
    int temp;
    if(*a > *b){
        temp = *a;
        *a = *b;
        *b = temp;
    }
}
void dis(int arr[], int len){
    int i = 0;    
    for(; i < len; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}
int main () {
    int arr[] = {49,38,65,97,76,13,27,49};
    int index = 0, len = sizeof(arr)/sizeof(arr[0]);
    dis(arr, len);
    for(; index < len-1; index++){
        int j=0;
        for(; j < len-1-index; j++){
            if(arr[j] > arr[j+1]){
                swap(&arr[j], &arr[j+1]);
            }
        }
        printf("第%d趟冒泡 ", index + 1);
        dis(arr, len);
    }
    return 0;
}

性能分析 Analysis

. 正序情况：O(N)

. 反序情况：O(N²)

. 平均时间复杂度：O(N²)

. 更多信息，请查看懒猫老师

改进

. 使用一个标记flag来标记本趟有没有交换；如果没有，说明数据已经有序，提前推出外层循环