常用演算法
一、時間複雜度和空間複雜度
演算法是指用來操作數據。解決程式問題的一組方法。對於同一個問題，使用不同的演算法，也許最終得到的結果是一樣的，但是過程匯總消耗的資源和時間卻會由很大的區別。
主要從演算法所佔用的【時間】和【空間】兩個緯度去考量演算法的優劣
時間緯度：是指執行當前演算法所消耗的時間，通常用【時間複雜度】來描述
空間緯度：是指執行當前演算法需要佔用多少記憶體空間，通常用【空間複雜度】來描述
時間複雜度
通用的方法為【大O符號表示法】，即T(n)=O(f(n))，其中f(n)表示每行程式碼執行次數之和，而O 表示正比例關係，這個公式全稱為：演算法的漸進時間複雜度。
常見的時間複雜度量級有：
- 常數階O(1)
- 對數階O(logN)
- 線性階O(n)
- 線性對數階O(nlogN)
- 平方階O(n²)
- 立方階O(n³)
- K次方階O(n^k)
- 指數階(2^n)
空間複雜度
既然時間複雜度不是用來計算程式具體耗時的，那麼，空間複雜度也不是用來計算實際佔用的空間的。
空間複雜度是對一個演算法在運行過程中臨時佔用存儲空間大小的一個量度，同樣反應的是一個趨勢，用S(n)來定義
空間複雜度比較常用的有：O(1)、O(n)、O(n²)
二、二分查找法
根據傳值查詢在數組中的索引
思路：
1、二分查找（又稱折半查找），即不斷將有序數組進行對半分割
2、每次拿中間位置的數和要查找的數進行比較
3、如果要查找的數小於中間數，則辨明要查找的數在數組的前半段
4、如果要查找的數大於中間數，則表明要查找的數在後半段
5、如果要查找的數等於中間數，則返回中間數
條件：
二分查找要求必須採用順序存儲結構，必須按關鍵字大小有序排列
實現：
public class binarySearch{
public static int binarySearch(long value,long[]arr){
int size =arr.length;
int left=0;
int right=size-1;
while(left<=right){
int middle=left+((right-left)>>1);
if(arr[middle]>value){
right=middle-1;
}else if(arr[middle]<value){
left=middle+1;
}else{
return middle;
}
}
return -1;
}
public static void main(String[] args) {
long []arr={1,4,6,9,12,15};
int result=binarySearch(6, arr);
System.err.println(result); //2
}
}
三、冒泡排序（交換排序）
思路：
1、在要排序的一組數中，對當前還未排好序的範圍內的全部數，自上而下對相鄰的兩個數一次進行比較和調整
2、較大的數往下沉，較小的往上冒
即：每當兩相鄰的數比較後發現他們的排序與拍訊要求相反時，就將他們互換
public class bubbleSort {
/**
* 時間複雜度：平均情況和最差情況都是O(n^2)
* 空間複雜度：o(1)
*/
public static void bubbleSort(long[]arr){
long temp;
for(int i=0;i<arr.length-1;i++){
for(int j=arr.length-1;j>i;j--){
if(arr[j]<arr[j-1]){
temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}
}
}
}
public static void main(String[] args) {
long[]arr={12,34,2,3,63,78,3,6,79,23};
bubbleSort(arr);
System.err.println(Arrays.toString(arr)); //[2, 3, 3, 6, 12, 23, 34, 63, 78, 79]
}
}
四、快速排序（交換排序）
思路：
1、選取主元（以下選取數組開頭為主元）
2、小於等於主元的放左邊，大於主元的放右邊
3、分別對左右遞歸，即重複1、2。
圖解：
1、以數組[49,38,65,97,76,13,27,49]為例，選擇第一個元素49位基準
2、初始化關鍵字：[49,38,65,97,76,13,27,49]
public class quickSort {
public static void quickSort(long arr[], int left, int right) {
int i = left;
int j = right;
long base = arr[left];
while (i <= j) {
while (arr[i] < base) {
i++;
}
while (arr[j] > base) {
j--;
}
if (i <= j) {
long temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
if (left < j) {
quickSort(arr, left, j);
}
if (i < right) {
quickSort(arr, i, right);
}
}
public static void main(String[] args) {
long[] arr = { 49, 38, 65, 97, 76, 13, 27, 49 };
quickSort(arr, 0, arr.length - 1);
System.err.println(Arrays.toString(arr)); //[13, 27, 38, 49, 49, 65, 76, 97]
}
}
五、直接插入排序
思路：
1、在要排序的一組數組中，假設前面（n-1)[n>=2]個數已經是排好序的（局部排序）
2、現在要把第n個數插到前面的有序數中，是的這n個數也是正好排好順序的。
3、如此反覆循環，知道全部排好順序
在插入排序中，一組數據僅僅是局部有序的，而冒泡排序和選擇排序，一組數據項在某個時刻是完全有序的
public class insertSort {
public static void insertSort(long[]arr,int left,int right){
long temp;
int j;
for(int i=left+1;i<right;i++){
temp=arr[i];
j=i-1;
while(j>=left&& arr[j]>temp){
arr[j+1]=arr[j--];
}
arr[j+1]=temp;
}
}
public static void main(String[] args) {
long[]arr={4,3,6,2,9,1};
insertSort(arr, 0, arr.length-1);
System.err.println(Arrays.toString(arr));
}
}
六、shell
shell排序時基於插入排序，並且添加了一些新特性，從而大大提高了插入排序的執行效率
插入排序的缺陷：
多次移動
假如一個很小的數據在靠右端位置上，那麼要將該數據排序到正確的位置上，則所有的中間數據都要向有移動一位
shell排序的優點：
shell排序通過加大插入排序中元素與元素之間的間隔，並且對這些間隔的元素進行插入排序，從而使得數據可以大幅度的移動。當完成該間隔的排序後，shell排序會減少數據間的間隔再進行排序，依次進行下去。shell排序也稱為最小增量排序。
思想：
1、先將要排序的一組數按某個增量d（n/2，n為要排序的個數）根偉若干個組
2、每個組中記錄的下標相差d，對每組中全部元素進行直接插入排序
3、然後再用一個較小的增量（d/2）對它進行分組，在每組中進行直接插入排序
4、當增量減到1是，進行直接插入排序後，排序完成
5、間隔的計算：間隔h的初始值為1.通過h=3*h+1來循環計算，知道間隔大於數組的大小事停止
6、間隔的減少：通過公式h=（h-1）/3來計算
圖解：
以長度10的數組{26,53,67,48,57,13,48,32,60,50}為例，步長序列為{5,2,1}
public class ShellSort {
public static void shellSort(int []arr){
int len=arr.length;
int h=1;
while(h<len/3){
h=h*3+1; //4
}
while(h>0){
for(int i=h;i<len;i+=h){
if(arr[i]<arr[i-h]){
int temp=arr[i];
int j=i-h;
while(j>=0&& arr[j]>temp){
arr[j+h]=arr[j];
j-=h;
}
arr[j+h]=temp;
}
}
h=(h-1)/3;
}
}
public static void shellSort2(int [] arr){
int n=arr.length;
for(int gap=n>>1;gap>0;gap>>=1){
for(int i=gap;i<n;i++){
int temp=arr[i];
int j=i-gap;
while(j>=0&&arr[j]>temp){
arr[j+gap]=arr[j];
j-=gap;
}
arr[j+gap]=temp;
}
}
}
public static void main(String[] args) {
int []arr={ 4, 3, 6, 2, 1, 9, 5, 8, 7};
//shellSort(arr);
shellSort2(arr);
System.err.println(Arrays.toString(arr));
}
}
七、直接選擇排序
思想：
1、要在排序的一組數中，選出最小的一個數以第一個位置的數交換
2、然後再剩下的數當中中在找到最小的與第二個位置的數交換
3、如此循環到倒數第二個數和最後一個數比較為止
與冒泡排序相比，選擇排序將必要的交換次數從O(n*n)減少到O(N)，但是比較次數仍保持為O(N*N)。
圖解：
public class SelectSort {
public static void selectSort(long[]arr){
long temp;
for(int i=0;i<arr.length;i++){
int k=i;
for(int j=i+1;j<arr.length;j++){
if(arr[j]<arr[k]){
k=j;
}
}
temp=arr[i];
arr[i]=arr[k];
arr[k]=temp;
}
}
public static void main(String[] args) {
long[]arr={4,3,6,37,1,58,6,89,23};
selectSort(arr);
System.err.println(Arrays.toString(arr));
}
}
八、歸併排序
歸併排序演算法是目前所有排序演算法中，平均時間複雜度較好O(nlgn)，演算法穩定性較好的一種排序演算法。它的核心演算法思路將大的問題分解成多個小的問題，並將結果進行合併
思想：
歸併排序是將一個序列劃分為同樣大小的兩個子序列，然後對兩個序列分別進行排序，最後進行合併操作，將兩個子序列合成有序的序列。在合成的過程中，一般的實現都需要開闢一塊玉原序列大小形同的空間，已進行合併操作，所以我們需要最大O(N)的輔助空間用於存儲合併序列。
1、整個演算法的拆分階段，是將未排序的數字集合，從一個較大的集合遞歸拆分成若干較小的集合，這些較小的集合要麼包含最多兩個元素，要麼就認為不夠小需要繼續進行拆分。
2、那麼對於一個集合中元素的排序問題就變成兩個問題：較小集合最多兩個元素的大小排序；如何將兩個有序集合合併成一個新的有序集合。
3、第二個問題只需要將兩個集合約時進行一次遍歷即可完成。比較當前集合中最小的元素，將最小元素放入新的集合，它的時間複雜度為O(N)。
實現：
1、申請空間，時期大小為兩個已經排序序列之和，該空間用來存放合併後的序列
2、設置兩個指針，最初位置分別為兩個已經排序序列的其實位置
3、比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指針到下一個位置
4、重複步驟3知道某一指針到達序列尾
5、將另一個序列剩下的所有元素直接複製到合併序列尾
public class MergeSort {
public static void mergeSort(long []arr,int low,int hight){
int mid=(low+hight)/2;
if(low<hight){
//左邊
mergeSort(arr, low, mid);
//右邊
mergeSort(arr, mid+1, hight);
//左右歸併
merge(arr, low, mid, hight);
}
}
public static void merge(long[]arr,int low,int mid,int hight){
long[]temp=new long[hight-low+1];
int i=low;//左指針
int j=mid+1;//右指針
int k=0;
//把較小的數先移到新數組
while(i<=mid&&j<=hight){
if(arr[i]<arr[j]){
temp[k++]=arr[i++];
}else{
temp[k++]=arr[j++];
}
}
//把左邊剩餘的數移入數組
while(i<=mid){
temp[k++]=arr[i++];
}
//把右邊剩餘的數組移入數組
while(j<=hight){
temp[k++]=arr[j++];
}
//把temp數組中的數覆蓋arr數組
for(int k2=0;k2<temp.length;k2++){
arr[k2+low]=temp[k2];
}
}
public static void main(String[] args) {
long[]arr={4,3,6,2,9,1};
mergeSort(arr, 0, arr.length-1);
System.err.println(Arrays.toString(arr));
}
}
