排序算法一——冒泡排序

浅浅的花香味﹌ 2022-06-10 02:07 150阅读 0赞

# **排序算法一：冒泡排序** #

最简单，最常用的排序方法之一。冒泡排序是稳定的，相同的值的相对位置在排序后没有改变。时间复杂度O（n^2）。  
冒泡排序的代码及其改进版：

/***************************************************** File name:1bubble.c Author: Tang Zhiqian Date:2017-08-07 17:07 *****************************************************/
    
    #include <stdio.h>
    
    #define MAX 10
    
    typedef int ElemenType;
    typedef ElemenType ARR[MAX];    //给数组另起名字
    int len = sizeof(ARR)/sizeof(ElemenType);    //数组长度
    
    void swap(ElemenType arr[],int i,int j);    //交换函数
    void print(ARR arr);    //打印
    void bubble1(ARR arr);    //未改进的冒泡排序
    void bubble2(ARR arr);    //改进后的冒泡排序
    
    int main()
    {
        ARR arr1 = {
       9,0,1,2,3,4,5,6,7,8};
        ARR arr2 = {
       9,0,1,2,3,4,5,6,7,8};
    
        printf("\n未改进的冒泡排序：\n");
        bubble1(arr1);
    
        printf("\n");
    
        printf("改进后的冒泡排序：\n");
        bubble2(arr2);
    
    
        return 0;
    }
    
    void bubble1(ARR arr)
    {
        int i,j;
    
        for (i = 0; i < len - 1; i++)
        {
            for (j = 0; j < len - i - 1; j++)
            {
                if (arr[j] > arr[j + 1])
                {
                    swap(arr,j,j+1);
                }
            }
            print(arr);
        }
    }
    
    void bubble2(ARR arr)
    {
        int i,j;
        int flag = 1;
    
        for (i = 0; i < len - 1; i++)
        {
            flag = 0;
            for (j = 0; j < len - i - 1; j++)
            {
                if (arr[j] > arr[j + 1])    
                {
                    flag = 1;     //进入这个判断，flag = 1；
                    swap(arr,j,j+1);
                }
            } 
            if (flag == 0)    //如果flag等于零，说明上一次循环没有交换位置，说明排序已经完成，则break
            {
                break;
            }
            print(arr);
        }
    }
    
    
    void  print(ARR arr)
    {
        int i;
        for (i = 0; i < len; i++)
        {
            printf("%d ",arr[i]);
        }
        printf("\n");
    }
    
    void swap(ElemenType arr[],int i,int j)
    {
        ElemenType temp;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

程序运行结果：  
![这里写图片描述][SouthEast]

在这里我们看到，未改进的bubble1排序，输出了9行排好序的数，而改进过的bubble2只输出了一行。未排序前的数字顺序为\{9，0，1，2，3，4，5，6，7，8\}，观察发现，其实经过一轮冒泡之后，这个数组就已经排好序了，但是程序不知道是否排好序，所以会一直循环完。 但是在bubble2中我添加了一个flag，进入第一个for循环就让flag=0，第二级for循环中if判断下flag= 1，假设二级for循环一圈后都没有进入到if里面，则flag = 0，说明这时候数组已经排好序了，因为它一轮比较之后都没有进入if里面执行swap函数。这样下来电脑就少执行了很多次 比较 的过程。

[SouthEast]: /images/20220610/25f8b386f41e472aa38d3a597ddb6af6.png