冒泡排序详解

待我称王封你为后i 2022-07-18 01:26 181阅读 0赞

**基本概念：**

冒泡排序（**bubble sort**）并没有什么特殊的价值，它是一种相对较慢的排序。

冒泡排序包括一个简单的双重for循环。第一次内部for循环从记录数组的底部比较到顶部，**比较相邻的值**，如果低序号的值比高序号的值大，则将二者交换顺序，这个过程将使它像个气泡一样被推到数组的顶部。第二次再重复调用上面的过程，但是既然知道最大元素第一次就被排到了数组的最上面（数组尾），因此就没有再比较最上面两个元素的必要了。

冒泡排序的**时间复杂度为****O(n²)**，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况，不能简单的用来计算精确值。

需要注意的是[选择排序][Link 1]和冒泡排序是两个不同的概念，网上很多文章是混淆了这两种算法。

**过程如图示：**

![20160904141420269][]

**简单例子：**

void bubble_sort(int arr[], int size)
    {
        if (arr == NULL)
            return ;
    
        int i, j, temp, flag;
        for (i = 0; i < size - 1; ++i) {
            /* 每轮内循环都将一个最大值浮到最上面 */
            flag = 1;
            for (j = 0; j < size - i - 1; ++j) {
                if (arr[j] > arr[j+1]) {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = 0;
                }
            }
    
            /* 每轮内循环后输出数组的现状 */
            int k;
            printf("the %d for(): ", i);
            for (k = 0; k < size; ++k) {
                printf("%d ", arr[k]);
            }
            printf("\n");
    
            /* 已经不需要交换 */
            if (flag)
                return ;
        }
    }
    
    int main()
    {
        int arr[] = {4, 5, 1, 7, 8, 0, 3, 2, 6, 9};
        int size = sizeof(arr) / sizeof(int);
    
        //sort
        bubble_sort(arr, size);
    
        //print
        int i = 0;
        for (i; i < size; ++i) {
            printf("%d\n", arr[i]);
        }
    
        return 0;
    }

**编译运行：**

![SouthEast][]

原文出自：[http://blog.csdn.net/daiyudong2020/article/details/52432040][http_blog.csdn.net_daiyudong2020_article_details_52432040]

End;

[Link 1]: http://blog.csdn.net/daiyudong2020/article/details/52433712
[20160904141420269]: /images/20220717/f92f5b6072534556ae9452dc276bbaf5.png
[SouthEast]: /images/20220717/d4e54e6cc8da469a95c917fd79aa5ca9.png
[http_blog.csdn.net_daiyudong2020_article_details_52432040]: http://blog.csdn.net/daiyudong2020/article/details/52432040