算法

算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述,是一系列解決問(wèn)題的清晰指令,算法代表著用系統(tǒng)的方法描述解決問(wèn)題的策略機(jī)制.
也就是說(shuō),能夠?qū)σ欢ㄒ?guī)范的輸入,在有限時(shí)間內(nèi)獲得所要求的輸出.
如果一個(gè)算法有缺陷,或不適合于某個(gè)問(wèn)題,執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問(wèn)題.
不同的算法可能用不同的時(shí)間、空間或效率來(lái)完成同樣的任務(wù).
一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度于時(shí)間復(fù)雜度來(lái)衡量
----維基百科

插入排序

有一個(gè)已經(jīng)有序的數(shù)據(jù)序列，要求在這個(gè)已經(jīng)排好的數(shù)據(jù)序列中插入一個(gè)數(shù)
但要求插入后此數(shù)據(jù)序列仍然有序，這個(gè)時(shí)候就要用到一種新的排序方法——插入排序法
插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中
從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序
時(shí)間復(fù)雜度為 O(n^2)。是穩(wěn)定的排序方法。插入算法把要排序的數(shù)組分成兩部分：
第一部分包含了這個(gè)數(shù)組的所有元素，但將最后一個(gè)元素除外（讓數(shù)組多一個(gè)空間才有插入的位置），
而第二部分就只包含這一個(gè)元素（即待插入元素）。
在第一部分排序完成后，再將這個(gè)最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：每步將一個(gè)待排序的記錄
按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當(dāng)位置上，直到全部插入完為止。

排序過(guò)程步驟:

1. 從第一個(gè)元素開(kāi)始, 該元素可以認(rèn)為已經(jīng)被排序
2. 取出下一個(gè)元素, 在已經(jīng)排序的元素序列中從后向前掃描
3. 如果該元素(已排序)大于新元素,將該元素移到下一位置
4. 重復(fù)步驟3, 直到找到已排序的元素小于或者等于新元素的位置
5. 將新元素插入到該位置后
6. 重復(fù)步驟2~5

示例代碼:

import java.util.Arrays;

public class InsertSort {
    public static void sort(int[] arr) {
        int temp;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                //對(duì)已經(jīng)排序好的元素比較，找到一個(gè)比插入元素大的元素 交換位置
                if (arr[i] < arr[j]) {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] ints = {5, 3, 4, 1, 2};
        sort(ints);
        System.out.println(Arrays.toString(ints));
    }
}

冒泡排序

冒泡排序（Bubble Sort），是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡(jiǎn)單的排序算法。 它重復(fù)地走訪過(guò)要排序的元素列
依次比較兩個(gè)相鄰的元素，如果他們的順序（如從大到小、首字母從 A 到 Z）錯(cuò)誤就把他們交換過(guò)來(lái)
走訪元素的工作是重復(fù)地進(jìn)行直到?jīng)]有相鄰元素需要交換，也就是說(shuō)該元素已經(jīng)排序完成-
這個(gè)算法的名字由來(lái)是因?yàn)樵酱蟮脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會(huì)上浮到頂端一樣
故名“冒泡排序”。

冒泡排序的運(yùn)行過(guò)程如下:

• 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
• 對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。
• 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
• 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較

示例代碼:

import java.util.Arrays;

public class BubbleSort {
    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                //如果當(dāng)前元素比后一位元素大 交換位置
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] ints = {5, 3, 4, 1, 2};
        sort(ints);
        System.out.println(Arrays.toString(ints));
    }
}

歸并排序

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法
該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用
將已有序的子序列合并，得到完全有序的序列；
即先使每個(gè)子序列有序，再使子序列段間有序。
若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。

排序過(guò)程:

1. 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列
2. 設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
3. 比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
4. 重復(fù)步驟 3 直到某一指針到達(dá)序列尾
5. 將另一序列剩下的所有元素直接復(fù)制到合并序列尾

import java.util.Arrays;

public class MergeSort {

    public static void mergeSort(int[] arrays, int left, int right) {
//        如果數(shù)組還可以拆分
        if (left < right) {
            //數(shù)組的中間位置
            int middle = (left + right) / 2;
            //拆分左邊數(shù)組
            mergeSort(arrays, left, middle);
            //拆分右邊數(shù)組
            mergeSort(arrays, middle + 1, right);
            //合并
            merge(arrays, left, middle, right);

        }
    }


    /**
     * 合并數(shù)組
     */
    public static void merge(int[] arr, int left, int middle, int right) {
        //申請(qǐng)合并空間 大小為兩個(gè)已經(jīng)排序序列之和
        int[] temp = new int[right - left + 1];
        //i 和 j為兩個(gè)已經(jīng)排好序的數(shù)組的起始位置
        int i = left;
        int j = middle + 1;
        int k = 0;
        //排序
        while (i <= middle && j <= right) {
            //將比較小的數(shù)組放入合并空間
            if (arr[i] < arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        //將左邊剩余元素寫(xiě)入合并空間
        while (i <= middle) {
            temp[k++] = arr[i++];
        }
        //將右邊剩余的元素寫(xiě)入合并空間
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        //將排序后的數(shù)組寫(xiě)回原來(lái)的數(shù)組
        for (int l = 0; l < temp.length; l++) {
            arr[l + left] = temp[l];
        }

    }

    public static void main(String[] args) {
        int[] ints = {5, 3, 4, 1, 2};
        mergeSort(ints,0,ints.length-1);
        System.out.println(Arrays.toString(ints));
    }
}

快速排序

快速排序（英語(yǔ)：Quicksort），又稱劃分交換排序（partition-exchange sort），簡(jiǎn)稱快排
一種排序算法，最早由東尼·霍爾提出。在平均狀況下，排序 n 個(gè)項(xiàng)目要 O(nlogn) 次比較
。在最壞狀況下則需要 O(n^2) 次比較，但這種狀況并不常見(jiàn)
。事實(shí)上，快速排序 O(nlogn)通常明顯比其他算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地達(dá)成。

快速排序使用分治法(Divide and conquer) 策略來(lái)吧一個(gè)序列(List)分為兩個(gè)子序列(sub-lists)

步驟如下 :

1. 從數(shù)列中挑出一個(gè)元素，稱為“基準(zhǔn)”（pivot），
2. 重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任何一邊）。在這個(gè)分割結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分割（partition）操作。
3. 遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

遞歸到最底部時(shí)，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。這個(gè)算法一定會(huì)結(jié)束，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。

示例代碼:

import java.util.Arrays;

public class QuickSort {
    public static void sort(int[] arr, int head, int tail) {
        if (head >= tail || arr == null || arr.length <= 1) {
            return;
        }
        //設(shè)置數(shù)組的起始位置 i 結(jié)束位置j 基準(zhǔn) pivot 為數(shù)組的中間
        int i = head, j = tail, pivot = arr[(head + tail) / 2];
        while (i <= j) {
            //當(dāng)數(shù)組小于基準(zhǔn) 循環(huán)結(jié)束后 相當(dāng)于i所處的位置的值為大于基準(zhǔn)的元素
            while (arr[i] < pivot) {
                ++i;
            }
            //當(dāng)數(shù)組大于基準(zhǔn) 循環(huán)結(jié)束后 相當(dāng)于j所處的位置的值為小于于基準(zhǔn)的元素
            while (arr[j] > pivot) {
                --j;
            }
            //如果i<j 那么則將交互i j對(duì)應(yīng)位置的值
            if (i < j) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                //將指針繼續(xù)移動(dòng)
                ++i;
                --j;
            } else if (i == j) {
//如果i=j 那么說(shuō)明本次排序已經(jīng)結(jié)束 將i++ 如果這里不使用i++ 那么后面的sort(arr,i,tail)將改為arr(arr,i+1,tail)
                ++i;
            }
        }
        //繼續(xù)將數(shù)組分割  
        sort(arr, head, j);
        sort(arr, i, tail);
    }

    public static void main(String[] args) {
        int[] ints = {5, 3, 4, 1, 2};
        sort(ints, 0, ints.length - 1);
        System.out.println(Arrays.toString(ints));
    }
}

搜索算法

線性搜索或順序搜索是一種尋找某一特定值的搜索算法，指按一定的順序檢查數(shù)組中每一個(gè)元素，直到找到所要尋找的特定值為止。是最簡(jiǎn)單的一種搜索算法。

示例代碼:

public class LinearSearch {
    public static void main(String[] args) {
        int[] ints = {5, 3, 4, 1, 2};
        System.out.println(search(ints, 4));
    }

    public static int search(int[] arr, int key) {
        //循環(huán)
        for (int i = 0; i < arr.length; i++) {
            //比較是否等于key
            if (arr[i] == key) {
                return arr[i];
            }
        }
        //找不到就返回-1
        return -1;
    }
}

二分查找

在計(jì)算機(jī)科學(xué)中，二分搜索（英語(yǔ)：binary search），也稱折半搜索（英語(yǔ)：half-interval search）、對(duì)數(shù)搜索（英語(yǔ)：logarithmic search）
是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜索過(guò)程從數(shù)組的中間元素開(kāi)始，如果中間元素正好是要查找的元素，則搜索過(guò)程結(jié)束
如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開(kāi)始一樣從中間元素開(kāi)始比較
如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。

示例代碼:

public class BinarySearch {
    public static int search(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int middle = (high + low) / 2;
            //如果相等 返回值
            if (key == arr[middle]) {
                return key;
            } else if (key < arr[middle]) {
                //如果key小于中間值，那么改變high，值可能在左邊部（比較小的部分）
                high = middle - 1;
            }else {
                //如果key大于中間值，那么改變low，值可能在右邊部（比較大的部分）
                low = middle + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] ints = {1, 2, 3, 4, 5};
        System.out.println(search(ints, 4));
    }
}