一、時間復雜度和空間復雜度
演算法是指用來操作資料，解決程式問題的一組方法，對于同一個問題，使用不同的演算法，也許最終得到的結果是一樣的，但是程序匯總消耗的資源和時間卻會由很大的區別，
主要從演算法所占用的【時間】和【空間】兩個緯度去考量演算法的優劣
時間緯度：是指執行當前演算法所消耗的時間，通常用【時間復雜度】來描述
空間緯度：是指執行當前演算法需要占用多少記憶體空間，通常用【空間復雜度】來描述
時間復雜度
通用的方法為【大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));
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/10049.html
標籤：Java
上一篇：SpringCloud系列之Nacos+Dubbo應用篇
下一篇：word檔案轉pdf解決修訂問題