數據結構與演算法

1.概述

1.1什麼是數據結構

數據結構就是把數據元素按照一定的關係組織起來的集合，用來組織和儲存數據
數據結構 = 元素 + 元素的關係

1.2數據結構的分類（元素的關係）

數據結構可以分爲邏輯結構和物理結構兩大類

1.2.1邏輯結構分類

使用數據元素之間的邏輯關係經行分類，主要可一分爲線性結構、與非線性結構。

線性結構
- 數據結構作爲最常用的數據結構，其特點是數據元素之間存在一對一的線性關係
- 線性結構右兩種不同的儲存結構，即順序儲存結構何鏈式儲存結構，順序儲存的線性表稱爲順序表，順序表中儲存元素是連續的（主要是地址連續）
- 鏈式儲存的線性表稱爲鏈表，鏈表中的儲存元素不一定是連續的，元素節點中存放數據元素以及相鄰元素的地址資訊
線性結構常見的有：陣列、佇列、列表何棧。
線性結構特徵：
- 集閤中必存在唯一的一個「第一個元素」；
- 集閤中必存在唯一的一個」最後的元素「；
- 除最後元素之外，其它數據元素均有唯一的」後繼「；
- 除第一元素之外，其它數據元素均有唯一的」前驅「。
非線性結構

非線性結構中各個數據元素不再保持在一個線性序列中，每個數據元素可能與零個或者多個其他數據元素髮生聯繫。根據關係的不同，可分爲層次結構和羣結構。

非線性結構包括：二維陣列，多維陣列，廣義表，樹結構，圖結構

1.2.2再具體經行分類

主要有線性結構、集合、樹形、圖狀。

集合：集合結構中數據除了屬於同一個集合外，他們之間沒有任何的關係。
線性結構：數據元素中存在一對一的關係
樹形結構：數據元素存在一對多的關係
圖形結構：數據元素存在多對多的關係。

1.2.3物理結構分類

邏輯節後再計算機中真正的表達方式（又成爲映像）稱爲物理結構。

數據元素的儲存結構形式有兩種:**順序儲存**和**鏈式儲存**

順序結構

順序儲存結構:是把數據元素存放在地址連續的儲存單元裡，其數據間的邏輯關係和物理關係是一致的，像生活中的排隊。我們可以通過索引來找到數據元素。

如果就是這麼簡單和有規律，一切就好辦了。可實際上，總會有人插隊，也會有人要上廁所、有人會放棄排隊。所以這個隊伍當中會新增新成員，也有可能會去掉老元素，整個結構時刻都處於變化中。顯然，面對這樣時常要變化的結構，順序儲存是不科學的。那怎麼辦呢? 此時就出現了我們的鏈式儲存結構。
鏈式儲存結構

鏈式儲存結構把數據元素存放在任意的儲存單元裡，這組儲存單元可以是連續的，也可以是不連續的。數據元素的儲存關係並不能反映其邏輯關係，因此需要用一個指針存放數據元素的地址，這樣通過地址就可以找到相關聯數據元素的位置。

1.3什麼是演算法

演算法就是：解決問題的方法和步驟

衡量演算法有如下標準:

時間複雜度：程式要執行的次數，並非執行時間
空間複雜度：演算法執行過程中大概要佔用的最大記憶體
難易程度(可讀性)
健壯性

1.3.1生活中的演算法

再生活中你遇到某個問題有多個解決方案。

比如從a到b你可以選擇飛機、汽車、步行等。不同的方案帶來的成本也是不同的，坐飛機花費金錢最多，單所用時間最短。步行花費金錢最少，使用時間最長。

在程式中，我們也可以使用不同的演算法解決相同的問題，而不同的演算法成本也是不同的，而優秀的演算法追求兩個目標：

花最少的時間完成需求
佔用最少的空間完成需求

2.演算法分析

演算法的目的就是爲了在花費少的時間，佔用少的記憶體完成需求。那麼花費少的時間我們稱爲時間複雜度分析，佔用少的記憶體叫做空間複雜度分析。

通常，對於一個給定的演算法，我們要做兩項分析。第一是從數學上證明演算法的正確性，這一步主要用到形式化證明的方法及相關推理模式，如回圈不變式、數學歸納法等。而在證明演算法是正確的基礎上，第二部就是分析演算法的時間複雜度。演算法的時間複雜度反映了程式執行時間隨輸入規模增長而增長的量級，在很大程度上能很好反映出演算法的優劣與否。因此，作爲程式設計師，掌握基本的演算法時間複雜度分析方法是很有必要的。

2.1時間複雜度分析

演算法執行時間需通過依據該演算法編制編製的程式在計算機上執行時所消耗的時間來度量。而度量一個程式的執行時間通常有兩種方法。

2.1.1事後分析法

在給定編譯好的演算法，通過測試程式執行來經行時間的比較

這種方法可行，但不是一個好的方法。該方法有兩個缺陷：

一是要想對設計的演算法的執行效能進行評測，必須先依據演算法編制編製相應的程式並實際執行；
二是所得時間的統計量依賴於計算機的硬體、軟體等環境因素，有時容易掩蓋演算法本身的優勢。

通過一個簡單的例子來說明

   public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int sum =0;
        int n = 100;
        for (int i = 0; i <= n; i++) {
            sum+=i;
        }

        System.out.println("sum:"+sum);
        long end = System.currentTimeMillis();
        System.out.println("所花費的時間"+(end-start));
    }

這是一個最簡單的程式，當我們有大量的程式程式碼，我們編寫測試的程式也是需要花費大量的時間。如果這個演算法很垃圾，那麼之前的做的測試等事就白做了

2.1.2事前分析法

因事後統計方法更多的依賴於計算機的硬體、軟體等環境因素，有時容易掩蓋演算法本身的優劣。因此人們常常採用事前分析估算的方法。

在編寫程式前，依據統計方法對演算法進行估算。一個用高階語言編寫的程式在計算機上執行時所消耗的時間取決於下列因素：

演算法採用的策略、方法；
編譯產生的程式碼品質；
問題的輸入規模；
機器執行指令的速度。

如果演算法固定，那麼演算法的執行時間就只和輸入規模有關係了。

一個演算法是由控制結構（順序、分支和回圈3種）和原操作（指固有數據型別的操作）構成的，則演算法時間取決於兩者的綜合效果。爲了便於比較同一個問題的不同演算法，通常的做法是，從演算法中選取一種對於所研究的問題（或演算法型別）來說是基本操作的原操作，以該基本操作的重複執行的次數作爲演算法的時間量度。

通過一個簡單的例子來說明

第一種

使用者輸入量n=1時，則計算需要一次
使用者輸入量n=100時，則計算需要一百次    
public static void main(String[] args) {
    int sum =0;   //執行1次
    int n = 100;  //執行1次
    for (int i = 0; i <= n; i++) {  //執行n+1次
        sum+=i;  //執行n次
    }
    System.out.println("sum:"+sum);

}

第二種

使用者輸入量n=1時，則計算需要一次
使用者輸入量n=100時，則計算需要一次    
public static void main(String[] args) {
    int sum =0;   //執行1次
    int n = 100;  //執行1次
	sum = (n+1)*n/2;
    System.out.println("sum:"+sum);

}

如果我們把第一種演算法的回圈體看作時一個整體，忽略結束判斷，那麼這個兩個演算法執行時間的差距就是n和1的差距。

在我們分析一個演算法的執行時間，最重要的就是把核心操作次數和輸入規模關聯起來。

[外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-Lz63E9C9-1597399150633)(C:/Users/84411/Desktop/學習筆記/學習筆記-數據演算法與結構/imgs/01.png)]

2.1.3函數漸進增長

概念：給定兩個函數f(n)和g(n) ,如果存在一個整數N,使其對於所有的n>N,f(n)總是比g(n) 大，那麼說明f(n)的增長漸進塊於g(n).

例：上面的f(n)=n^2>f(n)=n.

注意點：

隨着數據規模的增大，演算法的常數操作可以忽略不計。
隨着數據規模的增大，與最高次項相乘的常數可以忽略。
最高此項的指數大的，隨着n的增長會變得特別塊

2.1.4時間複雜度

時間頻度一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機執行測試才能纔能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱爲語句頻度或時間頻度。記爲T(n)。
時間複雜度在剛纔提到的時間頻度中，n稱爲問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律。爲此，我們引入時間複雜度概念。一般情況下，演算法中基本操作重複執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近於無窮大時，T(n)/f(n)的極限值爲不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 爲演算法的漸進時間複雜度，簡稱時間複雜度。
執行次數=執行時間

2.2空間複雜度分析

是指執行當前演算法需要佔用多少記憶體空間，我們通常用「空間複雜度」來描述。

2.排序

在我們的程式中，排序是非常常見的一種。我一些數據按照不同的規則來進行排序，如商品價格、訂單等

2.1 Comparable介面

Comparable 是排序介面。

若一個類實現了Comparable介面，就意味着「該類支援排序」。即然實現Comparable介面的類支援排序，假設現在存在「實現Comparable介面的類的物件的List列表(或陣列)」，則該List列表(或陣列)可以通過 Collections.sort（或 Arrays.sort）進行排序。

此外，「實現Comparable介面的類的物件」可以用作「有序對映(如TreeMap)」中的鍵或「有序集合(TreeSet)」中的元素，而不需要指定比較器。

我們可以點進Comparable 介面，可以看到只有一個方法。

package java.lang;
import java.util.*;

public interface Comparable<T> {

    public int compareTo(T o);
}

例子：

根據Student 物件的年齡進行排序

import lombok.Data;

@Data
public class Student implements Comparable<Student> {

 private String name;
 private int age;

 public int compareTo(Student o) {
     return this.age-o.age;
 }
}

class StudentTest {

 public static void main(String[] args) {
     Student student1 = new Student();
     student1.setName("張三");
     student1.setAge(18);
     Student student2 = new Student();
     student2.setName("王五");
     student2.setAge(20);
     Comparable max = getMax(student1, student2);
     System.out.println(max);
 }

 public static Comparable getMax(Comparable o1, Comparable o2){

     int i = o1.compareTo(o2);
     /**
        *  如果i>0  則o1>02
        *  如果i<0  則o1<02
        *  如果i=0  則o1=02
        */

       if (i>0){
           return o1;
       }else {
           return o2;
       }
   }
}

2.2 Comparator介面

Comparator 是比較器介面。

我們若需要控制某個類的次序，而該類本身不支援排序(即沒有實現Comparable介面)；那麼，我們可以建立一個「該類的比較器」來進行排序。這個「比較器」只需要實現Comparator介面即可。

也就是說，我們可以通過「實現Comparator類來新建一個比較器」，然後通過該比較器對類進行排序。

我們可以點進Comparator介面：

package java.util;

public interface Comparator<T> {

    int compare(T o1, T o2);

    boolean equals(Object obj);
}

若一個類要實現Comparator介面：它一定要實現compareTo(T o1, T o2) 函數，但可以不實現 equals(Object obj) 函數。

爲什麼可以不實現 equals(Object obj) 函數呢？因爲任何類，預設都是已經實現了equals(Object obj)的。 Java中的一切類都是繼承於java.lang.Object，在Object.java中實現了equals(Object obj)函數；所以，其它所有的類也相當於都實現了該函數。
int compare(T o1, T o2) 是「比較o1和o2的大小」。返回「負數」，意味着「o1比o2小」；返回「零」，意味着「o1等於o2」；返回「正數」，意味着「o1大於o2」。

區別：

Comparable是排序介面；若一個類實現了Comparable介面，就意味着「該類支援排序」。
而Comparator是比較器；我們若需要控制某個類的次序，可以建立一個「該類的比較器」來進行排序。

2.3簡單排序

2.3.1氣泡排序

排序原理：
- 比較相鄰的元素。如果前一個比後一個元素大，則這兩個交換位置。
- 對每一對相鄰的元素做同樣的工作，從開始第一對到元素。最終的位置就式最大值。

冒泡次數	冒泡結果
初始狀態	6 4 5 3 2 1
1次冒泡	4 5 3 2 1 6
2次冒泡	4 3 2 1 5 6
3次冒泡	3 2 1 4 5 6
4次冒泡	2 1 3 4 5 6
5次冒泡	1 2 3 4 5 6
6次冒泡	1 2 3 4 5 6

實現：

實現簡單的陣列排序

import java.util.Arrays;

public class BubbleA {
    public static void main(String[] args) {
        int[] arr ={5,2,6,4};

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

    }

    public static  void  sort(int[] arr){
        int temp;

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

Api實現

比較元素大小方法：greater()
位置交換:exch()
排序 :sort()

import java.util.Comparator;

public class BubbleB {
    /**
     * 對數據進行排序
     */
    public static void sort(Comparable[] a){
        for (int i = a.length - 1; i > 0 ; i--) {
            for (int j = 0; j < i; j++) {

                if (greater(a[j],a[j+1])) exch(a,j,j+1);

            }
        }
    }

    public static boolean greater(Comparable m ,Comparable n ){
        return m.compareTo(n)>0;
    }

    public static void exch(Comparable[] a, int i, int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

}

    public static void main(String[] args) {
        Integer[] arr = { 1 ,5, 10,6,5};
        BubbleB.sort(arr);

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

2.3.2氣泡排序的演算法分析

氣泡排序使用了雙層for回圈，其中內層回圈體中的程式碼是真正完成排序的，所以我們分析氣泡排序的時間複雜度，主要分析一下內層回圈體的執行次數即可。

最壞情況就是倒序：

例：

元素比較次數：（n-1）+ (n-2) + (n-3)…+2+1 = ((n-1)+1)*(n-1)/2=n^2/2-n/2;

元素的交換次數：（n-1）+(n-2)+(n-3)…+2+1 = ((n-1)+1)*(n-1)/2=n^2/2-n/2;

總執行次數：（n^{2/2-n/2）+（n}2/2-n/2） = n^2-n

按照大O推到法則，保留函數中的最高階項那麼最終氣泡排序的時間複雜度爲O(n^2);

2.3.3選擇排序

是一種簡單直觀的排序演算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

選擇排序的主要優點與數據移動有關。如果某個元素位於正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬於非常好的一種。

實現：

package 數據結構與演算法.排序.選擇排序;

import java.util.Arrays;

public class SelectionA {


 public static void sort(Comparable[] a){

     int n =  a.length - 2;

     for (int i = 0; i <= n; i++) {
         //定義一個變數，記錄最小元素的位置
         int min = i ;

         for (int j = i+1; j < a.length; j++)  if (greater(a[min],a[j])) min = j;

         //交換最小元素索引 min 處的值和j索引i處的值
         exch(a,i,min);

         }


 }


 public static boolean greater(Comparable v, Comparable w) {
     return v.compareTo(w) > 0;
 }

 public static void exch(Comparable[] a, int i, int j) {
     Comparable t = a[i];
     a[i] = a[j];
     a[j] = t;
 }


 public static void main(String[] args) {
     Integer[] arr = { 1 ,5, 10,6,5};

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

 }
}

平均時間複雜度	О(n²)
最壞時間複雜度	О(n²)
最優時間複雜度	О(n²)
空間複雜度	總共О(n)，需要輔助空間O(1)

2.3.4插入排序

插入排序（英語：Insertion Sort）是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常採用in-place排序，因而在從後向前掃描過程中，需要反覆反復把已排序元素逐步向後挪位，爲最新元素提供插入空間。

Insertion Sort 和打撲克牌時，從牌桌上逐一拿起撲克牌，在手上排序的過程相同。

舉例：

Input: {5 2 4 6 1 3}。

首先拿起第一張牌, 手上有 {5}。

拿起第二張牌 2, 把 2 insert 到手上的牌 {5}, 得到 {2 5}。

拿起第三張牌 4, 把 4 insert 到手上的牌 {2 5}, 得到 {2 4 5}。

以此類推。

實現：

從第一個元素開始，該元素可以認爲已經被排序

取出下一個元素，在已經排序的元素序列中從後向前掃描

如果該元素（已排序）大於新元素，將該元素移到下一位置

重複步驟3，直到找到已排序的元素小於或者等於新元素的位置

將新元素插入到該位置後

重複步驟2~5

可以採用二分查詢法來減少「比較操作」的數目，而由於「交換操作」的數目不變，演算法的時間複雜度依舊爲О(n²) 。該演算法可以認爲是插入排序的一個變種，稱爲二分查詢插入排序

實現：

public class Insertion {


 public static void sort(Comparable[] a){
     for (int i =  1; i < a.length ; i++) {

         for (int j = i; j >= 0; j--) {
             //比較索引j處的值和索引j-1處的值，如果索引j-1處的值大 則交換數據，如果不大，那麼找到合適的位置 ，退出回圈。
             if (greater(a[j-1],a[j])) exch(a,j-1,j);
             else break;
             
         }
     }
 }

 public static boolean greater(Comparable m ,Comparable n ){
     return m.compareTo(n)>0;
 }

 public static void exch(Comparable[] a, int i, int j){
     Comparable temp;
     temp = a[i];
     a[i] = a[j];
     a[j] = temp;
 }
}

平均時間複雜度	О(n²)
最壞時間複雜度	О(n²)
最優時間複雜度	О(n²)
空間複雜度	總共О(n)，需要輔助空間O(1)

2.4高階排序

2.4.1希爾排序

希爾排序（Shellsort），也稱遞減增量排序演算法，是插入排序的一種更高效的改進版本。希爾排序是非穩定排序演算法。

希爾排序是基於插入排序的以下兩點性質而提出改進方法的：

插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率
但插入排序一般來說是低效的，因爲插入排序每次只能將數據移動一位

實現原理：

選定一個增長量h ,按照h的長度對數據經行分組。

對分組的每一組元素經行插入排序

減少增長量，最少減爲1，重複第二部操作。

列：陣列{20，10，5，6，4，8} h = 3

次數數據增長量

0 20，10，5，6，4，8 h=3

1 6 , 4 , 5, 20, 10, 8 h=3

2 5， 4， 6，8，10，20 h=2

3 4，5，6，8，10，20 h=1

次數	數據	增長量
0	20，10，5，6，4，8	h=3
1	6 , 4 , 5, 20, 10, 8	h=3
2	5， 4， 6，8，10，20	h=2
3	4，5，6，8，10，20	h=1

增長量規則

public class ShellH {
    /**
     * 增長量的規則
     */

    public static void main(String[] args) {
        int[] arr={20,10,5,6,4,8};
        int h = 1;
        while (h<arr.length/2){   // h < 陣列長度/2 
            h=2*h+1;
        }
        System.out.println(h);
    }
    /**
     *h 減小的規則	
     * 		h=h/2
     */

}

實現：
public static void shellSort(int[] arr) {
     int length = arr.length;
     int temp;
     for (int step = length / 2; step >= 1; step /= 2) {
         for (int i = step; i < length; i++) {
             temp = arr[i];
             int j = i - step;
             while (j >= 0 && arr[j] > temp) {
                 arr[j + step] = arr[j];
                 j -= step;
             }
             arr[j + step] = temp;
         }
     }
 }
API設計：
import java.util.Arrays;

public class Shell {

 /**
     * 對陣列經行排序
     * @param a
     */
    public static void sort(Comparable[] a){
        int h =1;
        //1.根據陣列長度確定增長量
        while (h<a.length/2) h=(2*h)+1;

        //希爾排序
        while (h>=1){
            //找到待插入的元素
            for (int i = h; i < a.length; i++) {
                //把待插入的元素插入到有序數列中
                for (int j = i; j >= h; j-=h) {
                    //比較a[j] a[j-h]
                    if (greater(a[j-h],a[j])){
                        //交換
                        exch(a,j,j-h);
                    }else {
                        break;
                    }
                }
            }
            //減小h的值
            h=h/2;

        }

    }

    public static boolean greater(Comparable m ,Comparable n ){
        return m.compareTo(n)>0;
    }

    public static void exch(Comparable[] a, int i, int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        Integer[] arr={20,10,5,6,4,8};

        Shell.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
步長的選擇是希爾排序的重要部分。只要最終步長爲1任何步長序列都可以工作。演算法最開始以一定的步長進行排序。然後會繼續以一定步長進行排序，最終演算法以步長爲1進行排序。當步長爲1時，演算法變爲普通插入排序，這就保證了數據一定會被排序。

Donald Shell最初建議步長選擇爲[外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-v0ybj0oD-1597399150635)(https://wikimedia.org/api/rest_v1/media/math/render/svg/1216d48de276dc45542cb80b1e49037131ec9624)]並且對步長取半直到步長達到1。雖然這樣取可以比[外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-p0tOxefz-1597399150637)(https://wikimedia.org/api/rest_v1/media/math/render/svg/4441d9689c0e6b2c47994e2f587ac5378faeefba)]類的演算法（插入排序）更好，但這樣仍然有減少平均時間和最差時間的餘地。

步長序列最壞情況下複雜度

[外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-N2yznafl-1597399150639)(https://wikimedia.org/api/rest_v1/media/math/render/svg/6c8f4d868de17325e948844f4e4fc58fc0b0393a)] [外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-o6DjdUpg-1597399150640)(https://wikimedia.org/api/rest_v1/media/math/render/svg/d6ae2ed4058fb748a183d9ada8aea50a00d0c89f)][外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-bSLjrSVa-1597399150642)(https://wikimedia.org/api/rest_v1/media/math/render/svg/52376d02d45e1ac7c4cd8d8208c2f4ae104e3098)]

[外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-kiswvY8P-1597399150643)(https://wikimedia.org/api/rest_v1/media/math/render/svg/76af5b5bc7d056faef7eef0c6efeea3a16adc156)] [外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-8lLIMsyR-1597399150644)(https://wikimedia.org/api/rest_v1/media/math/render/svg/d6ae2ed4058fb748a183d9ada8aea50a00d0c89f)][外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-b5EEPZDU-1597399150644)(https://wikimedia.org/api/rest_v1/media/math/render/svg/0d30640651e80d1f38232384fdf407b253670801)]

[外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-x8IbzlKe-1597399150645)(https://wikimedia.org/api/rest_v1/media/math/render/svg/f2f4f16513454e80cf1f92f279d81914a8ee1e45)] [外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-uSHFug8H-1597399150645)(https://wikimedia.org/api/rest_v1/media/math/render/svg/d6ae2ed4058fb748a183d9ada8aea50a00d0c89f)][外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-0pAi1Xlm-1597399150646)(https://wikimedia.org/api/rest_v1/media/math/render/svg/de727f8c182ebfc7dd8fe3ac86b2b15ec5dd6d5d)]

步長序列	最壞情況下複雜度
[外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-N2yznafl-1597399150639)(https://wikimedia.org/api/rest_v1/media/math/render/svg/6c8f4d868de17325e948844f4e4fc58fc0b0393a)]	[外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-o6DjdUpg-1597399150640)(https://wikimedia.org/api/rest_v1/media/math/render/svg/d6ae2ed4058fb748a183d9ada8aea50a00d0c89f)][外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-bSLjrSVa-1597399150642)(https://wikimedia.org/api/rest_v1/media/math/render/svg/52376d02d45e1ac7c4cd8d8208c2f4ae104e3098)]
[外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-kiswvY8P-1597399150643)(https://wikimedia.org/api/rest_v1/media/math/render/svg/76af5b5bc7d056faef7eef0c6efeea3a16adc156)]	[外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-8lLIMsyR-1597399150644)(https://wikimedia.org/api/rest_v1/media/math/render/svg/d6ae2ed4058fb748a183d9ada8aea50a00d0c89f)][外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-b5EEPZDU-1597399150644)(https://wikimedia.org/api/rest_v1/media/math/render/svg/0d30640651e80d1f38232384fdf407b253670801)]
[外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-x8IbzlKe-1597399150645)(https://wikimedia.org/api/rest_v1/media/math/render/svg/f2f4f16513454e80cf1f92f279d81914a8ee1e45)]	[外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-uSHFug8H-1597399150645)(https://wikimedia.org/api/rest_v1/media/math/render/svg/d6ae2ed4058fb748a183d9ada8aea50a00d0c89f)][外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-0pAi1Xlm-1597399150646)(https://wikimedia.org/api/rest_v1/media/math/render/svg/de727f8c182ebfc7dd8fe3ac86b2b15ec5dd6d5d)]

2.4.2歸併排序

遞回：自己呼叫自己
歸併排序

歸併排序是建立在歸併操作上的一種有效的排序演算法，1945年由約翰·馮·諾伊曼首次提出。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞回可以同時進行。
採用分治法:
- 分割：遞回地把當前序列平均分割成兩半。
- 整合：在保持元素順序的同時將上一步得到的子序列整合到一起（歸併）。
排序原理
1. 儘可能的把一組數據拆分成兩個相等的子組，並對每一個子組再經行拆分，直到子組元素個數爲1；
2. 將相鄰的兩個子組經行合併成一個有序的大組
3. 不斷的重複2直到只有一個組爲止；

實現：

import java.util.Arrays;

/**
 *  歸併排序
 */
public class Merge {

    //輔助陣列
    private static Comparable[] assist;


    /**
     *  對陣列a經行排序
     * @param a
     */
    public static void sort(Comparable[] a){
        //1.初始化輔助陣列
        assist = new Comparable[a.length];
        //2.定義一個lo變數，hi變數，分別記錄陣列中最小索引和最大索引
        int lo = 0;
        int hi = a.length - 1;
        //呼叫sort過載的方法 完成 lo 到 hi 的排序
        sort(a,lo,hi);

    }

    /**
     * 對陣列a中 lo 到 hi 進行排序
     * @param a
     * @param lo
     * @param hi
     */
    public static void sort(Comparable[] a,int lo , int hi){
        if (hi<=lo) return;

        //分組 分兩組
        int mid = lo+(hi-lo)/2;

        //對每一組數據經行排序
        sort(a,lo,mid);
        sort(a,mid+1,hi);

        //歸併
        merge(a,lo,mid,hi);
    }


    /**
     * 對數據進行歸併
     * @param a
     * @param lo
     * @param mid
     * @param hi
     */
    public static  void merge(Comparable[] a, int lo ,int mid, int hi){
        //定義三個指針
        int i = lo;
        int p1 = lo;
        int p2 = mid+1;

        //遍歷 ，移動p1指針和p2指針，比較索引處的值，找出小的那個 ，放到輔助陣列索引的處
        while (p1<=mid && p2<=hi){
            if (less(a[p1],a[p2])){
                assist[i++] = a[p1++];
            }else {
                assist[i++] = a[p2++];
            }
        }

        //遍歷， 如果p1處的指針沒有走完，那麼順序移動到p1指針,把對應的元素放到輔助陣列的對應索引處
        while (p1<=mid) assist[i++] = a[p1++];

        //遍歷， 如果p2處的指針沒有走完，那麼順序移動到p2指針,把對應的元素放到輔助陣列的對應索引處
        while (p2<=hi) assist[i++] = a[p2++];

        //copy輔助陣列

        for (int index = 0; index <= hi ; index++) {
            a[index] = assist[index];
        }

    }


    public static boolean less(Comparable v ,Comparable w ){
        return v.compareTo(w)<0;
    }

    public static void exch(Comparable[] a, int i, int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    
}

2.4.3快速排序

快速排序由於排序效率在同爲O(N*logN)的幾種排序方法中效率較高，因此經常被採用，再加上快速排序思想----分治法也確實實用，因此很多軟體公司的筆試面試，包括像騰訊，微軟等知名IT公司都喜歡考這個，還有大大小的程式方面的考試如軟考，考研中也常常出現快速排序的身影。

總的說來，要直接默寫出快速排序還是有一定難度的，因爲本人就自己的理解對快速排序作了下白話解釋，希望對大家理解有幫助，達到快速排序，快速搞定。

快速排序是C.R.A.Hoare於1962年提出的一種劃分交換排序。它採用了一種分治的策略，通常稱其爲分治法(Divide-and-ConquerMethod)。

該方法的基本思想是：

1．先從數列中取出一個數作爲基準數。
2．分割區過程，將比這個數大的數全放到它的右邊，小於或等於它的數全放到它的左邊。
3．再對左右區間重複第二步，直到各區間只有一個數。

實現：

import java.util.Comparator;

public class Quick {

 public static void sort(Comparable[] a){
     int lo = 0 ;
     int hi = a.length-1;
     sort(a,lo,hi);

 }


 public static void sort(Comparable[] a,int lo , int hi){
     if (hi<=lo) return;

     int partition = partition(a, lo, hi);

     sort(a,lo,partition-1);

     sort(a,partition+1,hi);

 }



 //對陣列a中，從索引hi之間的元素進行排序 並返回分組對應的索引
 public static  int partition(Comparable[] a, int lo , int hi){

     Comparable  key = a[lo];

     int left = lo;
     int right = hi+1;

     while (true){
         while (less(key,a[--right])){
             if (right==lo) break;
         }

     while (less(a[++left],key)){
         if (left==hi) break;
     }

     if (left>=right) break;
     else exch(a,left,right);

     }
     exch(a,lo,right);
     return right;
 }


 public static boolean less(Comparable v ,Comparable w ){
     return v.compareTo(w)<0;
 }

 public static void exch(Comparable[] a, int i, int j){
     Comparable temp;
     temp = a[i];
     a[i] = a[j];
     a[j] = temp;
 }



}

i);

 sort(a,lo,partition-1);

 sort(a,partition+1,hi);
}

//對陣列a中，從索引hi之間的元素進行排序並返回分組對應的索引
public static int partition(Comparable[] a, int lo , int hi){
 Comparable  key = a[lo];

 int left = lo;
 int right = hi+1;

 while (true){
     while (less(key,a[--right])){
         if (right==lo) break;
     }

 while (less(a[++left],key)){
     if (left==hi) break;
 }

 if (left>=right) break;
 else exch(a,left,right);

 }
 exch(a,lo,right);
 return right;
}

public static boolean less(Comparable v ,Comparable w ){
return v.compareTo(w)<0;
}

public static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}

}

數據結構與演算法入門與排序

文章目錄

數據結構與演算法

1.概述

1.1什麼是數據結構

1.2數據結構的分類（元素的關係）

1.2.1邏輯結構分類

線性結構

非線性結構

1.2.2再具體經行分類

1.2.3物理結構分類

1.3什麼是演算法

1.3.1生活中的演算法

2.演算法分析

2.1時間複雜度分析

2.1.1事後分析法

2.1.2事前分析法

2.1.3函數漸進增長

2.1.4時間複雜度

2.2空間複雜度分析

2.排序

2.1 Comparable介面

2.2 Comparator介面

2.3簡單排序

2.3.1氣泡排序

2.3.2氣泡排序的演算法分析

2.3.3選擇排序

2.3.4插入排序

2.4高階排序

2.4.1希爾排序

2.4.2歸併排序

2.4.3快速排序

數據結構與演算法 入門 與 排序

文章目錄

數據結構與演算法

1.概述

1.1什麼是數據結構

1.2數據結構的分類（元素的關係）

1.2.1邏輯結構分類

線性結構

非線性結構

1.2.2再具體經行分類

1.2.3物理結構分類

1.3什麼是演算法

1.3.1生活中的演算法

2.演算法分析

2.1時間複雜度分析

2.1.1事後分析法

2.1.2事前分析法

2.1.3函數漸進增長

2.1.4時間複雜度

2.2空間複雜度分析

2.排序

2.1 Comparable介面

2.2 Comparator介面

2.3簡單排序

2.3.1氣泡排序

2.3.2氣泡排序的演算法分析

2.3.3選擇排序

2.3.4插入排序

2.4高階排序

2.4.1希爾排序

2.4.2歸併排序

2.4.3快速排序

數據結構與演算法入門與排序