穩(wěn)定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不穩(wěn)定：如果a原本在b的前面，而a=b，排序之后a可能會出現(xiàn)在b的后面；
內(nèi)排序：所有排序操作都在內(nèi)存中完成；
外排序：由于數(shù)據(jù)太大，因此把數(shù)據(jù)放在磁盤中，而排序通過磁盤和內(nèi)存的數(shù)據(jù)傳輸才能進行；
時間復雜度： 一個算法執(zhí)行所耗費的時間。
空間復雜度：運行完一個程序所需內(nèi)存的大小。

冒泡排序Bubble Sort

重復地走訪過要排序的數(shù)列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數(shù)列的工作是重復地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

算法描述：
1.比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2.對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。
3.針對所有的元素重復以上的步驟，除了最后一個。
4.持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

代碼實現(xiàn)

public static void bubbleSort(int[] array) {
        boolean didSwap;
        for (int i = 0; i < array.length; i++) {
            didSwap = false;
            for (int j = 0; j < array.length - 1 - i; j++) {
                //這里array[j + 1] < array[j]沒有用<=，同樣是為了提供穩(wěn)定的排序。
                if (array[j + 1] < array[j]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                    didSwap = true;
                }
            }
            if(didSwap == false) {
                return;
            }
        }
    }

當冒泡中途發(fā)現(xiàn)已經(jīng)為正序了，便無需繼續(xù)比對下去。這是優(yōu)化過的方法

時間復雜度

冒泡排序最優(yōu)的時間復雜度O(n)
若初始狀態(tài)是正序的，一趟掃描即可完成排序。所需的關(guān)鍵字比較次數(shù)C和記錄移動次數(shù)M均達到最小值：C=n-1，M=0
冒泡排序最差的時間復雜度O(n2)
若初始狀態(tài)是反序的，需要進行n-1趟排序。每趟排序要進行n-i次關(guān)鍵字的比較
(1≤i≤n-1)，且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下，比較和移動次數(shù)均達到最大值：
Cmax = N(N-1)/2 = O(N^2)
Mmax = 3N(N-1)/2 = O(N^2)
冒泡排序的平均時間復雜度為O(N^2)。

注：這里三次是指交換方法。
先將array[j + 1]值記錄temp,然后用array[j]覆蓋array[j + 1]的值，最后用temp值覆蓋array[j]的值

動畫演示：

image

插入排序Insertion Sort

工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。

插入排序的思想：
從第二個元素開始往后，依次選擇哨兵元素和前面的元素比較，如果前一個元素大于該哨兵元素（從小到大排序），則把前面那個元素移動到后一個位置；繼續(xù)往前比較，直到找某個元素不大于該哨兵元素，則把哨兵元素插入到位置上；

算法描述：
1.從第一個元素開始，該元素可以認為已經(jīng)被排序
2.取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
3.如果該元素（已排序）大于新元素，將該元素移到下一位置
4.重復步驟3，直到找到已排序的元素小于或者等于新元素的位置
5.將新元素插入到該位置后
6.重復步驟2~5

代碼實現(xiàn)

public static void insertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int key = array[i];
            int j = i - 1;
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
    }

時間復雜度

插入排序最優(yōu)的時間復雜度O(n)
若初始狀態(tài)是正序的，一趟掃描即可完成排序。所需的關(guān)鍵字比較次數(shù)C達到最小值：C=n-1
插入排序最差的時間復雜度O(n2)
若初始狀態(tài)是反序的，需要進行n-1趟排序。每趟排序要進行n-i次關(guān)鍵字的比較
(1≤i≤n-1)在這種情況下，比較次數(shù)達到最大值：
Cmax = N(N-1)/2 = O(N2)
冒泡排序的平均時間復雜度為O(N2)。

動畫演示

image

選擇排序Selection Sort

工作原理是首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排序完畢。

優(yōu)點

選擇排序的主要優(yōu)點與數(shù)據(jù)移動有關(guān)。如果某個元素位于正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N。

算法描述：
初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空；
第i趟排序(i=1,2,3…n-1)開始時，當前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(i..n）。該趟排序從當前無序區(qū)中-選出關(guān)鍵字最小的記錄 R[k]，將它與無序區(qū)的第1個記錄R交換，使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)；
n-1趟結(jié)束，數(shù)組有序化了。

代碼實現(xiàn)

public static void selectionSort(int[] arr) {
    int min, temp;
    for (int i = 0; i < arr.length; i++) {
           //初始化未排序序列中最小數(shù)據(jù)數(shù)組下標
                min=i;
        for (int j = i; j < arr.length; j++)
              //在未排序元素中繼續(xù)尋找最小元素，并保存其下標
            if (arr[j] <arr[min]) min = j;
               //將未排序列中最小元素放到已排序列末尾
        temp = arr[min]; 
        arr[min] = arr[i];
        arr[i] = temp;
    }
}

時間復雜度
表現(xiàn)最穩(wěn)定的排序算法之一，因為無論什么數(shù)據(jù)進去都是O(n2)的時間復雜度，所以最優(yōu)最差平均時間復雜度都是O(n2)
選擇排序的交換操作介于0和 (n-1)次之間。選擇排序的比較操作為 n(n-1)/2次。選擇排序的賦值操作介于0和3(n-1)次之間。

動畫演示

image

快速排序Quick Sort

快速排序的基本思想：通過一趟排序?qū)⒋庞涗浄指舫瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。

算法描述：

1.快速排序使用分治法來把一個串分為兩個子串。
從數(shù)列中挑出一個元素，稱為 “基準”
2.重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)操作
3.遞歸地把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序
遞歸到最底部時，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。這個算法一定會結(jié)束，因為在每次的迭代中，它至少會把一個元素擺到它最后的位置去。

代碼實現(xiàn)

private static void quickSort(int[] arr, int head, int tail) {
        if (head >= tail || arr == null || arr.length <= 1) {
            return;
        }
        int i = head, j = tail, pivot = arr[(head + tail) / 2];
        while (i <= j) {
            while (arr[i] < pivot) {
                ++i;
            }
            while (arr[j] > pivot) {
                --j;
            }
            if (i < j) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                ++i;
                --j;
            } else if (i == j) {
                ++i;
            }
        }
        quickSort(arr, head, j);
        quickSort(arr, i, tail);
    }

main方法中調(diào)用quickSort(arr,0,arr.length-1)需要傳排序數(shù)組，起始位置，數(shù)組長度-1

時間復雜度
最優(yōu)時間復雜度：O(nlogn)
快速排序最優(yōu)的情況就是每一次取到的元素都剛好平分整個數(shù)組，一次遞歸共需比較n次，遞歸深度為logn
最差時間復雜度： O(n2)
最差的情況就是每一次取到的元素就是數(shù)組中最小/最大的，這種情況其實就是冒泡排序了(每一次都排好一個元素的順序)n(n-1)/2 = O(n2)
平均情況：O(nlogn)　

image.png

動畫演示

image

希爾排序Shell Sort

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。希爾排序是非穩(wěn)定排序算法。

希爾排序的思想：
shell排序是相當于把一個數(shù)組中的所有元素分成幾部分來排序；先把幾個小部分的元素排序好，讓元素大概有個順序，最后再全面使用插入排序。一般最后一次排序都是和上面的插入排序一樣的

基于插入排序進行改進：
插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高，可以達到線性排序的效率
但插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位

先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，
具體算法描述：
1.選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2.按增量序列個數(shù)k，對序列進行k 趟排序；
3.每趟排序，根據(jù)對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

代碼實現(xiàn)

public static void shellSort(int[] array) {
        int number = array.length / 2;//設(shè)置起始增量
        int i;
        int j;
        int temp;
        while (number >= 1) {
            for (i = number; i < array.length; i++) {
                //對每個子序列進行插入排序
                temp = array[i];
                j = i - number;
                while (j >= 0 && array[j] > temp) {
                    array[j + number] = array[j];
                    j = j - number;
                }
                array[j + number] = temp;
            }
            number = number / 2;//縮小增量
        }
    }

通過增量是否為1控制整個排序的結(jié)束。在增量為為number時,遍歷此時的number個子序，從k=0到k=number-1。隨后對每個子序進行插入排序操作。

步長選擇

步長的選擇是希爾排序的重要部分。只要最終步長為1任何步長序列都可以工作。算法最開始以一定的步長進行排序。然后會繼續(xù)以一定步長進行排序，最終算法以步長為1進行排序。當步長為1時，算法變?yōu)槊芭菖判?，這就保證了數(shù)據(jù)一定會被排序。

時間復雜度
希爾排序的時間復雜度與增量的選取有關(guān)。
最佳情況：T(n) = O( n)
根據(jù)增量序列的不同而不同。已知最好的 O( n)
最壞情況：T(n) = O(nlog2 n)
平均情況：T(n) =O(nlog2n)

總的來說，比較在希爾排序中是最主要的操作，而不是交換。在一些步長序列的希爾排序比插入排序要快，甚至在小數(shù)組中比快速排序和堆排序還快，但是在涉及大量數(shù)據(jù)時希爾排序還是比快速排序慢。

動畫演示

image

以23, 10, 4, 1的步長序列進行希爾排序。

歸并排序Merge Sort

該算法是采用分治法的一個非常典型的應用，且各層分治遞歸可以同時進行。歸并指的是將兩個已經(jīng)排序的序列合并成一個序列的操作。

歸并操作有兩種實現(xiàn)方式：遞歸和迭代

遞歸算法描述：
1.申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列
2.設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
3.比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
4.重復步驟3直到某一指針到達序列尾
5.將另一序列剩下的所有元素直接復制到合并序列尾

代碼實現(xiàn)

public static void MergeSort(int[] arr, int low, int high)
    {
        //使用遞歸的方式進行歸并排序，所需要的空間復雜度是O（N+logN）
        int mid = (low + high)/2;
        if(low < high)
        {
            //遞歸地對左右兩邊進行排序
            MergeSort(arr, low, mid);
            MergeSort(arr, mid+1, high);
            //合并
            merge(arr, low, mid, high);
        }
    }
    //merge函數(shù)實際上是將兩個有序數(shù)組合并成一個有序數(shù)組
    //因為數(shù)組有序，合并很簡單
    private static void merge(int[] arr, int low, int mid, int high)
    {
        //temp數(shù)組用于暫存合并的結(jié)果
        int[] temp = new int[high - low + 1];
        //左半邊的指針
        int i = low;
        //右半邊的指針
        int j = mid+1;
        //合并后數(shù)組的指針
        int k = 0;
        //將記錄由小到大地放進temp數(shù)組
        for(; i <= mid && j <= high; k++)
        {
            if(arr[i] < arr[j]) {
                temp[k] = arr[i++];
            } else {
                temp[k] = arr[j++];
            }
        }
        //接下來兩個while循環(huán)是為了將剩余的（比另一邊多出來的個數(shù)）放到temp數(shù)組中
        while(i <= mid) {
            temp[k++] = arr[i++];
        }
        while(j <= high) {
            temp[k++] = arr[j++];
        }
        //將temp數(shù)組中的元素寫入到待排數(shù)組中
        for(int l = 0; l < temp.length; l++) {
            arr[low + l] = temp[l];
        }
    }

迭代算法描述：
假設(shè)序列共有n個元素
1.將序列每相鄰兩個數(shù)字進行歸并操作，形成ceil(n/2)個序列，排序后每個序列包含兩/一個元素
2.若此時序列數(shù)不是1個則將上述序列再次歸并，形成ceil(n/4)個序列，每個序列包含四/三個元素
3.重復步驟2，直到所有元素排序完畢，即序列數(shù)為1

代碼實現(xiàn)

public static void MergeSort(int[] arr)
    {
        //使用迭代的方式來實現(xiàn)歸并排序
        int len = arr.length;
        int k = 1;
        while(k < len)
        {
            MergePass(arr, k, len);
            k *= 2;
        }
    }
    //MergePass方法負責將數(shù)組中的相鄰的有k個元素的字序列進行歸并
    private static void MergePass(int[] arr, int k, int n)
    {
        int i = 0;
        int j;
        //從前往后,將2個長度為k的子序列合并為1個
        while(i < n - 2*k + 1)
        {
            merge(arr, i, i + k-1, i + 2*k - 1);
            i += 2*k;
        }
        //將“落單的”長度不足兩兩merge的部分和前面merge起來。
        if(i < n - k )
        {
            merge(arr, i, i+k-1, n-1);
        }

    }
    //merge函數(shù)實際上是將兩個有序數(shù)組合并成一個有序數(shù)組
    //因為數(shù)組有序，合并很簡單
    private static void merge(int[] arr, int low, int mid, int high)
    {
        //temp數(shù)組用于暫存合并的結(jié)果
        int[] temp = new int[high - low + 1];
        //左半邊的指針
        int i = low;
        //右半邊的指針
        int j = mid+1;
        //合并后數(shù)組的指針
        int k = 0;
        //將記錄由小到大地放進temp數(shù)組
        for(; i <= mid && j <= high; k++)
        {
            if(arr[i] < arr[j]) {
                temp[k] = arr[i++];
            } else {
                temp[k] = arr[j++];
            }
        }
        //接下來兩個while循環(huán)是為了將剩余的（比另一邊多出來的個數(shù)）放到temp數(shù)組中
        while(i <= mid) {
            temp[k++] = arr[i++];
        }
        while(j <= high) {
            temp[k++] = arr[j++];
        }
        //將temp數(shù)組中的元素寫入到待排數(shù)組中
        for(int l = 0; l < temp.length; l++) {
            arr[low + l] = temp[l];
        }
    }

時間復雜度
歸并排序每次會把當前的序列一分為二，然后兩部分各自排好序之后再合并，這個就像是一顆二叉樹，每一層的總計算量是O(n)的，總的層數(shù)是O(logn)的，所以總的復雜度是O(nlogn)
最佳情況： O(nlogn)
最壞情況： O(nlogn)
平均情況： O(nlogn)

動畫演示

image

堆排序Heap Sort

是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子結(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點。

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

代碼實現(xiàn)

public static void heapSort(int[] a){
        System.out.println("開始排序");
        int arrayLength=a.length;
        //循環(huán)建堆
        for(int i=0;i<arrayLength-1;i++){
            //建堆
            buildMaxHeap(a,arrayLength-1-i);
            //交換堆頂和最后一個元素
            swap(a,0,arrayLength-1-i);
            System.out.println(Arrays.toString(a));
        }
    }
    private static void swap(int[] data, int i, int j) {
        int tmp=data[i];
        data[i]=data[j];
        data[j]=tmp;
    }
    //對data數(shù)組從0到lastIndex建大頂堆
    private static void buildMaxHeap(int[] data, int lastIndex) {
        //從lastIndex處節(jié)點（最后一個節(jié)點）的父節(jié)點開始
        for(int i=(lastIndex-1)/2;i>=0;i--){
            //k保存正在判斷的節(jié)點
            int k=i;
            //如果當前k節(jié)點的子節(jié)點存在
            while(k*2+1<=lastIndex){
                //k節(jié)點的左子節(jié)點的索引
                int biggerIndex=2*k+1;
                //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k節(jié)點的右子節(jié)點存在
                if(biggerIndex<lastIndex){
                    //若果右子節(jié)點的值較大
                    if(data[biggerIndex]<data[biggerIndex+1]){
                        //biggerIndex總是記錄較大子節(jié)點的索引
                        biggerIndex++;
                    }
                }
                //如果k節(jié)點的值小于其較大的子節(jié)點的值
                if(data[k]<data[biggerIndex]){
                    //交換他們
                    swap(data,k,biggerIndex);
                    //將biggerIndex賦予k，開始while循環(huán)的下一次循環(huán)，
                          //重新保證k節(jié)點的值大于其左右子節(jié)點的值
                    k=biggerIndex;
                }else{
                    break;
                }
            }
        }
    }

時間復雜度
希爾排序的時間復雜度與增量的選取有關(guān)。
最佳情況：O(nlogn)
最壞情況：O(nlogn)
平均情況：O(nlogn)
動畫演示

image

計數(shù)排序Counting sort

當輸入的元素是 n個0 到k之間的整數(shù)時，它的運行時間是n+k。計數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。

算法描述：
1.找出待排序的數(shù)組中最大和最小的元素
2.統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組 C 的第i項
3.對所有的計數(shù)累加（從 C中的第一個元素開始，每一項和前一項相加）
4.反向填充目標數(shù)組：將每個元素i放在新數(shù)組的第C[i]項，每放一個元素就將C[i]減去1

代碼實現(xiàn)

public static void CountingSort(int[] array) {
        int k;
        int min = array[0];
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }
        k = 0 - min;
        int[] bucket = new int[max - min + 1];
        Arrays.fill(bucket, 0);
        for (int i = 0; i < array.length; i++) {
            bucket[array[i] + k]++;
        }
        int index = 0, i = 0;
        while (index < array.length) {
            if (bucket[i] != 0) {
                array[index] = i - k;
                bucket[i]--;
                index++;
            } else {
                i++;
            }
        }
    }

時間復雜度
k代表數(shù)值中的位數(shù)
最佳情況：O(n+k)
最壞情況：O(n+k)
平均情況：O(n+k)

動畫演示

image

基數(shù)排序Radix Sort

將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)字長度，數(shù)字較短的數(shù)前面補零。然后，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后，數(shù)列就變成一個有序序列。

算法描述
1.取得數(shù)組中的最大數(shù)，并取得位數(shù)；
2.arr為原始數(shù)組，從最低位開始取每個位組成radix數(shù)組；
3.對radix進行計數(shù)排序（利用計數(shù)排序適用于小范圍數(shù)的特點）；

代碼實現(xiàn)

public static int[] RadixSort(int[] array) {
        if (array == null || array.length < 2) {
            return array;
        }
        // 1.先算出最大數(shù)的位數(shù)；
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            max = Math.max(max, array[i]);
        }
        int maxDigit = 0;
        while (max != 0) {
            max /= 10;
            maxDigit++;
        }
        int mod = 10, div = 1;
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            bucketList.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
            for (int j = 0; j < array.length; j++) {
                int num = (array[j] % mod) / div;
                bucketList.get(num).add(array[j]);
            }
            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;
    }

時間復雜度
最佳情況：O(n*k)
最壞情況：O(n2)
平均情況：O(n*k)

動畫演示

image

桶排序Bucket Sort

桶排序是計數(shù)排序的升級版。它利用了函數(shù)的映射關(guān)系，高效與否的關(guān)鍵就在于這個映射函數(shù)的確定。桶排序 (Bucket sort)的工作的原理：假設(shè)輸入數(shù)據(jù)服從均勻分布，將數(shù)據(jù)分到有限數(shù)量的桶里，每個桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排）。

算法描述
1.設(shè)置一個定量的數(shù)組當作空桶
2.遍歷輸入數(shù)據(jù)，并且把數(shù)據(jù)一個一個放到對應的桶里去
3.對每個不是空的桶進行排序
4.從不是空的桶里把排好序的數(shù)據(jù)拼接起來

代碼實現(xiàn)

public static void bucketSort(int[] a){
        int minValue = a[0];
        int maxValue = a[0];
        for (int i = 0; i < a.length; i++) {
            maxValue = Math.max(maxValue, a[i]);
            minValue = Math.min(minValue, a[i]);
        }
        int bucketSize = (maxValue - minValue) / a.length + 1;
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketSize);
        for (int i = 0; i < bucketSize; i++) {
            buckets.add(new ArrayList());
        }
        System.out.println("minValue ="  + minValue);
        System.out.println("maxValue = " + maxValue);
        System.out.println("bucketSize = " + bucketSize);
        for (int i = 0; i < a.length; i++) {
            //映射函數(shù)實現(xiàn)元素與桶之間的對應
            int num = (a[i] - minValue) / a.length;
            buckets.get (num).add(a[i]);
        }
        //對桶進行排序(這里使用了java自帶的TimSort算法)
        // 時間復雜度平均值=最壞= O(nlogn)) 最好=O(n)
        //空間復雜度O(n)
        for (int i = 0; i < buckets.size(); i++) {
            Collections.sort(buckets.get(i));
        }
        System.out.println(buckets.toString());
    }

時間復雜度
N個數(shù)據(jù)平均的分配到M個桶中，這樣每個桶就有[N/M]個數(shù)據(jù)量
桶排序平均時間復雜度為：
O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)
當N=M時，即極限情況下每個桶只有一個數(shù)據(jù)時。桶排序的最好效率能夠達到O(N)。
最佳情況：O(N)
最壞情況：O(n2)
平均情況：O(N+C)，其中C=N*(logN-logM)

關(guān)于基數(shù)排序，計數(shù)排序和桶排序

1.都是非比較的排序算法
2.基數(shù)排序和計數(shù)排序都可以看作是桶排序。
計數(shù)排序本質(zhì)上是一種特殊的桶排序，當桶的個數(shù)取最大的時候，就變成了計數(shù)排序。
3.基數(shù)排序也是一種桶排序。桶排序是按值區(qū)間劃分桶，基數(shù)排序是按數(shù)位來劃分；基數(shù)排序可以看做是多輪桶排序，每個數(shù)位上都進行一輪桶排序。
4.當用最大值作為基數(shù)時，基數(shù)排序就退化成了計數(shù)排序。

關(guān)于這10個流行排序算法的總結(jié)

image.png