排序——软件测试工程师面试秘籍(09)

发表于:2021-11-24 09:34

字体: | 上一篇 | 下一篇 | 我要投稿

 作者:G. li    来源:51Testing软件测试网原创

#
面试
#
求职
分享:
  2.1.5  排序
  考点:各种排序算法及它们的时间复杂度。
  排序算法有很多,包括插入排序算法、冒泡排序算法、堆排序算法、归并排序算法、选择排序算法、计数排序算法、基数排序算法、桶排序算法、快速排序算法等。下面介绍几种常考的排序算法。

  1.冒泡排序算法
  简单的冒泡排序算法如下。
public void bubbleSort()
      {
      int out,in; 
      for(out=nElems-1;out>0;out--)   
         for(in=0;in<out;in++)   
            if(a[in]>a[in+1]) 
               swap(in,in+1);   
      }

  上述冒泡排序算法的时间复杂度为O(n2)。

  2.选择排序算法
  常用的选择排序算法如下。
public void selectionSort()
      {
      int out,in,min;
 
      for(out=0;out<nElems-1;out++)   
         {
         min=out;                     
         for(in=out+1;in<nElems;in++)
            if(a[in]<a[min] )  
                min=in;  
         swap(out,min);                
         }
      }

  上述选择排序算法的时间复杂度为O(n2)。

  3.插入排序算法
  在插入排序算法中,一组数据在某个时刻是局部有序的,而在冒泡排序和选择排序中是完全有序的。
public void insertionSort()
      {
      int in,out;
 
      for(out=1;out<nElems;out++)    
         {
         long temp=a[out];         
         in=out;                     
         while(in>0&&a[in-1]>=temp)
            {
            a[in]=a[in-1];           
            --in;                   
            }
         a[in]=temp;                
         } 
      } 

  上述插入排序算法的效率比冒泡排序的高一倍,比选择排序算法略高,但其时间复杂度也是O(n2)。如果数据基本有序,几乎需要O(n)的时间。

  4.快速排序算法
  快速排序算法的根本机制在于划分,划分数据就是把数据分为两组,使所有关键字大于特定值的数据项在一组,使所有关键字小于特定值的数据项在另一组。
public int partitionIt(int left,int right,long pivot)
       {
       int leftPtr=left-1;  
       int rightPtr=right+1; 
       while(true)
          {
          while(leftPtr<right &&      
                theArray[++leftPtr]<pivot)
             ; 
 
          while(rightPtr>left &&      
                theArray[--rightPtr]>pivot)
             ;  
          if(leftPtr>=rightPtr) 
             break;             
          else                  
             swap(leftPtr,rightPtr);   
          }  
       return leftPtr;        
       }  

  快速排序算法本质上通过把一个数组划分为两个子数组,并递归地调用自身为每一个子数组进行快速排序。
  综上所述,常用排序算法的时间复杂度对比如表2.1所示。
表2.1 常用排序算法的时间复杂度对比

查看《软件测试工程师面试秘籍》全部连载章节
版权声明:51Testing软件测试网获得人民邮电出版社和作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可,不得对本文内容复制、转载或进行镜像,否则将追究法律责任。
《2023软件测试行业现状调查报告》独家发布~

关注51Testing

联系我们

快捷面板 站点地图 联系我们 广告服务 关于我们 站长统计 发展历程

法律顾问:上海兰迪律师事务所 项棋律师
版权所有 上海博为峰软件技术股份有限公司 Copyright©51testing.com 2003-2024
投诉及意见反馈:webmaster@51testing.com; 业务联系:service@51testing.com 021-64471599-8017

沪ICP备05003035号

沪公网安备 31010102002173号