黑马程序员技术交流社区

标题: 面试的一些算法（很实用） [打印本页]
作者: 卞潇洋    时间: 2012-12-17 22:36
标题: 面试的一些算法（很实用）
在面试中经常会遇到一些写算法的题目，这里就总结三个比较常用的算法，
首先，就是冒泡排序了，因为在面试中它的出镜率很高，所以它首当其冲，有些人看算法一开始都能理解，并能敲出，但由于时间的推移，就会慢慢忘记。
我也一样，所以建议同鞋们能背过，这样就不会忘了（废话）：
这里就写核心代码吧：
  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.              ;

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


作者: 卞潇洋    时间: 2012-12-17 22:38
忘了说一句了，swap()就是交换变量，相信都会写，再此就不写了



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2