九、設計模式以及查找、排序算法

九、設計模式

單例模式的幾種實作方法

懶漢模式、餓漢模式、雙重檢查加鎖

【1】懶漢模式：

延遲加載，在使用時才去初始化；

【2】餓漢模式：

【3】雙重檢查加鎖：

1. 說一下你熟悉的設計模式？

分為四類：

建立模式：單例模式、工程模式；

結構模式：代理模式；

行為模式：觀察者模式、疊代器模式；

線程池模式。

2. 簡單工廠和查詢工廠有什麼差別？

3. 常用的數組排序算法、查找算法？

常用的數組排序算法：冒泡排序、選擇排序、插入排序；

常用的數組查找算法：線性查找法、二分法查找法（即折半查找）：針對有序數組，需要先排好序再使用：eg：

public static int binarySearch(int[] arr,int number){
	int start=0;//數組下标從0開始
	int end=arr.length-1;//數組最大下标數為數組長度-1
	while(start<=end){
		int middle=(start+end)/2;
		if (number==arr[middle]) {
			return middle;
		}else if(number<arr[middle]){
			end=middle-1
		}else{
			start=middle+1;
		}
	}
	return -1;
}
           

3_1. 排序有哪幾種方法，用 Java實作一個快排？

有：冒泡排序、選擇排序、插入排序、歸并排序、配置設定排序、快速排序；

【1_ 冒泡排序 】： 兩兩比較，大的下沉（從下往上排序，上面是 j，下面是 j+1）；

int[] arr={1,7,6,3};
for (int i=0;i<arr.length-1;i++) {
    for (int j=0;j<arr.length-i-1;j++) {
        if (arr[j]>arr[j+1]) {
            int temp=arr[j+1];
            arr[j+1]=arr[j];
            arr[j]=temp;
        }
    }   
}
           

【2_ 選擇排序】： 每一輪找到最小值從上往下排序；

int[] arr={1,7,6,3};
for (int i=0;i<arr.length;i++) {
    int min=i;
    for (int j=i+1;j<arr.length;j++ ) {
        if (arr[j]<arr[min]) {
            min=j;
        }
    }
    if (i!=min) {//若找到的最小值位置不在固定的i位置上，
        int temp=arr[i];//将其放到要排序的位置i上
        arr[i]=arr[min];
        arr[min]=temp;
    }
}
           

【3_ 插入排序】：

int[] arr={1,7,6,3};
for (int i=1;i<arr.length;i++) {
    int temp=arr[i];
    int j=i;
    while(j>0&&temp<arr[j-1]){
        arr[j]=arr[j-1];
        j--;
    }
    arr[j]=temp;
}