冒泡排序，C语言实现

来源：cnblogs　　作者：Taltao　　时间：2018/12/10 9:44:27　　对本文有异议

冒泡排序是一种稳定排序，时间复杂度平均为O(n^2)，最好的时间复杂度为O(n)，最坏为O(n^2)。

排序时每次只比较当前元素与后一个元素的大小，如果当前元素大于后一个元素，则交换，如此循环直到队尾，每轮排序都可以保证将当前排序下最大的元素送到未排序部分的队尾。

有n个元素要排列，故要执行n次数组的整体大排列。

每次大排列中都要比较当前元素与后一个元素的大小，每轮要比较n-1次，但是因为之前的每一轮都将一个元素放置到了正确的位置，所以无需比较，若设之前累计循环了i次，将i个元素正确地放置在了数组的末尾，所以每轮大排列只需要比较n-1-i次。

代码如下

冒泡排序：

#include <stdio.h>
 
void bubblingSort(int arr[], int n) {
    int i, j, temp;
    // 每次将一个元素送到末尾，n个元素，执行n次
    for (i = 0; i < n; ++i) {
        // 之前的循环已经将i个元素送到末尾，不需要再次比较，故减去，因为跟后一个元素比较，为了避免溢出，故减一
        for (j = 0; j < n - i - 1; ++j) {
            // 如果当前的元素比后一个元素小，就交换
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
int main() {
    int i;
    int arr[10] = {5, 2, 3, 8, 1, 2, 6, 9, 3, 7};
    bubblingSort(arr, 10);
    for (i = 0; i < 10; ++i) {
        printf("%d ", arr[i]);
    }
    return 0;
}

从前面的图可以看出，冒泡排序在后几轮实际上已经排好序了，但还是在循环校验。当每次大排列时如果没有一个元素发生交换，数组就已经排好序了，可以终止循环。我们修改一下代码，加上判定元素交换的标志。

优化后的冒泡排序：

#include <stdio.h>
 
void bubblingSort(int arr[], int n) {
    int i, j, temp;
    int flag = 0;   // flag用来校验每轮循环有没有移动元素,0为没有移动，1为移动
    // 每次将一个元素送到末尾，n个元素，执行n次
    for (i = 0; i < n; ++i) {
        flag = 0;
        // 之前的循环已经将i个元素送到末尾，不需要再次比较，故减去，因为跟后一个元素比较，为了避免溢出，故减一
        for (j = 0; j < n - i - 1; ++j) {
            // 如果当前的元素比后一个元素小，就交换
            if (arr[j] > arr[j + 1]) {
                flag = 1;   // 有数据交换
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        // 没有数据交换，提前结束
        if (flag == 0) {
            break;
        }
    }
}
int main() {
    int i;
    int arr[10] = {5, 2, 3, 8, 1, 2, 6, 9, 3, 7};
    bubblingSort(arr, 10);
    for (i = 0; i < 10; ++i) {
        printf("%d ", arr[i]);
    }
    return 0;
}