盤點幾種常見的java排序算法

Posted on by

1.插入排序

這個打麻將或者打撲克的很好理解, 比如有左手有一副牌1,2,4,7 ,來一張3的牌, 是不是就是手拿著這張牌從右往左插到2,4之間

一次插入排序的操作過程：

將待插元素，依次與已排序好的子數列元素從後到前進行比較，如果當前元素值比待插元素值大，則將移位到與其相鄰的後一個位置，否則直接將待插元素插入當前元素相鄰的後一位置，因為說明已經找到插入點的最終位置

public class InsertSort {

    public static void sort(int[] arr) {
        if (arr.length >= 2) {
            for (int i = 1; i < arr.length; i++) {
                //挖出一個要用來插入的值,同時位置上留下一個可以存新的值的坑
                int x = arr[i];
                int j = i - 1;
                //在前面有一個或連續多個值比x大的時候,一直循環往前面找,將x插入到這串值前面
                while (j >= 0 && arr[j] > x) {
                    //當arr[j]比x大的時候,將j向後移一位,正好填到坑中
                    arr[j + 1] = arr[j];
                    j--;
                }
                //將x插入到最前面
                arr[j + 1] = x;
            }
        }
    }
}

2.分治排序法,快速排序法

簡單的說, 就是設置一個標準值, 將大於這個值的放到右邊(不管排序), 將小於這個值的放到左邊(不管排序), 那麼這樣隻是區分瞭左小右大, 沒有排序, 沒關系, 左右兩邊再重復這個步驟.直到不能分瞭為止.

詳細說就是:

  1. 選擇待排數列的首部第一個元素為基準元素x，設置兩指針，分別指向數列首尾部位置，假設兩指針分別設為i和j。
  2. 每次遍歷的過程是這樣的，首先從右到左遍歷指針j所指向的元素，直到j指向的元素值小於基準元素x時，停止遍歷，將其放到i的位置(因為i的值已經拷貝成瞭基準x騰出瞭位置)
  3. i往右挪一步, i++,接著輪到指針i從左到右遍歷,直到i所指向的元素值大於基準元素x時，停止遍歷，將其放到j的位置(因為上面一步j的值已經占用到瞭i的位置,騰出位置瞭)
  4. 依此類推，兩邊輪流遍歷, 直到指針i與指針j相等或者大於(實際肯定是i==j)時，停止外部循環。此時必定左邊都是比x小的, 右邊是比x大的.
  5. 最後直接將基準元素x直接放置於指針i所指向的位置即可
  6. 完成分區操作, 從i的位置一分為二, 左邊和右邊再遞歸執行上面的操作. 層層細分

接下來，我們通過示圖來展示上述分區算法思路的過程：

public class QuickSort {

    public static void sort(int[] arr,int begin,int end) {
        //先定義兩個參數接收排序起始值和結束值
        int a = begin;
        int b = end;
        //先判斷a是否大於b

        if (a >= b) {
            //沒必要排序
            return;
        }
        //基準數,默認設置為第一個值
        int x = arr[a];

        //循環
        while (a < b) {
            //從後往前找,找到一個比基準數x小的值,賦給arr[a]
            //如果a和b的邏輯正確--a<b ,並且最後一個值arr[b]>x,就一直往下找,直到找到後面的值大於x
            while (a < b && arr[b] >= x) {
                b--;
            }
            //跳出循環,兩種情況,一是a和b的邏輯不對瞭,a>=b,這時候排序結束.二是在後面找到瞭比x小的值
            if (a < b) {
                //將這時候找到的arr[b]放到最前面arr[a]
                arr[a] = arr[b];
                //排序的起始位置後移一位
                a++;
            }

            //從前往後找,找到一個比基準數x大的值,放在最後面arr[b]
            while (a < b && arr[a] <= x) {
                a++;
            }
            if (a < b) {
                arr[b] = arr[a];
                //排序的終止位置前移一位
                b--;
            }
        }
        //跳出循環 a < b的邏輯不成立瞭,a==b重合瞭,此時將x賦值回去arr[a]
        arr[a] = x;
        //調用遞歸函數,再細分再排序
        sort(arr,begin,a-1);
        sort(arr,a+1,end);
    }
}

3.冒泡排序 low版

每次冒泡過程都是從數列的第一個元素開始，然後依次和剩餘的元素進行比較, 跟列隊一樣, 從左到右兩兩相鄰的元素比大小, 高的就和低的換一下位置. 最後最高(值最大)的肯定就排到後面瞭.

但是這隻是把最高的排到後面瞭, 還得找出第二高的, 於是又從第一個開始兩兩比較, 高的往後站, 然後第二高的也到後面瞭.

然後是第三高的再往後排…

public class MaoPao {

    public static void  sort(int[] arr){
        for (int i = 1; i < arr.length; i++) {  //第一層for循環,用來控制冒泡的次數
            for (int j = 0; j < arr.length-1; j++) { //第二層for循環,用來控制冒泡一層層到最後
                //如果前一個數比後一個數大,兩者調換 ,意味著泡泡向上走瞭一層
                if (arr[j] > arr[j+1] ){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}

4.冒泡排序 bigger版

補充, 改進後,看下文的測試結果發現提升並不大, 這是正常的, 因為改進後省略的是排序成功後的判斷步驟, 而就算沒改進, 排序成功後也隻不過是對數組進行遍歷而已, 沒有進行數據更新操作, 而我們知道數組是讀取快更新慢的, 所以和上面的版本相比看起來提升不算大

在這個版本中,改動瞭兩點

  1. 第一點是加入瞭一個佈爾值,判斷第二層循環中的調換有沒有執行,如果沒有進行兩兩調換,說明後面都已經排好序瞭,已經不需要再循環瞭,直接跳出循環,排序結束.
  2. 第二點是第二層循環不再循環到arr.length – 1,因為外面的i循環遞增一次,說明數組最後就多瞭一個排好序的大泡泡.第二層循環也就不需要到最末尾一位瞭,可以提前結束循環
 /**
 * 終極版冒泡排序
 * 加入一個佈爾變量,如果內循環沒有交換值,說明已經排序完成,提前終止
 * @param arr
 */
public static void sortPlus(int[] arr){
    if(arr != null && arr.length > 1){
        for(int i = 0; i < arr.length - 1; i++){
            // 初始化一個佈爾值
            boolean flag = true;
            for(int j = 0; j < arr.length - i - 1 ; j++){
                if(arr[j] > arr[j+1]){
                    // 調換
                    int temp;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    // 改變flag
                    flag = false;
                }
            }
            if(flag){
                break;
            }
        }
    }
}

5.選擇排序

選擇排序也是一種簡單直觀的排序算法，實現原理比較直觀易懂：

首先在未排序數列中找到最小元素，然後將其與數列的首部元素進行交換，然後，在剩餘未排序元素中繼續找出最小元素，將其與已排序數列的末尾位置元素交換。以此類推，直至所有元素圴排序完畢.

同理,可以類比與打撲克和打麻將, 和上面插入排序不同, 插入排序相當於抽一張牌整理好瞭再抽一張, 而選擇排序相當於一次性給你一副亂牌, 然後慢慢整理的感覺.
這也容易理解為什麼選擇排序為啥比插入排序慢瞭. 插入排序是摸一張牌, 然後直接插入到手中已經排好序的牌,再摸下一張牌.
選擇排序相當於在一堆牌中, 不斷的找到最小的牌往前面放.

public static void sort(int[] arr){
    for(int i = 0; i < arr.length - 1 ; i++){
        int min = i; // 遍歷的區間最小的值
        for (int j = i + 1; j < arr.length ;j++){
             if(arr[j] < arr[min]){
                 // 找到當前遍歷區間最小的值的索引
                 min = j;
             }
        }
        if(min != i){
            // 發生瞭調換
            int temp =  arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }
}

6. 歸並排序

歸並排序,簡單的說把一串數

從中平等分為兩份,再把兩份再細分,直到不能細分為止. 這就是分而治之的分的步驟.

再從最小的單元,兩兩合並,合並的規則是將其按從小到大的順序放到一個臨時數組中,再把這個臨時數組替換原數組相應位置,這就是治. 圖解如下:



代碼:

public static void mergeSort(int[] a,int s,int e){
    int m = (s + e) / 2;
    if (s < e){
      mergeSort(a,s,m);
      mergeSort(a,m+1,e);
      //歸並
      merge(a,s,m,e);
    }
  }

  private static void merge(int[] a, int s, int m, int e) {
    //初始化一個從起始s到終止e的一個數組
    int[] temp = new int[(e - s) + 1];
    //左起始指針
    int l = s;
    //右起始指針
    int r = m+1;
    int i = 0;
    //將s-e這段數據在邏輯上一分為二,l-m為一個左邊的數組,r-e為一個右邊的數組,兩邊都是有序的
    //從兩邊的第一個指針開始遍歷,將其中小的那個值放在temp數組中
    while (l <= m && r <= e){
      if (a[l] < a[r]){
        temp[i++] = a[l++];
      }else{
        temp[i++] = a[r++];
      }
    }

    //將兩個數組剩餘的數放到temp中
    while (l <= m){
      temp[i++] = a[l++];
    }
    while (r <= e){
      temp[i++] = a[r++];
    }
    
    //將temp數組覆蓋原數組
    for (int n = 0; n < temp.length; n++) {
      a[s+n] = temp[n];
    }
    
  }

8. 堆排序

堆排序, 顧名思義, 就是將數據以堆的結構, 或者說類似於二叉樹的結構, 每次都整理二叉樹將最大值找到, 然後放到數組末尾. 個人感覺有點像選擇排序.都是每次遍歷選擇一個最大值或最小值
從下往上調整堆, 將最大值放到頂部

  1. 首先我們可以把一個數組, 從上往下, 從左到右依次放置成為二叉樹
  2. 接著我們創建最大頂堆, 就是將最大的值調整到頂部.
  3. 然後我們開始遍歷, 把這個[0]的最大值放到最末尾, 然後再次整理二叉樹, 當然將最後一位排除在外.然後我們將截至末尾的下標往前移一位.
  4. 一直遍歷, 把最大值放到頂部, 再調換到末尾, 到隻剩最後一個元素,
    找到最大值後, 放到數組後面, 並設置一個標記, 表示截止後面的都是已排序的元素, 相當於堆刪除一個元素

因為是樹結構, 所以整理一次樹的時間復雜度是O(logn), 但是又因為它需要遍歷一次挨個整理找到剩下數據中的最大值, 所以它的最壞，最好，平均時間復雜度均為O(nlogn)

踩坑

大傢可以直奔v3.0版本

v1.0 巨慢不能用

這裡說下踩坑, 下面是我寫的堆排序v1.0版本, 寫瞭個簡單的數組測試瞭下發現也沒有問題, ok. 然後我寫一個10w的數組來和冒泡排序, 選擇排序等比較, 結果發現程序像是卡死瞭直接花瞭幾分鐘還沒出結果. 這已經遠遠大於冒泡排序的時間瞭.

/**
   * 最大頂堆排序
   * @param a
   */
  public static void topMaxHeapSort(int[] a){
    //先創建最大頂堆
    createTopMaxHeap(a);
    int end = a.length - 1 ;
    while(end > 0 ){
      //把0位的最大值放到最後
      swaparr(a, 0, end);
      //將計算的長度減一.不考慮最後的那個值
      end--;
      //重新調整堆結構
      handleMaxHeapFromIndex(a, end);
    }
      //打印下看看
      // System.out.println(Arrays.toString(a));
  }

  /** [3,7,1,4,9,5,6,7,2,6,8,3]
   * `````````3
   * ``````/     \
   * `````7       1
   * ````/ \     / \
   * ``4   9   5   6
   * `/ \ / \ /
   * `7 2 6 8 3
   * 變成 [9, 7, 6, 7, 6, 5, 1, 4, 2, 3, 8, 3]
   * `````````9
   * ```````/    \
   * `````7       6
   * ````/ \     / \
   * ``7   6   5   1
   * `/ \ / \ /
   * `4 2 3 8 3
   * 構建最大頂堆, 變成父節點都比子節點大的樹
   * @param a
   */
  public static void createTopMaxHeap(int[] a){
    //從倒數第二排最後一個開始, 從下往上, 層層處理把最大的換上去構建最大頂堆
    //如上面的註釋, 就是從5開始. 再往後就沒意義瞭
      handleMaxHeapFromIndex(a,a.length-1);
    //打印下看看
    // System.out.println(Arrays.toString(a));
  }

  private static void handleMaxHeapFromIndex(int[] a,int end){
    for (int i = end / 2; i>=0; i--) {
      //從i開始往後面調整它的堆
    //左子節點, 右子節點
 
    // 設置一個用於玩下遍歷和判斷的子節點, 默認就是左邊的兒子
    int child = 2 * i + 1;
    while (child <= end){
      //如果右子節點比左邊大
      int leftson = child;
      int rightson = child + 1;
      if(rightson <= end && a[rightson] > a[leftson]){
        //就設置為右邊的兒子
        child++;
      }
      //再比較父子,如果兒子比父親大,就互換
      if(a[i] < a[child]){
        swaparr(a,i,child);
      }
      //繼續循環
      i = child;
      //繼續選擇它的左兒子
      child = 2 * i + 1;
    }
    }
  }

  

  private static void swaparr(int[] arr,int a,int b){
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }

v2.0 太慢不能用

考慮肯定調整堆的代碼有問題

  1. 在初始構建瞭最大頂堆時, 父親都比兒子大
  2. 後面每次都隻移除頂部元素.即變化瞭第一層
  3. 那我在調整的時候, 如果這個節點比兒子節點都大, 那應該下面的都是調整好的不用管.

我選擇在handleMaxHeapFromIndex方法中, 加入瞭break來提前跳出循環, 如下:

 while (child <= end) {
      // 如果右子節點比左邊大
      int leftson = child;
      int rightson = child + 1;
      if (rightson <= end && a[rightson] > a[leftson]) {
        // 就設置為右邊的兒子
        child++;
      }
      // 再比較父子,如果兒子比父親大,就互換
      if (a[i] < a[child]) {
        swaparr(a, i, child);
      } else {
        // 否則直接跳出循環, 隻要父節點比子節點大, 不用管下面的調整瞭
        break;
      }
      // 繼續循環
      i = child;
      // 繼續選擇它的左兒子
      child = 2 * i + 1;
    
  }

再跑一次, 發現還是很慢, 但是比之前好多瞭, 但是還是耗時很久, 這也還是有問題啊…

v3.0

代碼如下:

 /**
   * 最大頂堆排序
   * 
   * @param a
   */
  public static void topMaxHeapSort(int[] a) {
    // 先創建最大頂堆
    createTopMaxHeap(a);
    System.out.println("創建完畢");
    int end = a.length - 1;
    while (end > 0) {
      // 把0位的最大值放到最後
      swaparr(a, 0, end);
      // 將計算的長度減一.不考慮最後的那個值
      end--;
      handleMaxHeapFromIndex(a, 0, end);
    }
    // 打印下看看
    // System.out.println(Arrays.toString(a));
  }

  /** [3,7,1,4,9,5,6,7,2,6,8,3]
   * `````````3
   * ``````/     \
   * `````7       1
   * ````/ \     / \
   * ``4   9   5   6
   * `/ \ / \ /
   * `7 2 6 8 3
   * 變成 [9, 7, 6, 7, 6, 5, 1, 4, 2, 3, 8, 3]
   * `````````9
   * ```````/    \
   * `````7       6
   * ````/ \     / \
   * ``7   6   5   1
   * `/ \ / \ /
   * `4 2 3 8 3
   * 構建最大頂堆, 變成父節點都比子節點大的樹
   * @param a
   */
  public static void createTopMaxHeap(int[] a) {
    // 從倒數第二排最後一個開始, 從下往上, 層層處理把最大的換上去構建最大頂堆
    // 如上面的註釋, 就是從5開始. 再往後就沒意義瞭
    for (int i = (a.length - 1) / 2; i >= 0; i--) {
      handleMaxHeapFromIndex(a, i, a.length - 1);
    }
    // 打印下看看
    // System.out.println(Arrays.toString(a));
  }

  private static void handleMaxHeapFromIndex(int[] a, int i, int end) {
    // 從i開始往後面調整它的堆
    // 左子節點, 右子節點
    // 設置一個用於玩下遍歷和判斷的子節點, 默認就是左邊的兒子
    int child = 2 * i + 1;
    while (child <= end) {
      // 如果右子節點比左邊大
      int leftson = child;
      int rightson = child + 1;
      if (rightson <= end && a[rightson] > a[leftson]) {
        // 就設置為右邊的兒子
        child++;
      }
      // 再比較父子,如果兒子比父親大,就互換
      if (a[i] < a[child]) {
        swaparr(a, i, child);
      } else {
        // 否則直接跳出循環, 隻要父節點比子節點大, 不用管下面的調整瞭
        break;
      }
      // 繼續循環
      i = child;
      // 繼續選擇它的左兒子
      child = 2 * i + 1;
    }
  }

  private static void swaparr(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }

無奈之下參考瞭別人的博客(也有一些寫的是我1.0版本和2.0版本的), 最後發現問題

首先再分析為什麼要分成兩步, 1. 創建大頂堆. 2. 遍歷調整 ?

在創建大頂堆的時候, 是從(a.length-1)/2處從下往上整理, 才能確保最大值能像冒泡一樣跑到頂部

那在構建完瞭大頂堆後, 我們還需不需要重新從這個位置倒排往上整理呢? 其實是不需要的. 因為變化的是第一個元素, 除瞭這個元素以外, 其他的元素經過大頂堆的整理肯定父親比兒子大.

所以後面遍歷調整的時候, 隻需要從0下標開始找最大值就可以瞭. 這樣就可以去掉handleMaxHeapFromIndex外層的那個循環:

private static void handleMaxHeapFromIndex(int[] a,int end){
 for (int i = end / 2; i>=0; i--) { //這個循環隻在創建大頂堆的時候需要, 這個就可以去掉瞭
    ....
     while (child <= end){
     ...
	}
 }

另外一個坑, child<=end這裡要用大於等於號, 以及後面的rightson <= end .因為我就寫著寫著忘記瞭end是最後處理的下標, 而不是數組長度, 習慣性用的<號, 導致最後2個無法排序

9. 其他排序

比如Arrays工具類提供的排序方法。它內部實現也是快速排序

private static void arraysSort(int[] a){
    Arrays.sort(a);
  }

還有就是將數組轉為list,使用集合的排序方法,但是這無異於兜圈子,因為集合底層也是數組

private static void listSort(int[] a){
    List<Integer> integers = Ints.asList(a);
    Collections.sort(integers);
    integers.toArray(new Integer[a.length]);
  }

10. 比較

試瞭一下幾個排序的速度,代碼如下:

public static void main(String[] args) {

    int[] arr = new int[200000];
    int[] a =getRandomArr(arr);
    int[] b = a.clone();
    int[] c = b.clone();
    int[] d = b.clone();
    int[] e = b.clone();
    int[] f = b.clone();
    int[] g = b.clone();
    int[] h = b.clone();

    long s = Clock.systemDefaultZone().millis();
    quickSort(a, 0, a.length - 1);
    System.out.println("quickSort耗時: " + (Clock.systemDefaultZone().millis() - s) + " ms");

    s = Clock.systemDefaultZone().millis();
    mergeSort(b,0,b.length-1);
    System.out.println("mergeSort: " + (Clock.systemDefaultZone().millis() - s) + " ms");

    s = Clock.systemDefaultZone().millis();
    listSort(c);
    System.out.println("listSort耗時: " + (Clock.systemDefaultZone().millis() - s) + " ms");

    s = Clock.systemDefaultZone().millis();
    arraysSort(d);
    System.out.println("arraysSort耗時: " + (Clock.systemDefaultZone().millis() - s) + " ms");

    s = Clock.systemDefaultZone().millis();
    maoPaoSort(e);
    System.out.println("maoPaoSort耗時: " + (Clock.systemDefaultZone().millis() - s) + " ms");

    s = Clock.systemDefaultZone().millis();
    maoPaoSortPlus(f);
    System.out.println("maoPaoSortPlus耗時: " + (Clock.systemDefaultZone().millis() - s) + " ms");

    s = Clock.systemDefaultZone().millis();
    insertSort(g);
    System.out.println("insertSort耗時: " + (Clock.systemDefaultZone().millis() - s) + " ms");

    s = Clock.systemDefaultZone().millis();
    selectSort(h);
    System.out.println("selectSort耗時: " + (Clock.systemDefaultZone().millis() - s) + " ms");



}

/**
   * 獲取一個打亂的數組
   * @param arr
   */
  private static int[] getRandomArr(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
      arr[i] = new Random().nextInt(arr.length);
    }
    return arr;
  }

分別對1k,1w,10w,20w大小的隨機數組排序,結果如下:

得到綜合結果是:

速度: 快速排序>>歸並排序>>>>>插入排序>>選擇排序>>冒泡排序

並且可以看到,選擇排序,冒泡排序在數據量越來越大的情況下,耗時已經呈指數型上漲,而不是倍數上漲,在50w的時候已經需要足足5分鐘以上

//—1k—

quickSort耗時: 0 ms

mergeSort: 1 ms

listSort耗時: 7 ms

arraysSort耗時: 1 ms

maoPaoSort耗時: 3 ms

maoPaoSortPlus耗時: 4 ms

insertSort耗時: 2 ms

selectSort耗時: 3 ms

//—1w—

quickSort耗時: 2 ms

mergeSort: 3 ms

listSort耗時: 19 ms

arraysSort耗時: 4 ms

maoPaoSort耗時: 166 ms

maoPaoSortPlus耗時: 122 ms

insertSort耗時: 12 ms

selectSort耗時: 52 ms

//—10w—

quickSort耗時: 14 ms

mergeSort: 19 ms

listSort耗時: 65 ms

arraysSort耗時: 12 ms

maoPaoSort耗時: 15242 ms

maoPaoSortPlus耗時: 15044 ms

insertSort耗時: 797 ms

selectSort耗時: 4073 ms

//—20w—

quickSort耗時: 26 ms

mergeSort: 34 ms

listSort耗時: 102 ms

arraysSort耗時: 60 ms

maoPaoSort耗時: 60811 ms

maoPaoSortPlus耗時: 60378 ms

insertSort耗時: 3279 ms

selectSort耗時: 15762 ms

2021年11月25日 更新. 增加瞭堆排序

// 20w數據

quickSort耗時: 39 ms

mergeSort: 32 ms

創建完畢

heapSort耗時: 21 ms

listSort耗時: 111 ms

arraysSort耗時: 20 ms

maoPaoSort耗時: 50410 ms

maoPaoSortPlus耗時: 55862 ms

insertSort耗時: 10127 ms

selectSort耗時: 8619 ms

總結

到此這篇關於幾種常見的java排序算法的文章就介紹到這瞭,更多相關java排序算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：