在面试中经常会遇到一些写算法的题目,这里就总结三个比较常用的算法,
首先,就是冒泡排序了,因为在面试中它的出镜率很高,所以它首当其冲,有些人看算法一开始都能理解,并能敲出,但由于时间的推移,就会慢慢忘记。
我也一样,所以建议同鞋们能背过,这样就不会忘了(废话):
这里就写核心代码吧:- int out,in;
- for(out = a.length-1;out>1out--){
- for(in = 0;in<out;in++){
- if(a[in]>a[in+1])
- swap(in,in+1);
- }
- }
复制代码 冒泡排序是比较慢的,但相对好容易理解。下面是选择排序:- int out,min,inner;
- for(out=0;out<a.length-1;out++){
- min = out;
- for(inner=out+1;inner<a.length;inner++){
- if(a[min]>a[inner])
- min=inner;
- }
- swap(out,min)
- }
复制代码 选择排序比冒泡排序稍优一些,执行速度也稍微快一些。接下来是插入排序:- int out,inner;
- for(out=1;out<a.length;out++){
- long temp = a[out];
- inner=out;
- while(inner>0&&a[inner-1]>temp){
- a[inner] = a[inner-1];
- --inner;
- }
- a[inner]=temp;;
- }
复制代码 插入排序与其他两个相比是最快的,但相对理解起来比较难些。下面就是最快的了---快速排序:- public void recQuickSort(int left, int right)
- {
- if(right-left <= 0)
- return; // already sorted
- else
- {
- long pivot = theArray[right];
-
- int partition = partitionIt(left, right, pivot);
- recQuickSort(left, partition-1);
- recQuickSort(partition+1, right);
- }
- }
- //--------------------------------------------------------------
- public int partitionIt(int left, int right, long pivot)
- {
- int leftPtr = left-1;
- int rightPtr = right;
- while(true)
- {
- while( theArray[++leftPtr] < pivot )
- ;
-
- while(rightPtr > 0 && theArray[--rightPtr] > pivot)
- ;
- if(leftPtr >= rightPtr)
- break;
- else
- swap(leftPtr, rightPtr);
- }
- swap(leftPtr, right);
- return leftPtr;
- }
复制代码 该算法非常之快,执行速度与其他三个算法相比,简直一个天上一个地下,非常吊,但代码复杂度也有目共睹,理解起来不宜,而且随着的时间的推移,也很容易忘记。所以能背过最好
|