面试常见算法——冒泡排序 - 技术分享 - 志盟培训
首页技术分享 面试常见算法——冒泡排序

面试常见算法——冒泡排序

更新时间:2017-05-25      作者:武老师       阅读:966

笔试面试的时候,我们经常会遇到以填空、上机、及分析算法时间复杂度、空间复杂度等问题,一些经典的算法是常见的考查范围,为什么会集中考查算法的实现和分析呢?

1.逻辑思维分析能力

2.代码的编写能力

3.代码效率是否会注意

4.想办法解决问题的能力(有同学一看没写过,就不分析)

今天我们实现一个常见的经典的算法——冒泡排序。

算法的基本思想:

每一趟排序依次比较相邻两个记录的关键字,如果发生逆序,则交换之

第一趟排序过程,n个数比较n-1次,如果逆序交换,则最大的数(49)就像“铅块”一样沉下去,最终n个无序数,变成了n-1个无序数和1个有序数。

以此类推,n个数进行冒泡排序,需要进行n-1趟排序过程。

面试常见算法——冒泡排序


冒泡排序的改进排序思路:

n个数进行冒泡排序,最大需要进行n-1趟排序过程。因为如果上一趟排序过程没有任何交换,则说明数列已经有序,不需要继续进行下一趟排序过程,因此在改进的排序算法中,我们需要记录change标记,如果有交换change标记置

1,如果没有交换change标记置0.没有交换则从算法中跳出。

voidbubble_sort(int a[],int n)

{

       int change = 0,temp,i,j;

       for(i=0;i<n-1;i++)

       {

               change = 0;

               //如果有交换change = 1;

               for(j=0;j<n-1-i;j++)

              {

                     if(a[j]>a[j+1])//相邻两个元素比较

                    {

                            temp = a[j];

                            a[j]=a[j+1];

                            a[j+1]=temp;

                            change = 1;

                    }

               }

               if(change == 0)

               {

                      break;

               }

       }

}

下面我们一起分析一下冒泡排序的算法效率:

n个数进行排序

最大趟数:n-1

最大比较次数:n-1+n-2+n-3+..1=n(n-1)/2

最大交换次数:n(n-1)/2

适用于基本有序序列,是一种稳定的排序算法。

其时间复杂度为O(n2),空间复杂度为O(n).

不适合大数据量的排序,如n = 10000, 排序算法执行估计花费几秒的时间。但是如果n=100000,排序算法执行估计花费几分钟的时间,n=1000000,排序算法的时间效率是与n2成正比,算法时间就会花费几个小时。

在线报名

志盟科技上海招聘

在线报名 联系我们

志盟科技深圳招聘

在线报名 联系我们

志盟科技北京招聘

在线报名 联系我们
联系我们

咨询热线:

咨询 QQ:517578         

就业学员

  • 就业学员

    姓名:郭凡凡 
    院校:阜阳师范学院
    就职:佳戴
    职位:软件工程师
    月薪:10000

  • 就业学员

    姓名:陈祥龙 
    院校:中北大学
    就职:美囤妈妈
    职位:软件工程师
    月薪:9000

  • 就业学员

    姓名:陈建伟
    院校:南昌航空大学
    就职:SONY
    职位:嵌入式工程师
    月薪:8000

×
×
  • *真实姓名
  • *联系手机
  • *上课地址
  •    QQ号码

温馨提示:请保持手机畅通,咨询老师将为您提供专属的一对一报名服务。

×
  • *真实姓名
  • *联系手机
  • *联系邮箱
  • * QQ号码

温馨提示:请保持手机畅通,咨询老师将为您提供专属的一对一的服务。

本站由 宽敬科技——创新企业的建站运营顾问 提供支持