JAVA常用算法以及常用设计模式(面试经常设计到）

学习目标：

记录下笔试以及面试常问的常用算法以及常用设计模式，其中算法有快速排序，冒泡排序，选择排序和折半查找，模式有单例与工作，并不是所有，是常见

学习内容：

1.快速排序算法

1.从数列中挑出一个元素，作为基准进行比较

2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码：import java.util.Arrays;

public class TestQuickSort {

       private static int partition(int[] arr, int low, int high) {

               //指定左指针i和右指针j

                int i = low;

                int j= high;

           //将第一个数作为基准值。挖坑

                int x = arr[low];

          //使用循环实现分区操作

           while(i<j){//5      8

                           //1.从右向左移动j，找到第一个小于基准值的值arr[j]

                    while(arr[j]>=x && i<j){

                              j–;

                                                         }

//2.将右侧找到小于基准数的值加入到左边的（坑）位置，左指针想中间移动一个位置 i++

                            if(i<j){

                                    arr[i] = arr[j];

                                     i++;

}

        //3.从左向右移动i，找到第一个大于等于基准值的值arr[i]

                    while(arr[i]<x && i<j){

                                   i++;

                          }

            //4.将左侧找到的打印等于基准值的值加入到右边的坑中，右指针向中间移动一个位置j–                                    if(i<j){

                                          arr[j] = arr[i];

                                                          j–;

                                         }

                                                     }/

/使用基准值填坑，这就是基准值的最终位置

                                        arr[i] = x;//arr[j] = y;

//返回基准值的位置索引

                                      return i; //return j;

}

     private static void quickSort(int[] arr, int low, int high) {//???递归何时结束

if(low < high){

//分区操作，将一个数组分成两个分区，返回分区界限索引

                 int index = partition(arr,low,high);

//对左分区进行快排

                quickSort(arr,low,index-1);

//对右分区进行快排

                 quickSort(arr,index+1,high);

          }

}

public static void quickSort(int[] arr) {

                       int low = 0;

                       int high = arr.length-1;

                       quickSort(arr,low,high);

}

public static void main(String[] args)

{

//给出无序数组

                int arr[] = {72,6,57,88,60,42,83,73,48,85};

 //输出无序数组

                System.out.println(Arrays.toString(arr));

//快速排序

                  quickSort(arr);

//partition(arr,0,arr.length-1);

//输出有序数组

                    System.out.println(Arrays.toString(arr));

               }

}

2.冒泡排序

1.比较相邻的元素。如果第一个比第二个大，就交换它们两个；

2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；

3.针对所有的元素重复以上的步骤，除了最后一个；

4.重复步骤1~3，直到排序完成。

代码：public class BubbleSort{

public static void bubbleSort(int[] arr){

/空数组或只有一个元素的数组，则什么都不做。

              if(arr = null arr.length = 1)return;

/外层循环表示趟数。

              for(int i 0; i arr.length-1; i++){

/默认有序，如果发生交换说明无序。

              boolean isSorted true;

/j表示要比较元素对的第一个。

                for (int j 0; j

                   /不能写>=，否则不稳定。

                   if (arr[j] > arr[j + 1]) {

                     int temp arr[j];

                      arr[j] = arr[j + 1];

                        arr[j 1]= temp;

/发生交换了，说明无序。

                          isSorted false;

//如果没有发生交换，则数组已经有序，结束冒泡。

                           if(isSorted) return;

/把每一趟排序的结果也输出一下。

                    System.out.print(“第”+(i+1)+”:”);

                     print(arr);

public static void main(String[] args){

          int[] arr = {6, 9, 1, 4, 5, 8, 7, 0, 2, 3);

          System.out.print(“排序前：”)；

          print(arr);

          bubbleSort(arr);System.out.print(“排序后：”)；

          print(arr);

public static void print(int[] arr){

              if(arr = null) return;

                     for(int i: arr){

                           System.out.print(i +””)

                         System.out.println();

}

3.选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后， 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。 以此类推，直到所有元素均排序完毕。

代码：

public static int selectionSort(int[] array){

     int len array.length;

 /如果数组长度为0或者1，都是不用排序直接返回

 if(len == 0 | len == 1) {

return array;

}

            for(int i = 0; i < len – 1; i++) {

                  int minIdx i;

                    for(intj= i+ 1; j len; j++){

/找到最小的数

                         if(array[minIdx] array]){

/保存最小数的索引

                                  minIdx =j;

                }

            }

/如果一轮比较下来都没有变更最小值的索引则无需调换顺序

                 if(minIdx ! i){

                      int tmp array[i];

                         array[i] array[minIdx];

                         array[minIdx] tmp;

                       }

                 }

         return array;

}

4.折半查找

前提：查找表必须使用顺序存储结构；其次，查找表必须按关键字大小有序排列。首先取中间数据项，然后作比较，如果数据项比待查关键字大，那么就取数据项前半部分中间数据项在进行比较，直至查到该关键字.

static int binarySearch(int array, int value, int left, int right){

                        if(left>right){//退出条件

                         return-1;/没有找到指定元素

                           int mid =(left + right)>>>1;/相当于 mid=(left + right)/2

                                     if(array[mid] = value){

                                                   return mid;

                                     }else if (array[mid] value){

                             /递归调用查找左边

                                       return binarySearch(array,value,left,mid-1);

                                      }else

 /递归调用查找右边

                                          return binarySearch(array,value, mid+1,right);

static int binarySearch(int[] array, int value, int left, int right){

                                   int low= left;//开始位置

                                   int high=right-1;//结束位置

                                               while(low < high){

                                                     int mid =(low + high)>>1;

/相当于 mid = (low +right)/2 int midVal = array[mid];/取中间值

                                                     if(midVal<value){//中间值小于要查找的关键字比较

                                                                 low mid +1;

                                                     }else if(midVal>value){//中间值大于要查找的关键字比较 high=                                                               mid-1;

                                                     }else

                                                     return mid;/查找成功，返回找到的位置

                                                      return-(low+1);//没找到，返回负值

                      }

5.单例设计模式

饿汉式的单例模式

在类加载的时候创建单例实例，而不是等到第一次请求实例的时候的时候创建

1、私有的无参数构造方法singleton(),避免外部创建实例

2、私有静态属性instance

3、公有静态方法getInstance()

通过单例模式设计的方法创建的类在当前进程中只有一个实例。

public class Singleton{

private static Singleton instance =new Singleton();

                      private Singleton(){}

                      public static Singleton getInstance(){

                           return instance;

                              }

}

/**

懒汉式的单例模式

·在类加载的时候不创建单例实例，只有在第一次请求实例的时候的时候创建，使用了

synchronized所以是线程安全。

*/

public class Singleton{

private static Singleton instance;

private singleton(){}

/**

多线程情况的单例模式，避免创建多个对象

*/

public statia Singleton getInstance()(

                      if(instance=null)(//避免每次加锁，只有第一次没有创建对象时才加锁

                           synchronized(Singleton.class){//加锁，只允许一个线程进入

                              if(instance–null)//只创建一次对象

                                        instance new Singleton();

                                    }

                            }

             }

return instance;

          }

}

6.工厂设计模式

工厂模式分为简单工厂模式和工厂方法模式，简单工厂模式是只有一个工厂类，这个类里面有很多的方法，每一个方法的返回值就是一个对象，你需要什么对象，就调用什么方法。工厂方法模式是每一个实体类都有一个工厂，所以有很多的工厂，每一个工厂里面的返回值就是对应的一个对象，所以，想要使用什么对象，直接创建对应的工厂类，调用里面的方法就可以得到。