本文總結(jié)十大經(jīng)典排序算法及變形淀弹，并提供Java實(shí)現(xiàn)。
參考文章：
十大經(jīng)典排序算法總結(jié)（Java語言實(shí)現(xiàn)）
快速排序算法—左右指針法庆械，挖坑法薇溃，前后指針法，遞歸和非遞歸
快速排序及優(yōu)化（三路劃分等）

一缭乘、排序算法概述

1沐序、定義

將雜亂無章的數(shù)據(jù)元素，通過一定的方法按關(guān)鍵字順序排列的過程叫做排序堕绩。

2策幼、分類

十種常見排序算法可以分為兩大類：

• 非線性時(shí)間比較類排序：通過比較來決定元素間的相對次序，由于其時(shí)間復(fù)雜度不能突破O(nlogn)奴紧，因此稱為非線性時(shí)間比較類排序垄惧。

• 線性時(shí)間非比較類排序：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時(shí)間下界绰寞，以線性時(shí)間運(yùn)行到逊，因此稱為線性時(shí)間非比較類排序。

3滤钱、比較

4觉壶、相關(guān)概念

• 穩(wěn)定：如果a原本在b前面且a=b，排序之后a仍然在b的前面件缸。
• 不穩(wěn)定：如果a原本在b的前面且a=b铜靶，排序之后 a 可能會出現(xiàn)在 b 的后面。
• 時(shí)間復(fù)雜度：對排序數(shù)據(jù)的總的操作次數(shù)他炊。反映當(dāng)n變化時(shí)争剿，操作次數(shù)呈現(xiàn)什么規(guī)律。
• 空間復(fù)雜度：是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲空間的度量痊末，它也是數(shù)據(jù)規(guī)模n的函數(shù)蚕苇。
• 內(nèi)部排序：所有排序操作都在內(nèi)存中完成。本文主要介紹的是內(nèi)部排序凿叠。
• 外部排序：待排序記錄的數(shù)量很大涩笤，以致于內(nèi)存不能一次容納全部記錄嚼吞，所以在排序過程中需要對外存進(jìn)行訪問的排序過程。

二蹬碧、各算法原理及實(shí)現(xiàn)

下面我們來逐一分析十大經(jīng)典排序算法舱禽，主要圍繞下列問題展開：
1、算法的基本思想是什么恩沽？
2誊稚、算法的代碼實(shí)現(xiàn)？
3罗心、算法的時(shí)間復(fù)雜度是多少里伯？（平均、最好协屡、最壞）什么情況下最好？什么情況下最壞全谤？
4肤晓、算法的空間復(fù)雜度是多少？
5认然、算法的穩(wěn)定性如何补憾？

1、冒泡排序（Bubble Sort）

① 基本思想
冒泡排序是一種簡單的排序算法卷员。它重復(fù)地走訪過要排序的數(shù)列盈匾，一次比較兩個(gè)元素，如果它們的順序錯誤就把它們交換過來毕骡。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換削饵，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)槊刻吮容^將當(dāng)前數(shù)列未排序部分的最大的元素“沉”到數(shù)列末端未巫，而小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端窿撬。

② 算法描述
1）比較相鄰的元素。如果前一個(gè)比后一個(gè)大叙凡，就交換它們兩個(gè)劈伴；
2）對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對握爷，這樣在最后的元素應(yīng)該會是最大的數(shù)跛璧；
3）針對所有的元素重復(fù)以上的步驟，除了最后一個(gè)新啼；
4）重復(fù)步驟1~3追城，直到排序完成。為了優(yōu)化算法燥撞，可以設(shè)立一個(gè)布爾標(biāo)識漓柑，每趟排序開始前設(shè)為false，如果該趟排序發(fā)生了交換就置為true，如果一趟排序結(jié)束標(biāo)識仍為false表示該趟排序沒有發(fā)生交換辆布，即數(shù)組已經(jīng)有序瞬矩，可以提前結(jié)束排序。

③ 動圖演示

④ 代碼實(shí)現(xiàn)

 public static int[] bubbleSort(int[] array) {
      if (array.length == 0)
          return array;
      for (int i = 0; i < array.length; i++){  //外層循環(huán)一次為一趟排序
          /*設(shè)置標(biāo)識锋玲，判斷這趟排序是否發(fā)生了交換景用。
         如果未發(fā)生交換，則說明數(shù)組已經(jīng)有序惭蹂，不必再排序了*/
          boolean isSwap = false;
          for (int j = 0; j < array.length - 1 - i; j++) //內(nèi)層循環(huán)一次為一次相鄰比較
              if (array[j + 1] < array[j]) {
                  int temp = array[j + 1];
                  array[j + 1] = array[j];
                  array[j] = temp;
                  isSwap = true;
              }
          if(!isSwap)
              break;
      }
      return array;
  }

⑤ 時(shí)間復(fù)雜度
冒泡排序平均時(shí)間復(fù)雜度為O(n²)伞插，最好時(shí)間復(fù)雜度為O(n)，最壞時(shí)間復(fù)雜度為O(n²)盾碗。
最好情況：如果待排序元素本來是正序的媚污，那么一趟冒泡排序就可以完成排序工作，比較和移動元素的次數(shù)分別是 (n - 1) 和 0廷雅，因此最好情況的時(shí)間復(fù)雜度為O(n)耗美。
最壞情況：如果待排序元素本來是逆序的，需要進(jìn)行 (n - 1) 趟排序航缀，所需比較和移動次數(shù)分別為 n * (n - 1) / 2和 3 * n * (n-1) / 2商架。因此最壞情況下的時(shí)間復(fù)雜度為O(n²)。

⑥ 空間復(fù)雜度
冒泡排序使用了常數(shù)空間芥玉，空間復(fù)雜度為O(1)

⑦ 穩(wěn)定性
當(dāng) array[j] == array[j+1] 的時(shí)候蛇摸，我們不交換 array[i] 和 array[j]，所以冒泡排序是穩(wěn)定的灿巧。

⑧ 算法拓展
雞尾酒排序赶袄，又稱定向冒泡排序、攪拌排序等抠藕，是對冒泡排序的改進(jìn)弃鸦。在把最大的數(shù)往后面冒泡的同時(shí)，把最小的數(shù)也往前面冒泡幢痘，同時(shí)收縮無序區(qū)的左右邊界唬格，有序區(qū)在序列左右逐漸累積。

動圖如下：

代碼如下：

public static void cocktailSort(int[] array) {
        int left = 0,right = array.length-1;
        while(left < right) {
            for(int i = left; i < right; i++) 
              if(array[i] > array[i+1]) 
                    swap(array,i,i + 1);
            right--;
            for(int i = right; i > left; i--) 
              if(array[i] < array[i-1]) 
                    swap(array,i,i-1);
            left++;
        }
}

雞尾酒排序是穩(wěn)定的颜说。它的平均時(shí)間復(fù)雜度為O(n²)购岗，最好情況是待排序列原先就是正序的，時(shí)間復(fù)雜度為O(n)门粪，最壞情況是待排序列原先是逆序的喊积，時(shí)間復(fù)雜度為O(n²)⌒瑁空間復(fù)雜度為O(1)乾吻。

2髓梅、簡單選擇排序（Selection Sort）

① 基本思想
簡單選擇排序(Selection-sort)是一種簡單直觀的排序算法。它的工作原理：首先在未排序序列中找到最幸锴（大）元素枯饿，存放到排序序列的起始位置，然后诡必，再從剩余未排序元素中繼續(xù)尋找最猩莘健（大）元素，然后放到已排序序列的末尾爸舒。以此類推蟋字，直到所有元素均排序完畢。

② 算法描述
n個(gè)記錄的簡單選擇排序可經(jīng)過(n-1)趟簡單選擇排序得到有序結(jié)果扭勉。具體算法描述如下：
1）初始狀態(tài)：無序區(qū)為R[1..n]鹊奖，有序區(qū)為空；
2）第i趟排序(i=1,2,3…n-1)開始時(shí)涂炎，當(dāng)前有序區(qū)和無序區(qū)分別為R[1..i-1]和R[i..n]忠聚。該趟排序從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄 R[k]，將它與無序區(qū)的第1個(gè)記錄R交換璧尸，使R[1..i]和R[i+1..n]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)咒林；
3）(n-1)趟結(jié)束熬拒，數(shù)組有序化了爷光。

③ 動圖演示

④ 代碼實(shí)現(xiàn)

public static int[] selectionSort(int[] array) {
        if (array.length == 0)
             return array;
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[minIndex]) //找到最小的數(shù)
                    minIndex = j; //將最小數(shù)的索引保存
            }
            int temp = array[minIndex]; //將最小數(shù)和無序區(qū)的第一個(gè)數(shù)交換
            array[minIndex] = array[i];
            array[i] = temp;
        }
        return array;
    }

⑤ 時(shí)間復(fù)雜度
簡單選擇排序平均時(shí)間復(fù)雜度為O(n²)，最好時(shí)間復(fù)雜度為O(n²)澎粟，最壞時(shí)間復(fù)雜度為O(n²)蛀序。
最好情況：如果待排序元素本來是正序的若未，則移動元素次數(shù)為 0蒋譬，但需要進(jìn)行 n * (n - 1) / 2 次比較。
最壞情況：如果待排序元素中第一個(gè)元素最大刻撒，其余元素從小到大排列啸盏，則仍然需要進(jìn)行 n * (n - 1) / 2 次比較重贺，且每趟排序都需要移動 3 次元素，即移動元素的次數(shù)為3 * (n - 1)次回懦。
需要注意的是气笙，簡單選擇排序過程中需要進(jìn)行的比較次數(shù)與初始狀態(tài)下待排序元素的排列情況無關(guān)。

⑥ 空間復(fù)雜度
簡單選擇排序使用了常數(shù)空間怯晕，空間復(fù)雜度為O(1)

⑦ 穩(wěn)定性
簡單選擇排序不穩(wěn)定潜圃，比如序列 2、4舟茶、2谭期、1堵第，我們知道第一趟排序第 1 個(gè)元素 2 會和 1 交換，那么原序列中 2 個(gè) 2 的相對前后順序就被破壞了隧出，所以簡單選擇排序不是一個(gè)穩(wěn)定的排序算法踏志。

3、直接插入排序（Insertion Sort）

① 基本思想
直接插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法鸳劳。它的工作原理是通過構(gòu)建有序序列狰贯，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描赏廓，找到相應(yīng)位置并插入涵紊。

② 算法描述
一般來說，直接插入排序都采用in-place（原地算法）在數(shù)組上實(shí)現(xiàn)幔摸。具體算法描述如下：
1）從第一個(gè)元素開始摸柄，該元素可以認(rèn)為已經(jīng)被排序；
2）取出下一個(gè)元素既忆，在已經(jīng)排序的元素序列中從后向前掃描驱负；
3）如果該元素（已排序）大于新元素，將該元素移到下一位置患雇；
4）重復(fù)步驟3跃脊，直到找到已排序的元素小于或者等于新元素的位置；
5）將新元素插入到該位置后苛吱；
6）重復(fù)步驟2~5酪术。

③ 動圖演示

④ 代碼實(shí)現(xiàn)

public static int[] insertionSort(int[] array) {
        if (array.length == 0)
            return array;
        int current;
        for (int i = 1; i < array.length; i++) {
            current = array[i];
            int preIndex = i - 1;
            while (preIndex >= 0 && current < array[preIndex]) {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            array[preIndex + 1] = current;
        }
        return array;
    }

⑤ 時(shí)間復(fù)雜度
直接插入排序平均時(shí)間復(fù)雜度為O(n²)，最好時(shí)間復(fù)雜度為O(n)翠储，最壞時(shí)間復(fù)雜度為O(n²)绘雁。
最好情況：如果待排序元素本來是正序的，比較和移動元素的次數(shù)分別是 (n - 1) 和 0援所，因此最好情況的時(shí)間復(fù)雜度為O(n)庐舟。
最壞情況：如果待排序元素本來是逆序的，需要進(jìn)行 (n - 1) 趟排序住拭，所需比較和移動次數(shù)分別為 n * (n - 1) / 2和 n * (n - 1) / 2挪略。因此最壞情況下的時(shí)間復(fù)雜度為O(n²)。

⑥ 空間復(fù)雜度
直接插入排序使用了常數(shù)空間滔岳，空間復(fù)雜度為O(1)

⑦ 穩(wěn)定性
直接插入排序是穩(wěn)定的杠娱。

⑧ 算法拓展
在直接插入排序中，待插入的元素總是在有序區(qū)線性查找合適的插入位置澈蟆，沒有利用有序的優(yōu)勢墨辛，考慮使用二分查找搜索插入位置進(jìn)行優(yōu)化，即二分插入排序趴俘。

代碼實(shí)現(xiàn)如下：

 public static int[] BinaryInsertionSort(int[] array) {
        if (array.length == 0)
            return array;
        for(int i = 1;i < array.length;i++) {
            int left = 0;
            int right = i - 1;  // left 和 right 分別為有序區(qū)的左右邊界 
            int current = array[i];
            while (left <= right) {
           //搜索有序區(qū)中第一個(gè)大于 current 的位置睹簇，即為 current 要插入的位置
                int mid = left + ((right - left) >> 1);
                if(array[mid] > current){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }
            for(int j = i - 1;j >= left;j--) {
                array[j + 1] = array[j];
            }
            array[left] = current; // left 為第一個(gè)大于 current 的位置奏赘，插入 current
        }
        return array;
 }

二分插入排序是穩(wěn)定的。它的平均時(shí)間復(fù)雜度是O(n²)太惠，最好時(shí)間復(fù)雜度為O(nlogn)磨淌，最壞時(shí)間復(fù)雜度為O(n²)。

4凿渊、希爾排序（Shell Sort）

① 基本思想
1959年Shell發(fā)明梁只，第一個(gè)突破O(n²)的排序算法，是直接插入排序的改進(jìn)版埃脏。它與直接插入排序的不同之處在于搪锣，它會優(yōu)先比較距離較遠(yuǎn)的元素。希爾排序又叫縮小增量排序彩掐。

② 算法描述
先將整個(gè)待排元素序列分割成 gap 個(gè)增量為 gap 的子序列（每個(gè)子序列由位置相差為 gap 的元素組成构舟，整個(gè)序列正好分割成 gap 個(gè)子序列，每個(gè)序列中有 n / gap 個(gè)元素）分別進(jìn)行直接插入排序堵幽，然后縮減增量為之前的一半再進(jìn)行排序狗超，待 gap == 1時(shí)，希爾排序就變成了直接插入排序朴下。因?yàn)榇藭r(shí)序列已經(jīng)基本有序努咐，直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的殴胧。gap初始值一般取 len / 2渗稍。

③ 動圖演示

④ 代碼實(shí)現(xiàn)

 public static int[] ShellSort(int[] array) {
        int len = array.length;
        if(len == 0)
            return array;
        int current, gap = len / 2;
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                current = array[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && array[preIndex] > current) {
                    array[preIndex + gap] = array[preIndex];
                    preIndex -= gap;
                }
                array[preIndex + gap] = current;
            }
            gap /= 2;
        }
        return array;
    }

⑤ 時(shí)間復(fù)雜度
希爾排序平均時(shí)間復(fù)雜度為O(nlogn)，最好時(shí)間復(fù)雜度為O(nlog²n)溃肪，最壞時(shí)間復(fù)雜度為O(nlog²n)免胃。希爾排序的時(shí)間復(fù)雜度與增量序列的選取有關(guān)音五。

⑥ 空間復(fù)雜度
希爾排序使用了常數(shù)空間惫撰，空間復(fù)雜度為O(1)

⑦ 穩(wěn)定性
由于相同的元素可能在各自的序列中插入排序，最后其穩(wěn)定性就會被打亂躺涝，比如序列 2厨钻、4、1坚嗜、2夯膀，所以希爾排序是不穩(wěn)定的。

5苍蔬、歸并排序（Merge Sort）

① 基本思想
歸并排序是建立在歸并操作上的一種有效的排序算法诱建。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并碟绑，得到完全有序的序列俺猿；即先使每個(gè)子序列有序茎匠，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表押袍，稱為2-路歸并诵冒。

② 算法描述
1）把長度為 n 的輸入序列分成兩個(gè)長度為 n / 2 的子序列；
2）對這兩個(gè)子序列分別采用歸并排序谊惭；
3）將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列汽馋。

③ 動圖演示

④ 代碼實(shí)現(xiàn)

    /**
     * 歸并排序
     *
     * @param array
     * @return
     */
    public static int[] MergeSort(int[] array) {
        if (array.length < 2) return array;
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(MergeSort(left), MergeSort(right));
    }
    /**
     * 歸并排序——將兩段有序數(shù)組結(jié)合成一個(gè)有序數(shù)組
     *
     * @param left
     * @param right
     * @return
     */
    public static int[] merge(int[] left, int[] right) {
       int[] result = new int[left.length + right.length];
       int i = 0,j = 0,k = 0;
       while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        while (i < left.length) {
            result[k++] = left[i++];
        }
        while (j < right.length) {
            result[k++] = right[j++];
        }
        return result;
    }

⑤ 時(shí)間復(fù)雜度
歸并排序平均時(shí)間復(fù)雜度為O(nlogn)，最好時(shí)間復(fù)雜度為O(nlogn)圈盔，最壞時(shí)間復(fù)雜度為O(nlogn)豹芯。
歸并排序的形式就是一棵二叉樹，它需要遍歷的次數(shù)就是二叉樹的深度驱敲，而根據(jù)完全二叉樹的可以得出它在任何情況下時(shí)間復(fù)雜度均是O(nlogn)告组。

⑥ 空間復(fù)雜度
歸并排序空間復(fù)雜度為O(n)

⑦ 穩(wěn)定性
歸并排序是穩(wěn)定的。

⑧ 算法應(yīng)用
歸并排序可以用于求解逆序?qū)?shù)量問題癌佩，具體見：劍指offer - 數(shù)組中的逆序?qū)?/a>

解法如下：

import java.util.*;
public class Solution {
     private static final int MOD = 1000000007;
     private int cnt = 0;

    //遞歸調(diào)用
     private int[] MergeSort(int[] array) {
        if (array.length < 2) 
            return array;
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(MergeSort(left), MergeSort(right));
    }
    /**
     * 將兩段有序數(shù)組結(jié)合成一個(gè)有序數(shù)組
     *
     * @param left
     * @param right
     * @return
     */
    private int[] merge(int[] left, int[] right) {
             int[] result = new int[left.length + right.length];
             int i = 0,j = 0,k = 0;
             while (i < left.length && j < right.length) {
                if (left[i] <= right[j]) {
                    result[k++] = left[i++];
                } else {
                    result[k++] = right[j++];
                     /*歸并同時(shí)統(tǒng)計(jì)逆序?qū)?shù)量木缝，因?yàn)闅w并的兩個(gè)子序列都已有序，故當(dāng)left[i] >  
                     right[j]围辙，有l(wèi)eft[i...left.length - 1]均大于right[j]*/
                    this.cnt = (this.cnt % MOD + (left.length - i) % MOD) % MOD;
                }
             }
             while (i < left.length) {
                result[k++] = left[i++];
             }
             while (j < right.length) {
                result[k++] = right[j++];
             }
             return result;
     }

     public int InversePairs(int [] array) {
        MergeSort(array);
        return cnt % MOD;
    }
}

6我碟、快速排序（Quick Sort）

① 基本思想
快速排序的基本思想：通過一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小姚建，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序矫俺，以達(dá)到整個(gè)序列有序。

② 算法描述
快速排序使用分治法來把一個(gè)數(shù)列分為兩個(gè)子數(shù)列掸冤。具體算法描述如下：
1）從數(shù)列中挑出一個(gè)元素厘托，稱為 “基準(zhǔn)”（pivot）；
2）重新排序數(shù)列稿湿，所有比基準(zhǔn)值小的元素放在基準(zhǔn)前面铅匹，所有比基準(zhǔn)值大的元素放在基準(zhǔn)的后面（相同的數(shù)可以到任一邊），該基準(zhǔn)就處于數(shù)列的中間位置饺藤。這稱為分區(qū)（partition）操作包斑；
3）遞歸地（recursive）對小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列進(jìn)行快速排序。

③ 動圖演示

④ 代碼實(shí)現(xiàn)
快速排序最核心的步驟就是partition操作涕俗，即從待排序的數(shù)列中選出一個(gè)數(shù)作為基準(zhǔn)罗丰，將所有比基準(zhǔn)值小的元素放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素放在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）再姑，該基準(zhǔn)就處于數(shù)列的中間位置萌抵。partition函數(shù)返回基準(zhǔn)的位置，然后就可以對基準(zhǔn)位置的左右子序列遞歸地進(jìn)行同樣的快排操作，從而使整個(gè)序列有序绍填。

下面我們來介紹partition操作的兩種實(shí)現(xiàn)方法：左右指針法 和 挖坑法萎坷。

方法一：左右指針法
基本思路：
1．將數(shù)組的最后一個(gè)數(shù) right 作為基準(zhǔn)數(shù) key。
2．分區(qū)過程：從數(shù)組的首元素 begin 開始向后找比 key 大的數(shù)（begin 找大）沐兰；end 開始向前找比 key 小的數(shù)（end 找卸叩怠）；找到后交換兩者（swap）住闯，直到 begin >= end 終止遍歷瓜浸。最后將 begin（此時(shí)begin == end）和最后一個(gè)數(shù)交換（ 這個(gè)時(shí)候 end 不是最后一個(gè)位置），即 key 作為中間數(shù)（左區(qū)間都是比key小的數(shù)比原，右區(qū)間都是比key大的數(shù)）
3．再對左右區(qū)間重復(fù)第二步插佛，直到各區(qū)間只有一個(gè)數(shù)。

/**
 * partition操作
 * @param array
 * @param left 數(shù)列左邊界
 * @param right 數(shù)列右邊界
 * @return
 */
public static int partition(int[] array,int left,int right) {
        int begin = left;
        int end = right;
        int key = right;

        while( begin < end ) {
            //begin找大
            while(begin < end && array[begin] <= array[key])
                begin++;
            //end找小
            while(begin < end && array[end] >= array[key])
                end--;
            swap(array,begin,end);
        }
        swap(array,begin,right);
        return begin;   //返回基準(zhǔn)位置
    }
 
/**
 * 交換數(shù)組內(nèi)兩個(gè)元素
 * @param array
 * @param i
 * @param j
 */
public static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

方法二：挖坑法
基本思路：
1.定義兩個(gè)指針 left 指向起始位置量窘，right 指向最后一個(gè)元素的位置雇寇，然后指定一個(gè)基準(zhǔn) key（right），作為坑蚌铜。
2.left 尋找比基準(zhǔn)（key）大的數(shù)字锨侯，找到后將 left 的數(shù)據(jù)賦給 right，left 成為一個(gè)坑冬殃，然后 right 尋找比基數(shù)（key）小的數(shù)字囚痴，找到將 right 的數(shù)據(jù)賦給 left，right 成為一個(gè)新坑审葬，循環(huán)這個(gè)過程深滚，直到 begin 指針與 end指針相遇，然后將 key 填入那個(gè)坑（最終：key的左邊都是比key小的數(shù)涣觉，key的右邊都是比key大的數(shù)）痴荐，然后進(jìn)行遞歸操作。

/**
 * partition操作
 * @param array
 * @param left 數(shù)列左邊界
 * @param right 數(shù)列右邊界
 * @return
 */
public static int partition(int[] array,int left,int right) {
        int key = array[right];//初始坑
        while(left < right) {
            //left找大
            while(left < right && array[left] <= key )
                left++;
            array[right] = array[left];//賦值官册，然后left作為新坑
            //right找小
            while(left <right && array[right] >= key)
                right--;
            array[left] = array[right];//right作為新坑
        }
        array[left] = key;
       /*將key賦值給left和right的相遇點(diǎn)生兆，
        保持key的左邊都是比key小的數(shù)，key的右邊都是比key大的數(shù)*/
        return left;//最終返回基準(zhǔn)
    }

實(shí)現(xiàn)了partition操作攀隔，我們就可以遞歸地進(jìn)行快速排序了

 /**
 * 快速排序方法
 * @param array
 * @param left 數(shù)列左邊界
 * @param right 數(shù)列右邊界
 * @return
 */
public static void Quicksort(int array[], int left, int right) {
        if(left < right){
            int pos = partition(array, left, right);
            Quicksort(array, left, pos - 1);
            Quicksort(array, pos + 1, right);
        }
    }

⑤ 代碼優(yōu)化
我們之前選擇基準(zhǔn)的策略都是固定基準(zhǔn)皂贩，即固定地選擇序列的右邊界值作為基準(zhǔn)栖榨，但如果在待排序列幾乎有序的情況下昆汹，選擇的固定基準(zhǔn)將是序列的最大（小）值婴栽，快排的性能不好（因?yàn)槊刻伺判蚝舐郑笥覂蓚€(gè)子序列規(guī)模相差懸殊，大的那部分最后時(shí)間復(fù)雜度很可能會達(dá)到O(n²)）愚争。

下面提供幾種常用的快排優(yōu)化：
優(yōu)化一：隨機(jī)基準(zhǔn)
每次隨機(jī)選取基準(zhǔn)值映皆，而不是固定選取左或右邊界值挤聘。將隨機(jī)選取的基準(zhǔn)值和右邊界值進(jìn)行交換，然后就回到了之前的解法捅彻。
只需要在 partition 函數(shù)前增加如下操作即可：

int random = (int) (left + Math.random() * (right - left + 1));
//隨機(jī)選擇 left ~ right 之間的一個(gè)位置作為基準(zhǔn)
swap(array, random, right);
//把基準(zhǔn)值交換到右邊界

優(yōu)化二：三數(shù)取中法
基本思想：
取第一個(gè)數(shù)组去，最后一個(gè)數(shù)，第（N/2）個(gè)數(shù)即中間數(shù)步淹，三個(gè)數(shù)中數(shù)值中間的那個(gè)數(shù)作為基準(zhǔn)值从隆。
舉個(gè)例子，對于int[] array = { 2缭裆，5键闺，4，9澈驼，3辛燥，6，8缝其，7挎塌，1，0}内边，2勃蜘、3、0分別是第一個(gè)數(shù)假残，第（N/2）個(gè)是數(shù)以及最后一個(gè)數(shù)缭贡，三個(gè)數(shù)中3最大，0最小辉懒，2在中間阳惹，所以取2為基準(zhǔn)值。
實(shí)現(xiàn)getMid函數(shù)即可：

/**
     * 三數(shù)取中眶俩，返回array[left]莹汤、array[mid]、array[right]三者的中間者下標(biāo)作為基準(zhǔn)
     * @param array
     * @param left
     * @param right
     * @return
     */
public static int getMid(int[] array,int left,int right) {
        int mid = left + ((right - left) >> 1);
        int a = array[left];
        int b = array[mid];
        int c = array[right];
        if ((b <= a && a <= c) || (c <= a && a <= b)) { //a為中間值
            return left;
        }
        if ((a <= b && b <= c) || (c <= b && b <= a)) { //b為中間值
            return mid;
        }
        if ((a <= c && c <= b) || (b <= c && c <= a)) { //c為中間值
            return right;
        }
        return left;
    }

優(yōu)化三：當(dāng)待排序序列的長度分割到一定大小后颠印，使用插入排序
在子序列比較小的時(shí)候纲岭，直接插入排序性能較好，因?yàn)閷τ谟行虻男蛄邢吆保迮趴梢赃_(dá)到O(n)的復(fù)雜度止潮，如果序列比較小，使用插排效率要比快排高钞楼。
實(shí)現(xiàn)方式也很簡單喇闸，快排是在子序列元素個(gè)數(shù)為 1 時(shí)才停止遞歸，我們可以設(shè)置一個(gè)閾值n，假設(shè)為5燃乍，則大于5個(gè)元素唆樊，子序列繼續(xù)遞歸，否則選用插排刻蟹。
此時(shí)QuickSort()函數(shù)如下：

public static void Quicksort(int array[], int left, int right) {
        if(right - left > 5){
            int pos = partition(array, left, right);
            Quicksort(array, left, pos - 1);
            Quicksort(array, pos + 1, right);
        }else{
            insertionSort(array);
        }
    }

這種優(yōu)化非常實(shí)用逗旁。
實(shí)測發(fā)現(xiàn)當(dāng)待排序列為 [100000,99999,99998,...,3,2,1] 時(shí)，不加插入優(yōu)化的快排由于遞歸次數(shù)過多甚至拋出了 java.lang.StackOverflowError舆瘪！

而加入了插入優(yōu)化并選擇閾值為 12500 時(shí)痢艺，排序用時(shí)如下：

實(shí)驗(yàn)發(fā)現(xiàn)閾值的選擇也很關(guān)鍵，選擇閾值為 5 介陶，排序用時(shí)如下：

優(yōu)化四：三路劃分
如果待排序列中重復(fù)元素過多堤舒，也會大大影響排序的性能，這是因?yàn)榇罅肯嗤貐⑴c快排時(shí)哺呜，左右序列規(guī)模相差極大舌缤，快排將退化為冒泡排序，時(shí)間復(fù)雜度接近O(n²)某残。這時(shí)候国撵，如果采用三路劃分，則會很好的避免這個(gè)問題玻墅。
三路劃分的思想是利用 partition 函數(shù)將待排序列劃分為三部分：第一部分小于基準(zhǔn)v介牙，第二部分等于基準(zhǔn)v，第三部分大于基準(zhǔn)v澳厢。這樣在遞歸排序區(qū)間的時(shí)候环础，我們就不必再對第二部分元素均相等的區(qū)間進(jìn)行快排了，這在待排序列存在大量相同元素的情況下能大大提高快排效率剩拢。

來看下面的三路劃分示意圖：

說明：紅色部分為小于基準(zhǔn)v的序列线得，綠色部分為等于基準(zhǔn)v的序列，白色部分由于還未被 cur 指針遍歷到徐伐，屬于大小未知的部分贯钩，藍(lán)色部分為大于基準(zhǔn)v的序列。
left 指針為整個(gè)待排區(qū)間的左邊界办素，right 指針為整個(gè)待排區(qū)間的右邊界角雷。less 指針指向紅色部分的最后一個(gè)數(shù)（即小于v的最右位置），more 指針指向藍(lán)色部分的第一個(gè)數(shù)（即大于v的最左位置）性穿。cur 指針指向白色部分（未知部分）的第一個(gè)數(shù)勺三，即下一個(gè)要判斷大小的位置。

算法思路：
1）由于最初紅色和藍(lán)色區(qū)域沒有元素季二，初始化 less = left - 1檩咱，more = right + 1揭措，cur = left胯舷。整個(gè)區(qū)間為未知部分（白色）刻蚯。
2）如果當(dāng)前 array[cur] < v，則 swap(array,++less,cur++)桑嘶，即把紅色區(qū)域向右擴(kuò)大一格（less指針后移）炊汹，把 array[cur] 交換到該位置，cur 指針前移判斷下一個(gè)數(shù)逃顶。
3）如果當(dāng)前 array[cur] = v讨便，則不必交換，直接 cur++
4）如果當(dāng)前 array[cur] > v以政，則 swap(array,--more,cur)霸褒，即把藍(lán)色區(qū)域向左擴(kuò)大一格（more指針前移），把 array[cur] 交換到該位置盈蛮。特別注意废菱！此時(shí)cur指針不能前移，這是因?yàn)榻粨Q到cur位置的元素來自未知區(qū)域抖誉，還需要進(jìn)一步判斷array[cur]殊轴。

利用三路劃分，我們就可以遞歸地進(jìn)行三路快排了袒炉！并且可以愉快地避開所有重復(fù)元素區(qū)間旁理。

代碼實(shí)現(xiàn)：

public static int[] partition(int[] array,int left,int right){
        int v = array[right]; //選擇右邊界為基準(zhǔn)
        int less = left - 1; // < v 部分的最后一個(gè)數(shù)
        int more = right + 1; // > v 部分的第一個(gè)數(shù)
        int cur = left;
        while(cur < more){
            if(array[cur] < v){
                swap(array,++less,cur++);
            }else if(array[cur] > v){
                swap(array,--more,cur);
            }else{
                cur++;
            }
        }
        return new int[]{less + 1,more - 1};  //返回的是 = v 區(qū)域的左右下標(biāo)
}

public static void Quicksort(int array[], int left, int right) {
        if (left < right) {
            int[] p = partition(array,left,right);
            Quicksort(array,left,p[0] - 1); //避開重復(fù)元素區(qū)間
            Quicksort(array,p[1] + 1,right);
        }
}

三路劃分可以解決經(jīng)典的荷蘭國旗問題，具體見 leetcode 75

解法如下：

class Solution {
    // 方法一：使用計(jì)數(shù)排序解決我磁，但需要兩趟掃描,不符合要求
    /*public void sortColors(int[] nums) {
        int[] count = new int[3];
        for(int i = 0; i < nums.length; i++)
            count[nums[i]]++;
        int k = 0;
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < count[i]; j++){
                nums[k++] = i;
            }
        }
    }*/
    // 方法二：使用快速排序的三路劃分孽文，時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1)
    public void sortColors(int[] nums) {
        int len = nums.length;
        if(len == 0)
            return;
        int less = -1;
        int more = len;
        int cur = 0;
        while(cur < more){
            if(nums[cur] == 0){
                swap(nums,++less,cur++);
            }else if(nums[cur] == 2){
                swap(nums,--more,cur);
            }else{
                cur++;
            }
        }
    }
    
    public static void swap(int[] array,int i,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

}

⑥ 時(shí)間復(fù)雜度
快速排序平均時(shí)間復(fù)雜度為O(nlogn)，最好時(shí)間復(fù)雜度為O(nlogn)夺艰，最壞時(shí)間復(fù)雜度為O(n²)叛溢。
最好情況：基準(zhǔn)選擇得當(dāng)，partition函數(shù)每次恰好能均分序列劲适，其遞歸樹的深度就為logn楷掉，時(shí)間復(fù)雜度為O(nlogn)。
最壞情況：選擇了最大或者最小數(shù)字作為基準(zhǔn)霞势，每次劃分只能將序列分為一個(gè)元素與其他元素兩部分烹植，此時(shí)快速排序退化為冒泡排序，如果用樹畫出來愕贡，得到的將會是一棵單斜樹草雕，即所有的結(jié)點(diǎn)只有左（右）結(jié)點(diǎn)的樹，樹的深度為 n固以，時(shí)間復(fù)雜度為O(n²)墩虹。

⑦ 空間復(fù)雜度
快速排序的空間復(fù)雜度主要考慮遞歸時(shí)使用的椫鼋恚空間。
在最好情況下诫钓，即partition函數(shù)每次恰好能均分序列旬昭，空間復(fù)雜度為O(logn)；在最壞情況下菌湃，即退化為冒泡排序问拘，空間復(fù)雜度為O(n)。平均空間復(fù)雜度為O(logn)惧所。

⑧ 穩(wěn)定性
快速排序是不穩(wěn)定的骤坐。

⑨ 算法拓展
快速選擇算法
快速選擇算法用于求解 Kth Element 問題（無序數(shù)組第K大元素），使用快速排序的 partition() 進(jìn)行實(shí)現(xiàn)下愈。
快速排序的 partition() 方法會返回一個(gè)整數(shù) j 使得 a[left..j-1] 小于等于 a[j]纽绍，且 a[j+1..right] 大于等于 a[j]。
此時(shí) a[j] 就是數(shù)組的第 j 小的元素势似，我們可以轉(zhuǎn)換一下題意拌夏，第 k 大的元素就是第 nums.size() - k 小的元素。
找到 Kth Element 之后叫编，再遍歷一次數(shù)組辖佣，所有大于等于 Kth Element 的元素都是 TopK Elements。
時(shí)間復(fù)雜度 O(N)搓逾，空間復(fù)雜度 O(1)卷谈。

還可以使用小根堆求解此問題，時(shí)間復(fù)雜度 O(NlogK)霞篡，空間復(fù)雜度 O(K)世蔗。具體見：leetcode 215

解法如下：

class Solution {
private:
    int partition(vector<int>& array,int left,int right) {
        int key = array[right]; //初始坑
        while(left < right) {
            //left找大
            while(left < right && array[left] <= key )
                left++;
            array[right] = array[left]; //賦值，然后left作為新坑
            //right找小
            while(left <right && array[right] >= key)
                right--;
            array[left] = array[right]; //right作為新坑
        }
        array[left] = key;
       /*將key賦值給left和right的相遇點(diǎn)朗兵，
        保持key的左邊都是比key小的數(shù)污淋，key的右邊都是比key大的數(shù)*/
        return left;//最終返回基準(zhǔn)
    }

public:
    
    /*方法1：堆。用于求解 TopK Elements 問題余掖，通過維護(hù)一個(gè)大小為 K 的小根堆寸爆，
    堆中的元素就是TopK Elements。堆頂元素就是 Kth Element盐欺。如果是第K小的元素
    就建立大根堆赁豆。時(shí)間復(fù)雜度 O(NlogK)，空間復(fù)雜度 O(K)冗美。*/
   /* int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<int,vector<int>,greater<int>> q; 
        for(int i = 0;i < n;i++){
                q.push(nums[i]);
                if(q.size() > k) 
                    q.pop();
        }
        return q.top();
    }*/
    
    /*方法2:快速選擇魔种。用于求解 Kth Element 問題，使用快速排序的 partition() 進(jìn)行實(shí)現(xiàn)粉洼。
    快速排序的 partition() 方法會返回一個(gè)整數(shù) j 使得 a[left..j-1] 小于等于 a[j]节预，
    且 a[j+1..right] 大于等于 a[j]叶摄，此時(shí) a[j] 就是數(shù)組的第 j 小的元素，
    我們可以轉(zhuǎn)換一下題意安拟，第 k 大的元素就是第 nums.size() - k 小的元素蛤吓。
    找到 Kth Element 之后，再遍歷一次數(shù)組去扣，所有大于等于 Kth Element 的元素都是
    TopK Elements柱衔。時(shí)間復(fù)雜度 O(N)樊破，空間復(fù)雜度 O(1)*/
   int findKthLargest(vector<int>& nums, int k) {
    k = nums.size() - k;
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int j = partition(nums, left, right);
        if (j == k) { //選擇的基準(zhǔn)等于目標(biāo)愉棱，跳出循環(huán)
            break;
        } else if (j < k) { //選擇的基準(zhǔn)小于目標(biāo)，在右側(cè)子序列中繼續(xù)選擇
            left = j + 1; 
        } else { //選擇的基準(zhǔn)大于目標(biāo)哲戚，在左側(cè)子序列中繼續(xù)選擇
            right = j - 1; 
        }
      }
        return nums[k];
    }
};

拓展：Arrays.sort() 和 Collections.sort() 原理奔滑，Collections.sort() 底層調(diào)用的是 Arrays.sort()。Arrays.sort() 原理見 剖析JDK8中Arrays.sort底層原理及其排序算法的選擇

7顺少、堆排序（Heap Sort）

① 基本思想
堆排序是一種樹形選擇排序方法朋其，它利用了堆這種數(shù)據(jù)結(jié)構(gòu)。在排序的過程中脆炎，將array[0梅猿，...，n-1]看成是一顆完全二叉樹的順序存儲結(jié)構(gòu)秒裕，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的關(guān)系袱蚓，在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大（最小）的元素几蜻。

② 概念
堆：堆是一種完全二叉樹喇潘，且滿足所有父節(jié)點(diǎn)的值均大于等于（或小于等于）其子節(jié)點(diǎn)的值。
大根堆（最大堆）：滿足所有父節(jié)點(diǎn)的值均大于等于其子節(jié)點(diǎn)的值的堆稱為大根堆梭稚，堆頂元素是堆中元素的最大值颖低。
小根堆（最小堆）：滿足所有父節(jié)點(diǎn)的值均小于等于其子節(jié)點(diǎn)的值的堆稱為小根堆，堆頂元素是堆中元素的最小值弧烤。
堆的順序存儲結(jié)構(gòu)：使用順序數(shù)據(jù)結(jié)構(gòu)（數(shù)組）存儲堆忱屑，表示方法為：
1.數(shù)組按層序遍歷的順序存放完全二叉樹的結(jié)點(diǎn)，下標(biāo)為 0 處為堆頂暇昂，下標(biāo)為 len - 1 處為堆尾莺戒。
2.結(jié)點(diǎn) i 如果存在左孩子（下標(biāo)不超過 len - 1 就存在），左孩子的下標(biāo)為（2 * i + 1）话浇；如果存在右孩子脏毯，右孩子的下標(biāo)為（2 * i + 2）。結(jié)點(diǎn) i 的父結(jié)點(diǎn)下標(biāo)為 (i - 1) / 2 (下標(biāo)為 0 的結(jié)點(diǎn)除外幔崖，它沒有父結(jié)點(diǎn))食店。最后一個(gè)非葉子結(jié)點(diǎn)即為堆尾元素的父結(jié)點(diǎn)渣淤，下標(biāo)為 (len - 1 - 1) / 2 = (len - 2) / 2。

③ 算法描述
1）將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成大頂堆吉嫩，此堆為初始的無序區(qū)；
2）將堆頂元素R[1]與最后一個(gè)元素R[n]交換自娩，此時(shí)得到新的無序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2…n-1]<=R[n]；
3）由于交換后新的堆頂R[1]可能違反堆的性質(zhì)脐彩，因此需要對當(dāng)前無序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆姊扔，然后再次將R[1]與無序區(qū)最后一個(gè)元素交換，得到新的無序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)佛南。不斷重復(fù)此過程直到有序區(qū)的元素個(gè)數(shù)為（n-1）嵌言，則整個(gè)排序過程完成。

④ 動圖演示

⑤ 代碼實(shí)現(xiàn)

//聲明全局變量绵载，用于記錄數(shù)組array的長度蓬蝶；
static int len;
/**
 * 堆排序算法
 * @param array
 * @return
 */
public static int[] HeapSort(int[] array) {
        len = array.length;
        if (len == 0) return array;
        //1.構(gòu)建一個(gè)大根堆
        buildMaxHeap(array);
        //2.循環(huán)將堆頂（最大值）與堆尾交換尘分，刪除堆尾元素，然后重新調(diào)整大根堆
        while (len > 0) {
            swap(array, 0, len - 1);
            len--; //原先的堆尾進(jìn)入有序區(qū)丸氛，刪除堆尾元素
            adjustHeap(array, 0); //重新調(diào)整大根堆
        }
        return array;
 }

 /**
   * 自頂向下調(diào)整以 i 為根的堆為大根堆
   * @param array
   * @param i
   */
public static void adjustHeap(int[] array, int i) {
        int maxIndex = i;
        //如果有左子樹培愁，且左子樹大于父節(jié)點(diǎn)，則將最大指針指向左子樹
        if (2 * i + 1 < len && array[2 * i + 1] > array[maxIndex])
            maxIndex = 2 * i + 1;
        //如果有右子樹缓窜，且右子樹大于父節(jié)點(diǎn)定续，則將最大指針指向右子樹
        if (2 * i + 2 < len && array[2 * i + 2] > array[maxIndex])
            maxIndex = 2 * i + 2;
        //如果父節(jié)點(diǎn)不是最大值，則將父節(jié)點(diǎn)與最大值交換禾锤，并且遞歸調(diào)整與父節(jié)點(diǎn)交換的位置私股。
        if (maxIndex != i) {
            swap(array, maxIndex, i);
            adjustHeap(array, maxIndex);
        }
 }

 /**
  * 自底向上構(gòu)建初始大根堆
  * @param array
  */
 public static void buildMaxHeap(int[] array) {
        //從最后一個(gè)非葉子節(jié)點(diǎn)開始自底向上構(gòu)造大根堆
        for (int i = (len - 2) / 2; i >= 0; i--) { 
            adjustHeap(array, i);
        }
 }

拓展：
1）插入元素：只需要把待插入的元素放置在堆尾，然后 len++ 把其納入堆恩掷，然后調(diào)用 adjustHeap 函數(shù)重新調(diào)整堆即可倡鲸。
2）刪除堆頂元素：只需要把堆頂元素交換到堆尾，然后 len-- 把其移出堆黄娘，然后調(diào)用 adjustHeap 函數(shù)重新調(diào)整堆即可峭状。

⑥ 時(shí)間復(fù)雜度
堆排序平均時(shí)間復(fù)雜度為O(nlogn)克滴，最好時(shí)間復(fù)雜度為O(nlogn)，最壞時(shí)間復(fù)雜度為O(nlogn)优床。
堆排序的形式就是一棵二叉樹劝赔，它需要遍歷的次數(shù)就是二叉樹的深度，而根據(jù)完全二叉樹的可以得出它在任何情況下時(shí)間復(fù)雜度均是O(nlogn)胆敞。

⑦ 空間復(fù)雜度
堆排序使用了常數(shù)空間仍翰，空間復(fù)雜度為O(1)歉备。

⑧ 穩(wěn)定性
堆排序是不穩(wěn)定的。

8帽驯、計(jì)數(shù)排序（Counting Sort）

① 基本思想
計(jì)數(shù)排序不是基于比較的排序算法，其核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中嫌术。 作為一種線性時(shí)間復(fù)雜度的排序度气，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

② 算法描述
1）找出待排序的數(shù)組中最大和最小的元素院领；
2）統(tǒng)計(jì)數(shù)組中每個(gè)值為 i 的元素出現(xiàn)的次數(shù)比然，存入數(shù)組C的第i項(xiàng)扒寄；
3）對所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始嵌戈，每一項(xiàng)和前一項(xiàng)相加）；
4）反向填充目標(biāo)數(shù)組：將每個(gè)元素 i 放在新數(shù)組的第C(i)項(xiàng)于樟，每放一個(gè)元素就將C(i)減去1。

③ 動圖演示

④ 代碼實(shí)現(xiàn)

/**
     * 計(jì)數(shù)排序
     *
     * @param array
     * @return
     */
    public static int[] CountingSort(int[] array) {
        if (array.length == 0) return array;
        int bias, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int i = 0; i < array.length; i++) {
            max = Math.max(max, array[i]);
            min = Math.min(min, array[i]);
        }
       //計(jì)算偏移量路捧，將 min ~ max 映射到 bucket 數(shù)組的 0 ~ (max - min) 位置上
        bias = -min; 
        int[] bucket = new int[max - min + 1];
        Arrays.fill(bucket, 0);
        for (int i = 0; i < array.length; i++) {
            bucket[array[i] + bias]++;
        }
        int index = 0, i = 0;
        while (index < array.length) {
            if (bucket[i] != 0) {
                array[index] = i - bias;
                bucket[i]--;
                index++;
            } else
                i++;
        }
        return array;
    }

⑤ 時(shí)間復(fù)雜度
計(jì)數(shù)排序平均時(shí)間復(fù)雜度為O(n + k)，最好時(shí)間復(fù)雜度為O(n + k)章姓，最壞時(shí)間復(fù)雜度為O(n + k)。n 為遍歷一趟數(shù)組計(jì)數(shù)過程的復(fù)雜度系忙，k 為遍歷一趟桶取出元素過程的復(fù)雜度。

⑥ 空間復(fù)雜度
計(jì)數(shù)排序空間復(fù)雜度為O(k)见剩，k為桶數(shù)組的長度苍苞。

⑦ 穩(wěn)定性
計(jì)數(shù)排序是穩(wěn)定的骂际。

9、桶排序（Bucket Sort）

① 基本思想
桶排序與計(jì)數(shù)排序很相似凑耻，不過現(xiàn)在的桶不單計(jì)數(shù)香浩，是實(shí)實(shí)在在地放入元素餐弱。按照映射函數(shù)將數(shù)據(jù)分配到不同的桶里膏蚓，每個(gè)桶內(nèi)元素再分別排序（可能使用別的排序算法），最后拼接各個(gè)桶中排好序的數(shù)據(jù)。映射函數(shù)人為設(shè)計(jì)破停，但要保證桶 i 中的數(shù)均小于桶 j （i < j）中的數(shù)真慢，即必須桶間必須有序，桶內(nèi)可以無序朗鸠，可以考慮按照數(shù)的區(qū)間范圍劃分桶。下面代碼的桶映射函數(shù)為：(i - min) / arr.length忆家。

② 算法描述
1）設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶揭芍；
2）遍歷輸入數(shù)據(jù)，并且把數(shù)據(jù)一個(gè)一個(gè)放到對應(yīng)的桶里去列另；
3）對每個(gè)不是空的桶的桶內(nèi)元素進(jìn)行排序（可以使用直接插入排序等）页衙；
4）從不是空的桶里把排好序的數(shù)據(jù)拼接起來。

③ 動圖演示

④ 代碼實(shí)現(xiàn)

public static int[] bucketSort(int[] array){
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < array.length; i++){
        max = Math.max(max, array[i]);
        min = Math.min(min, array[i]);
    }
    
    /*桶映射函數(shù)：自己設(shè)計(jì)，要保證桶 i 的數(shù)均小于桶 j （i < j）的數(shù)廉侧，
      即必須桶間必須有序段誊，桶內(nèi)可以無序。這里桶映射函數(shù)為：(i - min) / arr.length*/
    int bucketNum = (max - min) / array.length + 1;
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    for(int i = 0; i < bucketNum; i++){
        bucketArr.add(new ArrayList<Integer>());
    }
    
    //將每個(gè)元素放入桶
    for(int i = 0; i < array.length; i++){
        int num = (array[i] - min) / (array.length);
        bucketArr.get(num).add(array[i]);
    }
    
    //對每個(gè)桶進(jìn)行排序
    for(int i = 0; i < bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));
    }
    
   int k = 0;
   for(int i = 0; i < bucketArr.size(); i++){
      for(int j = 0;j < bucketArr.get(i).size();j++) {
           array[k++] = bucketArr.get(i).get(j);
      }
  }
  return array;
}

⑤ 時(shí)間復(fù)雜度
桶排序平均時(shí)間復(fù)雜度為O(n + k)，最好時(shí)間復(fù)雜度為O(n + k)潜腻，最壞時(shí)間復(fù)雜度為O(n²)砾赔。

⑥ 空間復(fù)雜度
桶排序空間復(fù)雜度為O(n + k)妓盲。

⑦ 穩(wěn)定性
桶排序是穩(wěn)定的。

10筋粗、基數(shù)排序（Radix Sort）

① 基本思想
基數(shù)排序是按照低位先排序，然后收集买决；再按照高位排序督赤，然后再收集；依次類推没卸，直到最高位。有時(shí)候有些屬性是有優(yōu)先級順序的，先按低優(yōu)先級排序瑰煎，再按高優(yōu)先級排序酒甸。最后的次序就是高優(yōu)先級高的在前，高優(yōu)先級相同的低優(yōu)先級高的在前农尖。

② 算法描述
1）取得數(shù)組中的最大數(shù)助隧，并取得位數(shù)并村；
2）array 為原始數(shù)組哩牍，從最低位開始取每個(gè)位組成 radix 數(shù)組；

3. 對 radix 進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）外潜；

③ 動圖演示

④ 代碼實(shí)現(xiàn)

    /**
     * 基數(shù)排序
     * @param array
     * @return
     */
public static int[] RadixSort(int[] array) {
     if (array == null || array.length < 2)
        return array;
        // 1.先算出最大數(shù)的位數(shù)；
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < array.length; i++) {
            max = Math.max(max, array[i]);
    }
    int maxDigit = 0;
    while (max != 0) {
            max /= 10;
            maxDigit++;
    }
    int div = 1;
    ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
    for (int i = 0; i < 10; i++)
        bucketList.add(new ArrayList<Integer>());
        //2.進(jìn)行maxDigit趟分配
    for (int i = 0; i < maxDigit; i++,div *= 10) {
            for (int j = 0; j < array.length; j++) {
                int num = (array[j] / div) % 10;
                bucketList.get(num).add(array[j]);
            }
        //3.收集
            int index = 0;
            for (int j = 0; j < bucketList.size(); j++) {
                for (int k = 0; k < bucketList.get(j).size(); k++)
                    array[index++] = bucketList.get(j).get(k);
                bucketList.get(j).clear();
            }
   }
   return array;
}

⑤ 時(shí)間復(fù)雜度
基數(shù)排序平均時(shí)間復(fù)雜度為O(n * k)，最好時(shí)間復(fù)雜度為O(n * k)哆致，最壞時(shí)間復(fù)雜度為O(n * k)摊阀。

⑥ 空間復(fù)雜度
基數(shù)排序空間復(fù)雜度為O(n + k)。

⑦ 穩(wěn)定性
基數(shù)排序是穩(wěn)定的漱牵。

三刁赦、各排序算法應(yīng)用場景及選擇

1）若 n 較猩趼觥（如n ≤ 50）時(shí)，可采用直接插入或簡單選擇排序波闹。
2）若元素初始狀態(tài)基本有序（正序）精堕，直接插入、冒泡或快速排序?yàn)橐恕?br> 3）若 n 較大庄撮，則應(yīng)采用時(shí)間復(fù)雜度為O(nlogn)的排序方法：快速排序、堆排序或歸并排序烙如。
快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法亚铁，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)徘溢，快速排序的平均時(shí)間最短。
堆排序所需的輔助空間少于快速排序，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況雌隅。這兩種排序都是不穩(wěn)定的修械。
若要求排序穩(wěn)定肯污，則可選用歸并排序。但本文介紹的從單個(gè)記錄起進(jìn)行兩兩歸并的歸并排序算法并不值得提倡，通吵荩可以將它和直接插入排序結(jié)合在一起使用。先利用直接插入排序求得較長的有序數(shù)列灰伟，然后再兩兩歸并之袱箱。因?yàn)橹苯硬迦肱判蚴欠€(wěn)定的，所以改進(jìn)后的歸并排序仍是穩(wěn)定的了讨。
4）當(dāng)范圍已知，且空間不是很重要的情況下可以考慮使用桶排序男杈。