java面试：手写代码

二分查找法。

/**

 *   二分查找法：给定一组有序的数组，每次都从一半中查找。直到找到要求的数据。

 *   主要是得找到下标的表示方法。

 */

public class BinaryFind {

    /**

     * 使用二分法，找到有序数组中的某个数，返回下标。

     * @param sortedArray

     * @param number

     * @return

     */

    public int find(int[] sortedArray,int number){

          if(sortedArray==null)  {

              throw new IllegalArgumentException();

          }

          int last=sortedArray.length-1;

          int start=0;

          //没找到对应的数据，就一直循环查找

          while ( start<= last ) {

              //先找到中间的元素的下标 ， mid是首尾下标的和的一半

               int mid= (start+last)/2 ;

               if( sortedArray[mid] > number   ) {

                   last=mid-1;

               }else if(sortedArray[mid] <number ){

                   start=mid+1;

               }else {

                   return  mid;

               }

          }

         return  -1;

}

排序算法

1.快速排序

/**

 * 快速排序.

 * https://gitbook.cn/books/59f6a752d97c2122653a169e/index.html

 */

public class QuicklySort {

    /**

     *

     * @param a 数组

     * @param low  数组开始的下标。也就是0。

     * @param high  数组末尾的下标。也就是length-1。

     */

    public int[] sort(int a[],int low,int high){

        if(low>high || a==null) {

            return null;

        }

        int i=low;

        int j=high;

        //key设置为数组首位

        int key=a[low];

        //while结束后，小于key的全部放在key的左边，大于key的全部放在右边。。

         while (i<j) {

               //最后面的下标，从后向前遍历，找到第一个大于key的数据，将它赋给数组首位

                while (i<j && key<=a[j]) {

                     j--;

                }

                a[i]=a[j];

                //最前面的下标，从前向后遍历，找到第一个小于key的数据

                while (i<j && key>=a[i]) {

                    i++;

                }

                a[j]=a[i];

                a[i]=key;

            }

        //以下的i就是key的下标，对key两边的数据分别进行排序。

           sort(a,low,i-1);

           sort(a,i+1,high);

        return  a;

    }

}

2.冒泡排序

比较低端，不建议写。

多线程

1.手写一下生产者消费者模式，不要用BlockingQueue。

思路：可以使用wait()，notify()

2.手写一个死锁。

设计模式

设计模式的代码详情见：

设计模式代码示例

1.手写一下单例模式。

单例模式示例

2.手写一下工厂模式。

3.手写一下观察者模式。

观察者模式示例

说起来很尴尬，我曾经在面试平安某个子公司时，一面聊了一个小时顺利通过，二面因为没能手写观察者模式，十分钟就结束了面试。当时的心情真的好难受。

待补充。

参考资料：

十大排序算法全面解析-Java实现

《剑指offer》