冒泡排序是一种基本的排序算法,其基本思想为每次遍历将较小的值移到前面,像密度比较小的气泡从水中冒出一样。

冒泡的C实现:

void bubble(int *n, int len)
{
    int i, j;
    int sorted;
    for (i=0; i<len; i++) {
        sorted = 1;
        for (j=len-1; j>i; j--) {
            if (*(n+j) < *(n+j-1)) {
                swap(n+j, n+j-1);
                sorted = 0;
            }
        }
        if (sorted) break;
    }
}

冒泡排序最差情况的计算次数为\((n-1) + (n-2) + \cdots + 1 = n (n -1) / 2\) , 由此可知冒泡排序的时间复杂度为\(O(n^2)\) , 冒泡排序需要的额外空间为\(O(1)\) , 冒泡最优情况下时间复杂度接近\(O(n)\) , 冒泡排序是稳定的.

comments powered by Disqus