A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 卞潇洋 中级黑马   /  2012-12-17 22:36  /  1475 人查看  /  1 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

在面试中经常会遇到一些写算法的题目,这里就总结三个比较常用的算法,
首先,就是冒泡排序了,因为在面试中它的出镜率很高,所以它首当其冲,有些人看算法一开始都能理解,并能敲出,但由于时间的推移,就会慢慢忘记。
我也一样,所以建议同鞋们能背过,这样就不会忘了(废话):
这里就写核心代码吧:
  1. int out,in;
  2. for(out = a.length-1;out>1out--){
  3.      for(in = 0;in<out;in++){
  4.           if(a[in]>a[in+1])
  5.               swap(in,in+1);
  6. }
  7. }
复制代码
冒泡排序是比较慢的,但相对好容易理解。下面是选择排序:
  1. int out,min,inner;
  2. for(out=0;out<a.length-1;out++){
  3.       min = out;
  4.      for(inner=out+1;inner<a.length;inner++){
  5.      if(a[min]>a[inner])
  6.              min=inner;
  7. }
  8.    swap(out,min)
  9. }
复制代码
选择排序比冒泡排序稍优一些,执行速度也稍微快一些。接下来是插入排序:
  1. int out,inner;
  2. for(out=1;out<a.length;out++){
  3.       long temp = a[out];
  4.       inner=out;
  5.       while(inner>0&&a[inner-1]>temp){
  6.            a[inner] = a[inner-1];
  7.            --inner;
  8. }
  9.       a[inner]=temp;;
  10. }
复制代码
插入排序与其他两个相比是最快的,但相对理解起来比较难些。下面就是最快的了---快速排序:
  1. public void recQuickSort(int left, int right)
  2.       {
  3.       if(right-left <= 0)
  4.           return;                      //    already sorted
  5.       else                             
  6.          {
  7.          long pivot = theArray[right];      
  8.                                             
  9.          int partition = partitionIt(left, right, pivot);
  10.          recQuickSort(left, partition-1);   
  11.          recQuickSort(partition+1, right);  
  12.          }
  13.       }  
  14. //--------------------------------------------------------------
  15.     public int partitionIt(int left, int right, long pivot)
  16.        {
  17.        int leftPtr = left-1;
  18.        int rightPtr = right;
  19.        while(true)
  20.           {
  21.           while( theArray[++leftPtr] < pivot )
  22.              ;  
  23.                                        
  24.           while(rightPtr > 0 && theArray[--rightPtr] > pivot)
  25.              ;

  26.           if(leftPtr >= rightPtr)
  27.              break;
  28.           else
  29.              swap(leftPtr, rightPtr);  
  30.           }
  31.        swap(leftPtr, right);
  32.        return leftPtr;
  33.        }
复制代码
该算法非常之快,执行速度与其他三个算法相比,简直一个天上一个地下,非常吊,但代码复杂度也有目共睹,理解起来不宜,而且随着的时间的推移,也很容易忘记。所以能背过最好


评分

参与人数 1技术分 +1 收起 理由
邵天强 + 1 神马都是浮云

查看全部评分

1 个回复

倒序浏览
忘了说一句了,swap()就是交换变量,相信都会写,再此就不写了
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马