一、歸併排序 Merge Sort

1.1、實現原理

• 如果要排序一個數組，我們先把數組從中間分成前後兩部分，然後對前後兩部分分別排序，再將排好序的兩部分合併在一起，這樣整個數組就都有序了。
• 歸併排序使用的就是分治思想。分治，顧名思義，就是分而治之，將一個大問題分解成小的子問題來解決。小的子問題解決了，大問題也就解決了。
• 分治思想跟遞歸思想很像。分治算法一般都是用遞歸來實現的。 分治是一種解決問題的處理思想，遞歸是一種編程技巧，這兩者並不衝突。

• 寫遞歸代碼的技巧就是，分析得出遞推公式，然後找到終止條件，最後將遞推公式翻譯成遞歸代碼。所以，要想寫出歸併排序的代碼，我們先寫出歸併排序的遞推公式。
• 遞推公式：erge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
• 終止條件：p >= r 不用再繼續分解
• merge_sort(p…r)表示，給下標從 p 到 r 之間的數組排序。
• 我們將這個排序問題轉化為了兩個子問題， merge_sort(p…q) 和 merge_sort(q+1…r)，其中下標 q 等於 p 和 r 的中間位置，也就是 (p+r)/2。
• 當下標從 p 到 q 和從 q+1 到 r 這兩個子數組都排好序之後，我們再將兩個有序的子數組合併在一起，這樣下標從 p 到 r 之間的數據就也排好序了。
• 實現思路如下：

/**
 * 歸併排序
 * @param arr 排序數據
 * @param n   數組大小
 */
public static void merge_sort(int[] arr, int n) {
    merge_sort_c(arr, 0, n - 1);
}

// 遞歸調用函數
public static void merge_sort_c(int[] arr, int p, int r) {
    // 遞歸終止條件
    if (p >= r) {
        return;
    }
    // 取p到r之間的中間位置q
    int q = (p + r) / 2;

    // 分治遞歸
    merge_sort_c(arr, p, q);
    merge_sort_c(arr, q + 1, r);
    // 將 arr[p...q] 和 arr[q+1...r] 合併為 arr[p...r]
    merge(arr[p...r],arr[p...q],arr[q + 1...r]);
}

• merge(arr[p…r], arr[p…q], arr[q + 1…r]) 這個函數的作用就是，將已經有序的 arr[p…q] 和 arr[q+1…r] 合併成一個有序的數組，並且放入 arr[p…r]。
• 如下圖所示，我們申請一個臨時數組 tmp，大小與 arr[p…r] 相同。
• 我們用兩個游標 i 和 j，分別指向 arr[p…q] 和 arr[q+1…r] 的第一個元素。
• 比較這兩個元素 arr[i] 和 arr[j]，如果 arr[i] <= arr[j]，我們就把 arr[i] 放入到臨時數組 tmp，並且 i 后移一位，否則將 arr[j] 放入到數組 tmp，j 后移一位。
• 繼續上述比較過程，直到其中一個子數組中的所有數據都放入臨時數組中，再把另一個數組中的數據依次加入到臨時數組的末尾，這個時候，臨時數組中存儲的就是兩個子數組合併之後的結果了。
• 最後再把臨時數組 tmp 中的數據拷貝到原數組 arr[p…r] 中。

/**
 * merge 合併函數
 * @param arr 數組
 * @param p   數組頭
 * @param q   數組中間位置
 * @param r   數組尾
 */
public static void merge(int[] arr, int p, int q, int r) {
    if (r <= p) return;

    // 初始化變量i j k
    int i = p;
    int j = q + 1;
    int k = 0;

    // 申請一個大小跟A[p...r]一樣的臨時數組
    int[] tmp = new int[r - p + 1];

    // 比較排序移動到臨時數組
    while ((i <= q) && (j <= r)) {
        if (arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }

    // 判斷哪個子數組中有剩餘的數據
    int start = i, end = q;
    if (j <= r) {
        start = j;
        end = r;
    }

    // 將剩餘的數據拷貝到臨時數組tmp
    while (start <= end) {
        tmp[k++] = arr[start++];
    }

    // 將tmp中的數組拷貝回 arr[p...r]
    for (int a = 0; a <= r - p; a++) {
        arr[p + a] = tmp[a];
    }
}

1.2、性能分析

• 歸併排序穩不穩定關鍵要看 merge() 函數，也就是兩個有序子數組合併成一個有序數組的那部分代碼。
• 在合併的過程中，如果 arr[p…q] 和 arr[q+1…r] 之間有值相同的元素，那我們可以像偽代碼中那樣，先把 arr[p…q] 中的元素放入 tmp 數組。
• 這樣就保證了值相同的元素，在合併前後的先後順序不變。所以，歸併排序是一個穩定的排序算法。
• 其時間複雜度是非常穩定的，不管是最好情況、最壞情況，還是平均情況，時間複雜度都是 O(nlogn)。
• 歸併排序的合併函數，在合併兩個有序數組為一個有序數組時，需要藉助額外的存儲空間。
• 儘管每次合併操作都需要申請額外的內存空間，但在合併完成之後，臨時開闢的內存空間就被釋放掉了。在任意時刻，CPU 只會有一個函數在執行，也就只會有一個臨時的內存空間在使用。
• 臨時內存空間最大也不會超過 n 個數據的大小，所以空間複雜度是 O(n)，不是原地排序算法。

二、快速排序 Quicksort

2.1、實現原理

• 快排的思想是：如果要排序數組中下標從 p 到 r 之間的一組數據，可以選擇 p 到 r 之間的任意一個數據作為 pivot（分區點）。
• 遍歷 p 到 r 之間的數據，將小於 pivot 的放到左邊，將大於 pivot 的放到右邊，將 pivot 放到中間。
• 經過這一步驟之後，數組 p 到 r 之間的數據就被分成了三個部分，前面 p 到 q-1 之間都是小於 pivot 的，中間是 pivot，後面的 q+1 到 r 之間是大於 pivot 的。

• 根據分治、遞歸的處理思想，可以用遞歸排序下標從 p 到 q-1 之間的數據和下標從 q+1 到 r 之間的數據，直到區間縮小為 1，就說明所有的數據都有序了。
• 用遞推公式來將上面的過程寫出來的話，就是這樣：quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)。
• 終止條件：p >= r

/**
 * 快速排序
 * @param arr 排序數組
 * @param p 數組頭
 * @param r 數組尾
 */
public static void quickSort(int[] arr, int p, int r) {
    if (p >= r) 
        return;
    // 獲取分區點 並移動數據
    int q = partition(arr, p, r);
    quickSort(arr, p, q - 1);
    quickSort(arr, q + 1, r);
}

partition() 分區函數：

• 是隨機選擇一個元素作為 pivot（一般情況下，可以選擇 p 到 r 區間的最後一個元素），然後對 arr[p…r] 分區，並將小於 pivot 的放右邊，大於的放左邊，函數返回 pivot 的下標。

partition() 的實現有兩種方式：

• 一種是不考慮空間消耗，此時非常簡單。

  • 申請兩個臨時數組 X 和 Y，遍歷 arr[p…r]，將小於 pivot 的元素都拷貝到臨時數組 X，將大於 pivot 的元素都拷貝到臨時數組 Y，最後再將數組 X 和數組 Y 中數據順序拷貝到arr[p…r]。

  /**
   * 分區函數方式一
   *
   * @param arr 數組
   * @param p   上標
   * @param r   下標
   * @return 函數返回 pivot 的下標
   */
  public static int partition1(int[] arr, int p, int r) {
      int[] xArr = new int[r - p + 1];
      int x = 0;
  
      int[] yArr = new int[r - p + 1];
      int y = 0;
  
      int pivot = arr[r];
  
      // 將小於 pivot 的元素都拷貝到臨時數組 X，將大於 pivot 的元素都拷貝到臨時數組 Y
      for (int i = p; i < r; i++) {
          // 小於 pivot 的存入 xArr 數組
          if (arr[i] < pivot) {
              xArr[x++] = arr[i];
          }
          // 大於 pivot 的存入 yArr 數組
          if (arr[i] > pivot) {
              yArr[y++] = arr[i];
          }
      }
  
      int q = x + p;
      // 再將數組 X 和數組 Y 中數據順序拷貝到 arr[p…r]
      for (int i = 0; i < x; i++) {
          arr[p + i] = xArr[i];
      }
      arr[q] = pivot;
      for (int i = 0; i < y; i++) {
          arr[q + 1 + i] = yArr[i];
      }
  
      return q;
  }
  

• 另外一種有點類似選擇排序。

  • 我們通過游標 i 把 arr[p…r-1] 分成兩部分。arr[p…i-1] 的元素都是小於 pivot 的，我們暫且叫它“已處理區間”，arr[i…r-1] 是“未處理區間”。
  • 我們每次都從未處理的區間 arr[i…r-1] 中取一個元素 arr[j]，與 pivot 對比，如果小於 pivot，則將其加入到已處理區間的尾部，也就是 arr[i]的位置。
  • 在數組某個位置插入元素，需要搬移數據，非常耗時。此時可以採用交換，在 O(1) 的時間複雜度內完成插入操作。需要將 arr[i] 與 arr[j] 交換，就可以在 O(1)時間複雜度內將 arr[j] 放到下標為 i 的位置。

  /**
   * 分區函數方式二
   * @param arr 數組
   * @param p   上標
   * @param r   下標
   * @return 函數返回pivot的下標
   */
  public static int partition2(int[] arr, int p, int r) {
      int pivot = arr[r];
      int i = p;
      for (int j = p; j < r; j++) {
          if (arr[j] < pivot) {
              if (i == j) {
                  ++i;
              } else {
                  int tmp = arr[i];
                  arr[i++] = arr[j];
                  arr[j] = tmp;
              }
          }
      }
      int tmp = arr[i];
      arr[i] = arr[r];
      arr[r] = tmp;
      return i;
  }
  

2.2、性能分析

• 因為分區的過程涉及交換操作，如果數組中有兩個相同的元素，比如序列 6， 8， 7， 6， 3， 5， 9， 4，在經過第一次分區操作之後，兩個 6 的相對先後順序就會改變。所以，快速排序並不是穩定的排序算法。
• 按照上面的第二種分區方式，快速排序只涉及交換操作，所以空間複雜度為 Q(1)，是原地排序算法。
• 時間複雜度為 Q(nlogn)，最差為Q(n²)。

三、兩者對比

	歸併排序	快速排序
排序思想	處理過程由下到上，先處理子問題，然後在合併	由上到下，先分區，在處理子問題
穩定性	是	否
空間複雜度	Q(n)	Q(1) 原地排序算法
時間複雜度	都為 O(nlogn)	平均為 O(nlogn)，最差為 O(n²)

• 歸併之所以是非原地排序算法，主要原因是合併函數無法在原地執行。快速排序通過設計巧妙的原地分區函數，可以實現原地排序，解決了歸併排序佔用太多內存的問題。
• 歸併排序算法是一種在任何情況下時間複雜度都比較穩定的排序算法，這也使它存在致命的缺點，即歸併排序不是原地排序算法，空間複雜度比較高，是 O(n)。正因為此，它也沒有快排應用廣泛。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※想知道最厲害的網頁設計公司"嚨底家"!

※別再煩惱如何寫文案,掌握八大原則!

※產品缺大量曝光嗎?你需要的是一流包裝設計!

※回頭車貨運收費標準

※台中搬家公司費用怎麼算?

ThreadLocal概述

ThreadLocal是線程變量，ThreadLocal中填充的變量屬於當前線程，該變量對其他線程而言是隔離的。ThreadLocal為變量在每個線程中都創建了一個副本，那麼每個線程可以訪問自己內部的副本變量。

它具有3個特性：

1. 線程併發：在多線程併發場景下使用。
2. 傳遞數據：可以通過ThreadLocal在同一線程，不同組件中傳遞公共變量。
3. 線程隔離：每個線程變量都是獨立的，不會相互影響。

在不使用ThreadLocal的情況下，變量不隔離，得到的結果具有隨機性。

public class Demo {
    private String variable;

    public String getVariable() {
        return variable;
    }

    public void setVariable(String variable) {
        this.variable = variable;
    }

    public static void main(String[] args) {
        Demo demo = new Demo();
        for (int i = 0; i < 5; i++) {
            new Thread(()->{
                demo.setVariable(Thread.currentThread().getName());
                System.out.println(Thread.currentThread().getName()+" "+demo.getVariable());
            }).start();
        }
    }
}

輸出結果：

Thread-2 Thread-2
Thread-4 Thread-4
Thread-1 Thread-2
Thread-0 Thread-2
Thread-3 Thread-3

View Code

在不使用ThreadLocal的情況下，變量隔離，每個線程有自己專屬的本地變量variable，線程綁定了自己的variable，只對自己綁定的變量進行讀寫操作。

public class Demo {
    private ThreadLocal<String> variable = new ThreadLocal<>();

    public String getVariable() {
        return variable.get();
    }

    public void setVariable(String variable) {
        this.variable.set(variable);
    }

    public static void main(String[] args) {
        Demo demo = new Demo();
        for (int i = 0; i < 5; i++) {
            new Thread(()->{
                demo.setVariable(Thread.currentThread().getName());
                System.out.println(Thread.currentThread().getName()+" "+demo.getVariable());
            }).start();
        }
    }
}

輸出結果：

Thread-0 Thread-0
Thread-1 Thread-1
Thread-2 Thread-2
Thread-3 Thread-3
Thread-4 Thread-4

View Code

synchronized和ThreadLocal的比較

上述需求，通過synchronized加鎖同樣也能實現。但是加鎖對性能和併發性有一定的影響，線程訪問變量只能排隊等候依次操作。TreadLocal不加鎖，多個線程可以併發對變量進行操作。

public class Demo {
    private String variable;
    public String getVariable() {
        return variable;
    }

    public void setVariable(String variable) {
        this.variable = variable;
    }

    public static void main(String[] args) {
        Demo demo = new Demo1();
        for (int i = 0; i < 5; i++) {
            new Thread(()->{
                synchronized (Demo.class){
                    demo.setVariable(Thread.currentThread().getName());
                    System.out.println(Thread.currentThread().getName()+" "+demo.getVariable());
                }
            }).start();
        }
    }
}

ThreadLocal和synchronized都是用於處理多線程併發訪問資源的問題。ThreadLocal是以空間換時間的思路，每個線程都擁有一份變量的拷貝，從而實現變量隔離，互相不干擾。關注的重點是線程之間數據的相互隔離關係。synchronized是以時間換空間的思路，只提供一個變量，線程只能通過排隊訪問。關注的是線程之間訪問資源的同步性。ThreadLocal可以帶來更好的併發性，在多線程、高併發的環境中更為合適一些。

ThreadLocal使用場景

轉賬事務的例子

JDBC對於事務原子性的控制可以通過setAutoCommit(false)設置為事務手動提交，成功后commit，失敗后rollback。在多線程的場景下，在service層開啟事務時用的connection和在dao層訪問數據庫的connection應該要保持一致，所以併發時，線程只能隔離操作自已的connection。

解決方案1：service層的connection對象作為參數傳遞給dao層使用，事務操作放在同步代碼塊中。

存在問題：傳參提高了代碼的耦合程度，加鎖降低了程序的性能。

解決方案2：當需要獲取connection對象的時候，通過ThreadLocal對象的get方法直接獲取當前線程綁定的連接對象使用，如果連接對象是空的，則去連接池獲取連接，並通過ThreadLocal對象的set方法綁定到當前線程。使用完之後調用ThreadLocal對象的remove方法解綁連接對象。

ThreadLocal的優勢：

1. 可以方便地傳遞數據：保存每個線程綁定的數據，需要的時候可以直接獲取，避免了傳參帶來的耦合。
2. 可以保持線程間隔離：數據的隔離在併發的情況下也能保持一致性，避免了同步的性能損失。

ThreadLocal的原理

每個ThreadLocal維護一個ThreadLocalMap，Map的Key是ThreadLocal實例本身，value是要存儲的值。

每個線程內部都有一個ThreadLocalMap，Map裏面存放的是ThreadLocal對象和線程的變量副本。Thread內部的Map通過ThreadLocal對象來維護，向map獲取和設置變量副本的值。不同的線程，每次獲取變量值時，只能獲取自己對象的副本的值。實現了線程之間的數據隔離。

JDK1.8的設計相比於之前的設計（通過ThreadMap維護了多個線程和線程變量的對應關係，key是Thread對象，value是線程變量）的好處在於，每個Map存儲的Entry數量變少了，線程越多鍵值對越多。現在的鍵值對的數量是由ThreadLocal的數量決定的，一般情況下ThreadLocal的數量少於線程的數量，而且並不是每個線程都需要創建ThreadLocal變量。當Thread銷毀時，ThreadLocal也會隨之銷毀，減少了內存的使用，之前的方案中線程銷毀后，ThreadLocalMap仍然存在。

ThreadLocal源碼解析

set方法

首先獲取線程，然後獲取線程的Map。如果Map不為空則將當前ThreadLocal的引用作為key設置到Map中。如果Map為空，則創建一個Map並設置初始值。

get方法

首先獲取當前線程，然後獲取Map。如果Map不為空，則Map根據ThreadLocal的引用來獲取Entry，如果Entry不為空，則獲取到value值，返回。如果Map為空或者Entry為空，則初始化並獲取初始值value，然後用ThreadLocal引用和value作為key和value創建一個新的Map。

 

remove方法

刪除當前線程中保存的ThreadLocal對應的實體entry。

initialValue方法

該方法的第一次調用發生在當線程通過get方法訪問線程的ThreadLocal值時。除非線程先調用了set方法，在這種情況下，initialValue才不會被這個線程調用。每個線程最多調用依次這個方法。

該方法只返回一個null，如果想要線程變量有初始值需要通過子類繼承ThreadLocal的方式去重寫此方法，通常可以通過匿名內部類的方式實現。這個方法是protected修飾的，是為了讓子類覆蓋而設計的。

ThreadLocalMap源碼分析

ThreadLocalMap是ThreadLocal的靜態內部類，沒有實現Map接口，獨立實現了Map的功能，內部的Entry也是獨立實現的。

與HashMap類似，初始容量默認是16，初始容量必須是2的整數冪。通過Entry類的數據table存放數據。size是存放的數量，threshold是擴容閾值。

 Entry繼承自WeakReference，key是弱引用，其目的是將ThreadLocal對象的生命周期和線程生命周期解綁。

弱引用和內存泄漏

內存溢出：沒有足夠的內存供申請者提供

內存泄漏：程序中已動態分配的堆內存由於某種原因程序未釋放或無法釋放，造成系統內存的浪費，導致程序運行速度減慢甚至系統崩潰等驗證后溝。內存泄漏的堆積會導致內存溢出。

弱引用：垃圾回收器一旦發現了弱引用的對象，不管內存是否足夠，都會回收它的內存。

內存泄漏的根源是ThreadLocalMap和Thread的生命周期是一樣長的。

如果在ThreadLocalMap的key使用強引用還是無法完全避免內存泄漏，ThreadLocal使用完后，ThreadLocal Reference被回收，但是Map的Entry強引用了ThreadLocal，ThreadLocal就無法被回收，因為強引用鏈的存在，Entry無法被回收，最後會內存泄漏。

在實際情況中，ThreadLocalMap中使用的key為ThreadLocal的弱引用，value是強引用。如果ThreadLocal沒有被外部強引用的話，在垃圾回收的時候，key會被清理，value不會。這樣ThreadLocalMap就出現了為null的Entry。如果不做任何措施，value永遠不會被GC回收，就會產生內存泄漏。

ThreadLocalMap中考慮到這個情況，在set、get、remove操作后，會清理掉key為null的記錄（將value也置為null）。使用完ThreadLocal后最後手動調用remove方法（刪除Entry）。

也就是說，使用完ThreadLocal后，線程仍然運行，如果忘記調用remove方法，弱引用比強引用可以多一層保障，弱引用的ThreadLocal會被回收，對應的value會在下一次ThreadLocalMap調用get、set、remove方法的時候被清除，從而避免了內存泄漏。

Hash衝突的解決

ThreadLocalMap的構造方法

構造函數創建一個長隊為16的Entry數組，然後計算firstKey的索引，存儲到table中，設置size和threshold。

firstKey.threadLocalHashCode & (INITIAL_CAPACITY-1)用來計算索引，nextHashCode是Atomicinteger類型的，Atomicinteger類是提供原子操作的Integer類，通過線程安全的方式來加減，適合高併發使用。

每次在當前值上加上一個HASH_INCREMENT值，這個值和斐波拉契數列有關，主要目的是為了讓哈希碼可以均勻的分佈在2的n次方的數組裡，從而盡量的避免衝突。

當size為2的冪次的時候，hashCode & (size – 1)相當於取模運算hashCode % size，位運算比取模更高效一些。為了使用這種取模運算， 所有size必須是2的冪次。這樣一來，在保證索引不越界的情況下，減少衝突的次數。

ThreadLocalMap的set方法

ThreadLocalMao使用了線性探測法來解決衝突。線性探測法探測下一個地址，找到空的地址則插入，若整個空間都沒有空餘地址，則產生溢出。例如：長度為8的數組中，當前key的hash值是6，6的位置已經被佔用了，則hash值加一，尋找7的位置，7的位置也被佔用了，回到0的位置。直到可以插入為止，可以將這個數組看成一個環形數組。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※別再煩惱如何寫文案,掌握八大原則!

※教你寫出一流的銷售文案?

※超省錢租車方案

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※產品缺大量曝光嗎?你需要的是一流包裝設計!

※回頭車貨運收費標準