征服面试官的冒泡排序算法

我就是我 2022-06-04 05:29 129阅读 0赞

### 一：目录： ###

**1：选择哪种方法实现排序？**  
**2：如何用C语言实现冒泡排序？**   
**３：如何实现一个通用的冒泡排序？**

### 二：实现： ###

**1：选择哪种方法实现排序？**

在面试的时候，面试官最喜欢问得问题，如果要实现一组数据的排序，那么你会选择哪种方法？ 冒泡排序？选择排序？快速排序？希尔排序？ 我想，我们最熟悉的莫过于冒泡排序了吧，C语言会提到，到C++会提，数据结构中也会讲，足以说明它的重要性；

那么要实现冒泡排序法，那么你会首先想到哪种方式呢？哪种最具说服力？

**概念：**冒泡排序法是一种简单的排序算法。它重复地访问待排序的序列，一次比较两个元素，如果他们的顺序不符合条件要求，就把他们交换过来，访问序列的工作重复地进行直到没有带交换的元素，此时排序完成。

**2：用C语言实现冒泡排序**

这里以升序为例：

//简单的冒泡排序法（升序）
    #include<stdio.h>
    #include<string.h>
    void bubble_sort(int arr[],int sz)
    {
        int i=0;
        int j=0;
        for(i=0;i<sz-1;i++)
        {
            for(j=0;j<sz-1-i;j++)
            {
                if(arr[j]>arr[j+1])
                {
                    int tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;   
                }
            }
        }
    }
    
    int main()
    {
        int arr[]={
       3,4,6,8,1,9,2,0,5,7};
        int sz=sizeof(arr)/sizeof(arr[0]);
        int i=0;
        bubble_sort(arr,sz);
        for(i=0;i<sz;i++)//打印数组
        {
            printf("%d\n",arr[i]);
        }
        return 0;
    }

运行结果如下：  
![图一][SouthEast]

上述实现方法有很多的缺陷和不足，在面试过程中，这种简单的冒泡排序肯定是不占优势的，那么，如何写一个通用的冒泡排序呢？

**３：如何实现一个通用的冒泡排序？**

\++使用函数模板及迭代器来实现++

**（1）示意图：**  
![图二][SouthEast 1]  
**（2）实现程序**

//升序
    #include<iostream>
    #include<functional>
    #include<algorithm>
    using namespace std;
    template<class Iterator>
    void Bubble(Iterator first,Iterator last)
    {
        while(first != last)
        {
            Iterator cur=first;
            Iterator next=cur+1;
            while(next!=last)
            {
                if(*cur>*next)//升序排列
                    swap(*cur,*next);
                    cur=next;
                    ++next;
            }
            --last;
        }
    }
    
    int main()
    {
        int arr[]={
       3,4,6,8,1,9,2,0,5,7};
        Bubble(arr,arr+sizeof(arr)/sizeof(arr[0]));
            for(int i=0;i<10;i++)
            {
                cout<<arr[i]<<endl;
               }
        return 0;
    }

**执行结果：**  
![图三][SouthEast 2]

如果要实现降序排列，那么，我们只需将上述代码 Bubble函数中的`if(*cur>*next)`改为：

if(*cur<*next)

程序实现结果如下：

![图四][SouthEast 3]

若代码量十分大，显然，要想找到改的这条if语句是有难度的，能不能封装一个函数，使得外部用户通过其提供的接口来改变它到底是升序还是降序呢？　这就好比收音机的音量键，一个控制声音调高，另外一个负责调低音量；至于调高还是调低，只用按动收音机的外部控制开关即可，不关心它内部的具体结构；

下面，我们放出今天的主角：

#include<iostream>
    #include<functional>
    #include<algorithm>
    using namespace std;
    
    template<class T>
    class Less//升序排列
    {
    public:
        bool operator()(const T&left,const T&right)
        {
            return left<right;
        }
    };
    
    template<class T>
    class Greater//降序排列
    {
      public:
        bool operator()(const T&left,const T&right)
        {
            return left>right;
        }
    };
    
    template<class Iterator,class compare>//比较判断并且交换两数
    
    void Bubble(Iterator first,Iterator last,compare com)
    {
        bool Ischange=false;//首先将交换次数记为０
        while(first != last)
        {
            Ischange=false;
            Iterator cur=first;
            Iterator next=cur+1;
            while(next!=last)
            {
                if(com(*next,*cur))//if(!com(*cur，next))
                    {
                        swap(*cur,*next);//交换两数
                        Ischange=1;//交换次数加１
                     }
                    cur=next;
                    ++next;
            }
            if(!Ischange)//如果没有交换直接返回 
            {
                return ;
            }
    
            --last;
        }
    }
    
    //如果外部用户没有指定为升序还是降序，那么将默认为升序排列；
    template<class T,class Iterator>
    void Bubble(Iterator first,Iterator last)
    {
        Bubble(first,last,Less<T>());//直接调用升序排列的函数模板即可
    }
    
    int main()
    {
        int arr[]={
       3,4,6,8,1,9,2,0,5,7};
        //第三个参数传Less<int>()时，为升序排列，情况１
        //Bubble(arr,arr+sizeof(arr)/sizeof(arr[0]),Less<int>());
    
        //第三个参数传Greater<int>()时，降序排列，情况２
        //*Bubble(arr,arr+sizeof(arr)/sizeof(arr[0]),Greater<int>());
    
        //若不传第三个参数时，默认为升序，情况３
        Bubble<int>(arr,arr+sizeof(arr)/sizeof(arr[0]));
    
        for(int i=0;i<10;i++)//打印数组
            {
                cout<<arr[i]<<endl;
               }
        return 0;
    }

**执行结果**

（１）情况１：主函数中传Less();

![情况１][SouthEast 4]

（２）情况２：主函数中传Greater();  
![情况２][SouthEast 5]

（３）情况３：主函数调用函数时不传第三个参数（控制升序降序的参数不传）

![情况３][SouthEast 6]

这样一来，函数每一部分的功能显而易见，同时，就算代码由上万行，百万行乃至更多，都不用怕找不到排序条件了，在主函数里调用该排序函数参数列表中传入排序条件即可，排序的效率高，且代码不易出错。

你ｇｅｔ到了吗？

[SouthEast]: /images/20220604/6d7cab2ef04445c086b27c71f16a871e.png
[SouthEast 1]: /images/20220604/175de294522d4f1e944d5f5aead68075.png
[SouthEast 2]: /images/20220604/3aa1c4011cb843a1b57d8e5bb0e06eb3.png
[SouthEast 3]: /images/20220604/66eaa522abc1495ead7cf69597429e1e.png
[SouthEast 4]: /images/20220604/048a25254da94ba8be0d6040d98ddd70.png
[SouthEast 5]: /images/20220604/33e5b538f481448dae14a82814a233ce.png
[SouthEast 6]: /images/20220604/fd98b61a21f147c8972bb6e0884f0aa5.png