C语言-数据结构-冒泡排序及优化-源代码

电玩女神 2022-07-13 14:27 129阅读 0赞

**1. 冒泡排序定义及时间复杂度（来自百度百科）**

冒泡排序（Bubble Sort），是一种[计算机科学][Link 1]领域的较简单的[排序算法][Link 2]。

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢　“浮”　到数列的顶端，故名。

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数　C　和记录移动次数　M　均达到最小值：Cmin=n-1，Mmin=0。所以，冒泡排序最好的 [时间复杂度][Link 3]为　O(n)。

若初始文件是反序的，需要进行　 n-1　趟排序。每趟排序要进行　n-i　次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

Cmax=n(n-1)/2=O(n^2)

Mmax=3\*n(n-1)/2=O(n^2)

冒泡排序的最坏时间复杂度为　 O(n^2)。

综上，因此冒泡排序总的平均时间复杂度为　 O(n^2) 。

**2. 伪冒泡排序**

从冒泡排序的定义可以看出，冒泡排序是相邻的数据两两比较，而伪冒泡排序则是固定一个数据和其他数据进行比较，如下面的代码。

#include<stdio.h>
    
    void bubble(int a[], int n)
    {
        int i, j, temp, c1=0, c2=0;
        for(i=0;i<n;i++)
        {
            for(j=i+1;j<n;j++)
            {
                c1++;
                if(a[i]>a[j])//这里是a[i]与每个a[j]比较
                {
                    temp=a[i];
                    a[i]=a[j];
                    a[j]=temp;
                    c2++;
                }
            }
        }
        printf("总计数据交换%d次, 访问数组%d次\n\n", c2, c1);
    }
    
    int main(void)
    {
        int i;
        int a[10]={1,2,0,3,4,5,6,7,9,8};
        printf("排序前：");
        for(i=0;i<10;i++)
        {
            printf("%d",a[i]);
        }
        printf("\n\n\n");
        bubble(a, 10);
        printf("排序后：");
        for(i=0;i<10;i++)
        {
            printf("%d",a[i]);
        }
        printf("\n\n\n");
        return 0;
    }

运行结果如下图：

![Center][]

**3. 冒泡法排序**

#include<stdio.h>
    
    void bubble(int a[], int n)
    {
        int i, j, temp, c1=0, c2=0;
        for(i=n-1;i>0;i--)
        {
            for(j=0;j<i;j++)
            {
                if(a[j]>a[j+1])
                {
                    c1++;
                    temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
                c2++;
            }
        }
        printf("总计数据交换%d次, 访问数组%d次\n\n", c1, c2);
    }
    
    int main(void)
    {
        int i;
        int a[10]={1,2,0,3,4,5,6,7,9,8};
        printf("排序前：");
        for(i=0;i<10;i++)
        {
            printf("%d",a[i]);
        }
        printf("\n\n\n");
        bubble(a, 10);
        printf("排序后：");
        for(i=0;i<10;i++)
        {
            printf("%d",a[i]);
        }
        printf("\n\n\n");
        return 0;
    }

运行结果如下图：

![Center 1][]

**4. 优化后的冒泡排序**

前面两种排序都只有在跑完所有位置后，才会停止，但是很多时候不用跑完，数据就已经按顺序排好了，对于这种情况则可以减少一些操作。下面的做法就是添加一个flag，去检查数据是否已经排好，如果已经排好则停止操作。

#include<stdio.h>
    #include<stdbool.h>
    
    void bubble(int a[], int n)
    {
        int i, j, temp, c1=0, c2=0;
        bool flag=1;
        for(i=n-1;i>0 && flag;i--)
        {
            flag=0;
            for(j=0;j<i;j++)//如果在整个内循环中都没有交换过数据，说明数据已经排好
            {
                if(a[j]>a[j+1])
                {
                    c1++;
                    temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                    flag=1;
                }
                c2++;
            }
        }
        printf("总计数据交换%d次, 访问数组%d次\n\n", c1, c2);
    }
    
    int main(void)
    {
        int i;
        int a[10]={1,2,0,3,4,5,6,7,9,8};
        printf("排序前：");
        for(i=0;i<10;i++)
        {
            printf("%d",a[i]);
        }
        printf("\n\n\n");
        bubble(a, 10);
        printf("排序后：");
        for(i=0;i<10;i++)
        {
            printf("%d",a[i]);
        }
        printf("\n\n\n");
        return 0;
    }

运行结果如下图：

![Center 2][]

[Link 1]: http://baike.baidu.com/view/92404.htm
[Link 2]: http://baike.baidu.com/view/297739.htm
[Link 3]: http://baike.baidu.com/view/104946.htm
[Center]: /images/20220713/ec80a4ea6e2a43e8aac84676942440fc.png
[Center 1]: /images/20220713/8b6894fe23b8405993780a285c48d4d0.png
[Center 2]: /images/20220713/2f66ba43e178498cbee14329f5b974ed.png