選泡插 快歸希 桶計(jì)基 堆

插入篙议，堆，歸并怠硼，快排

n表示數(shù)據(jù)規(guī)模鬼贱，k表示桶的個(gè)數(shù)。
n: 數(shù)據(jù)規(guī)模
k: “桶”的個(gè)數(shù)
In-place: 占用常數(shù)內(nèi)存香璃，不占用額外內(nèi)存
Out-place: 占用額外內(nèi)存

image.png

常見的快速排序这难、歸并排序、堆排序葡秒、冒泡排序等屬于比較排序姻乓。在排序的最終結(jié)果里嵌溢，元素之間的次序依賴于它們之間的比較。每個(gè)數(shù)都必須和其他數(shù)進(jìn)行比較蹋岩，才能確定自己的位置赖草。
在冒泡排序之類的排序中，問(wèn)題規(guī)模為n剪个，又因?yàn)樾枰容^n次秧骑，所以平均時(shí)間復(fù)雜度為O(n2)。在歸并排序扣囊、快速排序之類的排序中乎折，問(wèn)題規(guī)模通過(guò)分治法消減為logN次，所以時(shí)間復(fù)雜度平均O(nlogn)侵歇。
比較排序的優(yōu)勢(shì)是笆檀，適用于各種規(guī)模的數(shù)據(jù)，也不在乎數(shù)據(jù)的分布盒至，都能進(jìn)行排序酗洒。可以說(shuō)枷遂，比較排序適用于一切需要排序的情況樱衷。

計(jì)數(shù)排序、基數(shù)排序酒唉、桶排序則屬于非比較排序矩桂。非比較排序是通過(guò)確定每個(gè)元素之前，應(yīng)該有多少個(gè)元素來(lái)排序痪伦。針對(duì)數(shù)組arr侄榴，計(jì)算arr[i]之前有多少個(gè)元素，則唯一確定了arr[i]在排序后數(shù)組中的位置网沾。
非比較排序只要確定每個(gè)元素之前的已有的元素個(gè)數(shù)即可癞蚕，所有一次遍歷即可解決。算法時(shí)間復(fù)雜度O(n)辉哥。
非比較排序時(shí)間復(fù)雜度底桦山，但由于非比較排序需要占用空間來(lái)確定唯一位置。所以對(duì)數(shù)據(jù)規(guī)模和數(shù)據(jù)分布有一定的要求醋旦。

1.冒泡排序（BubbleSort）

算法核心

冒泡排序是最簡(jiǎn)單的算法之一恒水，算法的核心是將無(wú)序表中的所有記錄，通過(guò)兩兩比較關(guān)鍵字饲齐，得出升序序列或者降序序列钉凌。

image

最優(yōu)最差情況

冒泡排序什么情況下最快？在輸入的數(shù)據(jù)已經(jīng)是有序時(shí)捂人，在什么情況下最慢御雕，當(dāng)輸入的數(shù)據(jù)是反序時(shí)矢沿。

算法關(guān)鍵

• 1. i 循環(huán)只負(fù)責(zé)外層循環(huán)，比較的是 j 和 j+1 對(duì)應(yīng)的大小饮笛。
• 2. i 循環(huán)是從0開始咨察，長(zhǎng)度是length论熙，j 循環(huán)是從0開始 長(zhǎng)度是 length - 1 - i
• 3. 交換發(fā)生在內(nèi)層循環(huán)

public class BubbleSort {

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

    public static void main(String[] args) {
        int[] arr = new int[]{6,2,22,45,1,6,8,200,56,111};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

復(fù)雜度

• 平均復(fù)雜度: O(n²)
• 最好情況復(fù)雜度: O(n)
• 最壞情況復(fù)雜度: O(n²)
• 空間復(fù)雜度: O(1)
• 排序方式: 內(nèi)排序
• 穩(wěn)定性: 穩(wěn)定

2.選擇排序（SelectionSort）

算法核心

每次從待排序的數(shù)據(jù)元素中選出最懈Ｇ唷（或最大）的元素放在待排序序列起始的位置。

選擇排序

最優(yōu)最差情況

選擇排序什么情況下最快脓诡？在什么情況下最慢无午？無(wú)論任何數(shù)據(jù)進(jìn)去都是O(n²)，所以數(shù)據(jù)規(guī)模越小越好祝谚。

算法關(guān)鍵

• 1.需要一個(gè)minIndex 記錄待排序數(shù)據(jù)中心最邢艹佟（最大）數(shù)據(jù)的索引
• 2.i循環(huán)從0開始，長(zhǎng)度 length 交惯，j循環(huán)從 i+1 開始 長(zhǎng)度length
• 3.交換發(fā)生在外層循環(huán)

public class SelectionSort{

    public void sort(int[] arr) {
        int length = arr.length ;
        for (int i = 0; i < length ; i++) {
            int minIndex = i;
            for (int j = i + 1; j <length ; j++) {
                if(arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            if(minIndex == i){
                continue;
            }
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{6,2,22,45,1,6,8,200,56,111};
        new SelectionSort().sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

復(fù)雜度

• 平均復(fù)雜度: O(n²)
• 最好情況復(fù)雜度: O(n²)
• 最壞情況復(fù)雜度: O(n²)
• 空間復(fù)雜度: O(1)
• 排序方式: 內(nèi)排序
• 穩(wěn)定性: 不穩(wěn)定

3.插入排序 （InsertionSort）

算法核心

將數(shù)據(jù)按照一定的順序一個(gè)一個(gè)的插入到有序表中次泽，最終得到的序列就是已經(jīng)排好序的數(shù)據(jù)。
打過(guò)撲克牌的人都知道席爽，每摸起一張牌意荤，通常按牌的大小進(jìn)行插入排序。

插入排序

最優(yōu)最差情況

和冒泡排序一樣只锻。
插入排序什么情況下最快玖像？在輸入的數(shù)據(jù)已經(jīng)是有序時(shí)，在什么情況下最慢稠鼻，當(dāng)輸入的數(shù)據(jù)是反序時(shí)较解。

算法關(guān)鍵

• 1. i 循環(huán)只負(fù)責(zé)外層循環(huán)寡润，比較的是 j 和 j-1 對(duì)應(yīng)的大小。
• 2. i 循環(huán)是從0開始握恳，長(zhǎng)度是length，j 循環(huán)是從 i + 1 開始 長(zhǎng)度是 j - 1 不越界即（j - 1 >= 0）
• 3. 交換發(fā)生在外層循環(huán)

public class InsertionSort {
    public void sort(int[] arr) {
        int length = arr.length;
        for (int i = 1; i < length ; i++) {
            int j = i ;
            int temp = arr[j];
            for ( ;j >0 && arr[j - 1] > temp;j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }

 public static void main(String[] args) {
        int[] arrInsertion = new int[]{6,2,22,45,1,6,8,200,56,111};
        new InsertionSort().sort(arrInsertion);
        System.out.println("選擇排序結(jié)果"+Arrays.toString(arrInsertion));
    }

復(fù)雜度

• 平均復(fù)雜度: O(n²)
• 最好情況復(fù)雜度: O(n)
• 最壞情況復(fù)雜度: O(n²)
• 空間復(fù)雜度: O(1)
• 排序方式: 內(nèi)排序
• 穩(wěn)定性: 穩(wěn)定

折半插入排序

在原來(lái)插入排序的基礎(chǔ)上捺僻，查詢順序表比較的時(shí)候使用折半查找睡互，可以減少比較次數(shù)，提高排序效率陵像。

public void halfSort(int[] arr){
        int length = arr.length;
        for (int i = 1; i < length  ; i++) {
            int high = i;
            int temp = arr[i];
            int low = 0;
            while(low <= high) {
                int index = (low + high)/2;
                if(temp > arr[index])   {
                    low = index + 1;
                }else {
                    high = index -1;
                }
            }

            for (int j = i ; j > low ; j--) {
                arr[j] = arr[j - 1];
            }
            arr[low] = temp;
        }
    }

成對(duì)插入排序

JDK中使用的成對(duì)插入排序就珠，主要思想還是插入排序，只不過(guò)一次拿兩個(gè)元素醒颖，先用其中一個(gè)較大的元素向前遍歷插入妻怎，然后在用嬌小的元素繼續(xù)向前遍歷插入，這樣較小的元素不必再走一次較大元素走過(guò)的路泞歉。比傳統(tǒng)的插入排序要快逼侦。

2路插入排序

具體思路為：另外設(shè)置一個(gè)同存儲(chǔ)記錄的數(shù)組大小相同的數(shù)組d匿辩，將無(wú)需表中第一個(gè)記錄添加進(jìn)d[0]的位置上，然后從無(wú)需表中第二個(gè)記錄開始榛丢，同d[0]比較铲球，如果該值比d[0]大，則添加到其右側(cè)晰赞，反之添加到左側(cè)稼病。
在這里可將d數(shù)組理解成一個(gè)環(huán)狀數(shù)組。

理解為環(huán)狀數(shù)組

排好序的環(huán)狀數(shù)組

4.冒泡排序，選擇排序褐墅，插入排序?qū)Ρ?/h3>

• 1.三種排序都是內(nèi)排序拆檬，空間復(fù)雜度都為O(1)
• 2.三種排序最差的時(shí)間復(fù)雜度都為O(²),平均的時(shí)間復(fù)雜度都為O(²)，冒泡和插入最好的情況都是O(n)
• 3.選擇排序是不穩(wěn)定排序妥凳，冒泡排序和插入排序是穩(wěn)定排序竟贯。
• 4.選擇排序的交換次數(shù)最少 最差情況下為n-1，冒泡排序和插入排序元素交換次數(shù)不管怎么優(yōu)化都是一個(gè)固定值猾封。比選擇排序要多很多澄耍。
• 5.冒泡排序的數(shù)據(jù)交換要比插入排序移動(dòng)復(fù)雜，冒泡排序需要三個(gè)賦值操作晌缘，插入排序只需要一個(gè)齐莲。
• 6.插入排序在數(shù)據(jù)查找上可優(yōu)化的地方很多，折半插入磷箕、2路插入选酗、成對(duì)插入。而冒泡優(yōu)化空間并不大岳枷。

---

4.希爾排序（ShellSort）

希爾排序芒填。又叫縮小增量排序。也是插入排序中的一種空繁，但是希爾排序相對(duì)于插入算法殿衰，在效率上有很大的提升。
它與插入排序不同之處在于盛泡，他會(huì)優(yōu)先比較距離較遠(yuǎn)的元素闷祥。希爾排序的核心在于間隔序列的設(shè)定。既可以提前設(shè)置好間隔序列傲诵，也可以動(dòng)態(tài)定義間隔序列凯砍。

算法核心

• 1.計(jì)算步長(zhǎng)間隔值gap
• 2.將數(shù)組劃分成這些子數(shù)組
• 3.對(duì)這些子數(shù)組分別按照插入排序思想進(jìn)行排序

• 4.重復(fù)此過(guò)程箱硕，直到間隔為1，進(jìn)行普通的插入排序

  
  
  希爾排序

最優(yōu)最差情況

希爾排序什么情況下最快悟衩？數(shù)據(jù)本身有序的情況下最快O(n) 在什么情況下最慢剧罩？序列中的值（尤其是相鄰的值）互為倍數(shù)的情況。
雖然插入排序是穩(wěn)定的座泳，但是希爾排序在插入的時(shí)候是跳躍性插入的惠昔，有可能破壞穩(wěn)定性。
希爾提出了增量序列 h1 钳榨，h2 舰罚，……纽门，ht 薛耻，只要h1=1，任何增量序列都是可行的赏陵，使用希爾增量排序的時(shí)間復(fù)雜度為O(n^2)饼齿。
Hibbard提出了一個(gè)增量序列：2^k-1，使用Hibbard增量排序的時(shí)間復(fù)雜度為O(n^1.5)蝙搔。

算法關(guān)鍵

• 1.總共使用了三次循環(huán)（也可以使用四次循環(huán)缕溉，邏輯更清晰，效果完全一樣）
• 2. 內(nèi)部?jī)纱窝h(huán)和插入排序的代碼完全一樣吃型。只是內(nèi)部插入排序是增量拆分后的多個(gè)邏輯段交替執(zhí)行的
• 3. 外部循環(huán)是為了控制gap证鸥，gap每次增量如果控制成2^k-1 可以優(yōu)化最差情況時(shí)間復(fù)雜度到O(n^1.5)

插入排序會(huì)，希爾排序代碼就簡(jiǎn)單多了勤晚，在外層嵌套了一個(gè)循環(huán)控制增量枉层。

// 控制增量
  for (int gap = size / 2 ; gap > 0 ; gap /= 2 ) {}     

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

public class ShellSort {
    public void sort(int[] arr){
        int size = arr.length ;
        // 控制增量
        for (int gap = size / 2 ; gap > 0 ; gap /= 2 ) {
           // 注意：這里和動(dòng)圖演示的不一樣，動(dòng)圖是分組執(zhí)行赐写，這里操作是多個(gè)分組交替執(zhí)行
           //（如果使用分組執(zhí)行需要四次循環(huán)）
            for (int i = gap; i < size; i++) {
              int j = i ;
              int temp =arr[j];
              while(j>=gap && arr[j - gap] > temp){
                  arr[j] = arr[j - gap];
                  j-=gap;
              }
              arr[j] = temp;
            }
        }
    }
}

    public static void main(String[] args) {
        int[] arrInsertion = new int[]{6,2,22,45,1,6,8,200,56,111};
        new ShellSort().sort(arrInsertion);
        System.out.println("希爾排序的結(jié)果"+Arrays.toString(arrInsertion));
    }

復(fù)雜度

• 平均復(fù)雜度: O(nlog₂n)
• 最好情況復(fù)雜度: O(n)
• 最壞情況復(fù)雜度: O(n²)
• 空間復(fù)雜度: O(1)
• 排序方式: 內(nèi)排序
• 穩(wěn)定性: 不穩(wěn)定 --雖然插入排序是穩(wěn)定的鸟蜡，但是希爾排序在插入的時(shí)候是跳躍性插入的，有可能破壞穩(wěn)定性

5.快速排序（QuickSort）

快排是利用分治思想挺邀。

算法核心

選擇一個(gè)基準(zhǔn)pivot揉忘，piovt位置可以隨機(jī)選擇，一般選擇第一個(gè)元素端铛。選擇完成后泣矛，將小于pivot的元素放在pivot左邊，大于pivot的元素放在右邊禾蚕。接下來(lái)對(duì)pivot左右兩側(cè)的子序列分別遞歸進(jìn)行快速排序您朽。

image

最優(yōu)最差情況

快速排序什么情況下最快？每次劃分所選擇的中間數(shù)恰好將當(dāng)前序列等分夕膀，經(jīng)過(guò)log₂n趟劃分虚倒，便可以得到長(zhǎng)度為1的子表美侦，這樣整個(gè)算法的時(shí)間復(fù)雜度為O(nlog₂n).

在什么情況下最慢？每次劃分所選擇的中間數(shù)恰好是當(dāng)前序列中最大或最小的元素魂奥，那么每次劃分所得的子表中一個(gè)為空表菠剩，另一子表的長(zhǎng)度為原表長(zhǎng)度-1 這樣，長(zhǎng)度為n的數(shù)據(jù)表需要經(jīng)過(guò)n趟劃分耻煤，使得時(shí)間復(fù)雜度為O(n²)具壮。

另外，盡管快排只需要一個(gè)元素的輔助空間哈蝇，但快排需要一個(gè)椆准耍空間來(lái)實(shí)現(xiàn)遞歸。最好情況棧深為log²(n+1)炮赦， 最壞情況棧深為n 這樣怜跑，快速排序空間復(fù)雜度為O(log₂n)。

優(yōu)化版本-雙軸快速排序
找兩個(gè)基準(zhǔn)數(shù) pivot 將數(shù)據(jù)移動(dòng) 分為less區(qū)域吠勘，middle區(qū)域性芬，more區(qū)域 less和middle起始位置在序列頭部，more區(qū)域其實(shí)位置在序列尾部剧防，整體的移動(dòng)是向中間移動(dòng)植锉。交換到less區(qū)域，less索引向后移動(dòng)峭拘，交換到more區(qū)域 more索引向前移動(dòng) 俊庇。

JDK的快速排序采用的雙軸快排。

算法關(guān)鍵

• 1.一共使用三次循環(huán)鸡挠，可以合并成兩次循環(huán)辉饱，也可以只使用一次循環(huán) 這里為了便于理解使用三次循環(huán)。
• 2.一共使用兩次遞歸宵凌，也可以優(yōu)化成使用一次（增加一個(gè)while循環(huán)）鞋囊。

public class QuickSort {
    public int partition(int[] arr,int left,int right){
        int temp = arr[left];
        int low = left;
        while (left < right) {
            //此處兩個(gè)while可以合并成一個(gè)
            while ( left < right && arr[right] >= temp) {
                right--;
            }
            while (left < right && arr[left] <= temp) {
               left++;
            }
            if(left < right) {
                int current = arr[left];
                arr[left] = arr[right];
                arr[right] = current;
            }
        }
        arr[low] = arr[left];
        arr[left] = temp;

        return left;
    }

    public void sort(int[] arr,int left,int right) {
        if(left < right) {
            int partition = partition(arr,left,right);
            sort(arr,0,partition -1);
            sort(arr,partition + 1,right);
        }
    }


    public static void main(String[] args) {
        int[] arrInsertion = new int[]{66666666,2,3322,43445,31,8,6,8,22200,564,111};
        new QuickSort().sort(arrInsertion,0,arrInsertion.length - 1);
        System.out.println("快速排序的結(jié)果"+ Arrays.toString(arrInsertion));
    }

}

如果只使用一次循環(huán)，可以修改代碼為

  public int partition(int[] arr,int left,int right){
        int pivot= left;
        int index = pivot + 1;
        for(int i = index;i <= right;i++) {
            if(arr[i]<arr[pivot]) {
            swap(arr,i,index);
            index++;
            }
        }
        swap(arr,pivot,index - 1);
        return index - 1;
  }
   

如果改成一次遞歸(不重要)瞎惫， 其實(shí)這種編譯器會(huì)自動(dòng)優(yōu)化溜腐，相比不優(yōu)化時(shí)間幾乎沒(méi)有減少

   public void sort(int[] arr,int left,int right) {
        while(left < right) {
            int partition = partition(arr,left,right);
            sort(arr,left,partition - 1);
            left = partition + 1;
        }
    }

另外交換操作可以使用異或，假如 a = 3 瓜喇，b =4 那么a挺益、b交換可以

a = a ^ b;
b = a ^ b;
a = a ^ b;

再多說(shuō)兩個(gè) 求模運(yùn)算 % 假設(shè)a =5 n = 4 那么a%n = 1 可以用&運(yùn)算符替換 這樣效率要比用%求余要高。
但是有一個(gè)要求乘寒，n必須為2的冪

a & (n -1) = 1

乘除2ⁿ 操作 可以替換為 假設(shè)a =5

a >> 1    等于 a /2
a >>> 1  等于無(wú)符號(hào)a/2
a << 5  等于 a * 2的5次方

右移位運(yùn)算符>>望众，若操作的值為正，則在高位插入0；若值為負(fù)烂翰，則在高位插入1夯缺。
右移補(bǔ)零操作符>>>，無(wú)論正負(fù)甘耿，都在高位插入0踊兜。
此方法完美，推薦使用

復(fù)雜度

• 平均復(fù)雜度: O(nlog₂n)
• 最好情況復(fù)雜度: O(nlog₂n)
• 最壞情況復(fù)雜度: O(n²)
• 空間復(fù)雜度: O(log₂n)
• 排序方式: 內(nèi)排序
• 穩(wěn)定性: 不穩(wěn)定
  快速的效率在序列越亂的時(shí)候佳恬，效率越高捏境。在數(shù)據(jù)有序時(shí)，會(huì)退化成冒泡排序毁葱；
  快速排序比大部分排序算法都要快垫言。盡管我們可以在某些特殊的情況下寫出比快速排序快的算法，但是就通常情況而言倾剿，沒(méi)有比它更快的了筷频。快速排序是遞歸的柱告，對(duì)于內(nèi)存非常有限的機(jī)器來(lái)說(shuō)截驮，它不是一個(gè)好的選擇笑陈。

6.堆排序（HeapSort）

什么是堆际度？

• 1. 一棵完全二叉樹

• 2. 任意父節(jié)點(diǎn)的值大于子結(jié)點(diǎn)（大頂堆）或任意父節(jié)點(diǎn)的值小于子結(jié)點(diǎn)（小頂堆）

     
     
     image.png

堆排序是指利用堆的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的一種排序算法。

算法核心

• 1. 初始化堆 將初始順序表轉(zhuǎn)換為最大堆
• 2. 將堆中根結(jié)點(diǎn)和最右子結(jié)點(diǎn)交換涵妥，并且移除最右子節(jié)點(diǎn)乖菱。
• 3. 重新調(diào)整剩余順序表數(shù)據(jù)為最大堆，遞歸執(zhí)行蓬网。

最優(yōu)最差情況

略

算法關(guān)鍵

• 1. 初始化將順序表轉(zhuǎn)最大堆窒所，找到最后一個(gè)需要headpify的節(jié)點(diǎn) last表示最右葉子節(jié)點(diǎn) 即heapify = （last -1)/ 2 ,依次heapify()操作從heapify節(jié)點(diǎn)至根結(jié)點(diǎn)。
• 2. heapify 操作中如果發(fā)生了交換帆锋，需要遞歸操作交換后的子節(jié)點(diǎn)吵取，保證下層仍然構(gòu)成大頂堆。
• 3.交換時(shí)锯厢，只將順序表生成的最大堆頭部數(shù)據(jù)和尾部數(shù)據(jù)交換皮官。
• 4. 最后在sort時(shí)，只需要循環(huán)交換大頂堆首尾并heapify并即可实辑。

public class HeapSort implements Sort {
    @Override
    public void sort(int[] arr) {
        int length = arr.length;
        buildMaxHeap(arr);
        for (int i = length - 1 ; i > 0 ; i--) {
           swap(arr,0,i);
           heapify(arr,0,i);
        }
    }

    public void heapify(int arr[], int i, int n) {
        int large = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && arr[large] < arr[left]) {
            large = left;
        }
        if (right < n && arr[large] < arr[right]) {
            large = right;
        }
        if (large != i) {
            swap(arr, i, large);
            heapify(arr, large, n);
        }
    }

    public void buildMaxHeap(int[] arr) {
        int length = arr.length;
        int last = length - 1;
        int lastHeapify = (last - 1) / 2;
        for (int i = lastHeapify; i >= 0; i--) {
            heapify(arr, i, length);
        }
    }

    public void swap(int[] arr, int a, int b) {
        arr[a] = arr[a] ^ arr[b];
        arr[b] = arr[a] ^ arr[b];
        arr[a] = arr[a] ^ arr[b];
    }

    public static void main(String[] args) {
        int[] arr = new int[]{3, 5, 6, 10, 11, 12, 13};
        new HeapSort().sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

復(fù)雜度

• 平均復(fù)雜度: O(nlog₂n)
• 最好情況復(fù)雜度: O(nlog₂n)
• 最壞情況復(fù)雜度: O(nlog₂n)
• 空間復(fù)雜度: O(1)
• 排序方式: 內(nèi)排序
• 穩(wěn)定性: 不穩(wěn)定

7.歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法捺氢。該算法時(shí)采用分治法的一個(gè)非常典型的應(yīng)用。將已有子序列合并剪撬，得到完全有序的序列摄乒，即先每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表馍佑，稱為2路歸并斋否。歸并算法效率非常穩(wěn)定。無(wú)論任何數(shù)據(jù)時(shí)間復(fù)雜度都是O(nlog₂n).

算法核心

• 1.把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為n/2 的子序列拭荤。
• 2.對(duì)這兩個(gè)子序列分別采用歸并排序如叼。

• 3.將兩個(gè)子序列合并成一個(gè)最終的排序序列。

  
  
  歸并排序

最優(yōu)最差情況

歸并排序什么情況下最快穷劈？什么情況下最慢笼恰？無(wú)論任何數(shù)據(jù)進(jìn)去都是O(nlog₂n),效率非常穩(wěn)定。適合數(shù)據(jù)量比較大的排序歇终。穩(wěn)定的代價(jià)是需要額外的空間社证。空間復(fù)雜度為O(n).

算法關(guān)鍵

• 1. 整體排序需要兩個(gè)方法 merge 和 mergeSort merge控制合并评凝，mergeSort控制拆分追葡。
• 2.遞歸在mergeSort方法中進(jìn)行。merge合并方法只復(fù)雜把兩個(gè)數(shù)組合并奕短。
• 3.合并時(shí)要考慮四種情況宜肉。左數(shù)組越界，右數(shù)組越界翎碑，左小于右和左不小于右谬返。
• 4.整體只需要在合并時(shí)產(chǎn)生的新數(shù)組進(jìn)行一次循環(huán)。
• 5.遞歸時(shí)日杈，merge(mergeSort(left),mergeSort(right)) ,合并控制外層遞歸遣铝，拆分控制內(nèi)層遞歸。
• 6.length < 2 控制遞歸退出莉擒。

public class MergeSort implements Sort{


    @Override
    public void sort(int[] arr) {
        mergeSort(arr);
    }

    public int[] mergeSort(int[] arr) {
        int length = arr.length;
        if(length < 2) {
            return arr;
        }
        int mid = length / 2 ;
        //取左不取右 此處每次復(fù)制出一個(gè)新的數(shù)組酿炸，空間不是最優(yōu)≌羌剑可以使用原數(shù)組下標(biāo)檢索填硕。空間復(fù)雜度就變?yōu)镺(n)
        int[] left = Arrays.copyOfRange(arr,0,mid);
        int[] right = Arrays.copyOfRange(arr,mid,length);
        return merge(mergeSort(left),mergeSort(right));
    }



    public int[] merge(int[] left,int[] right){
            int[] result = new int[left.length + right .length];
            int leftIndex = 0;
            int rightIndex = 0;
        for (int i = 0; i < result.length; i++) {
            if(leftIndex >= left.length) {
                result[i] = right[rightIndex++];
            }else if(rightIndex >= right.length){
                result[i] = left[leftIndex++];
            }else if(left[leftIndex] > right[rightIndex]){
                result[i] = right[rightIndex++];
            }
             else {
                result[i] = left[leftIndex++];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arrMerge = new int[]{66666666,2,3322,43445,31,8,6,8,22200,564,111};
        System.out.println("歸并排序后結(jié)果："+Arrays.toString(new MergeSort().mergeSort(arrMerge)));
    }

復(fù)雜度

• 平均復(fù)雜度: O(nlog₂n)
• 最好情況復(fù)雜度: O(nlog₂n)
• 最壞情況復(fù)雜度: O(nlog₂n)
• 空間復(fù)雜度: O(n)
• 排序方式: 內(nèi)排序
• 穩(wěn)定性: 穩(wěn)定

快速排序鹿鳖、歸并排序扁眯、堆排序區(qū)別以及如何選擇

時(shí)間復(fù)雜度：平均都是O(nlog₂n)，堆栓辜、歸并和快排最優(yōu)也是O(nlog₂n),唯獨(dú)快排最差是O(n²)恋拍，但是數(shù)據(jù)隨機(jī)性可以消除這一影響。
空間復(fù)雜度：堆排是O(1)藕甩，快排是遞歸次數(shù)O(log₂n),歸并是額外空間+遞歸次數(shù) 簡(jiǎn)化為O(n)
穩(wěn)定性：快排和堆排序不穩(wěn)定施敢，歸并穩(wěn)定

堆排序適合做優(yōu)先隊(duì)列 或者找出k個(gè)數(shù)中前n大的數(shù)（屬于選擇排序的一種周荐，按順序選出）
快排在數(shù)據(jù)量在百萬(wàn)級(jí)以下下的時(shí)候比歸并和堆排序都要快。但是越來(lái)越大時(shí)僵娃，會(huì)超過(guò)歸并排序和堆排序概作。總的來(lái)說(shuō) 堆排序要慢于歸并默怨。
在數(shù)據(jù)量很小的情況下讯榕，插入排序速度會(huì)優(yōu)于快排，并且插入排序優(yōu)化空間比較大匙睹。

8.計(jì)數(shù)排序

計(jì)數(shù)排序是一種非比較性質(zhì)的排序算法愚屁，元素從未排序狀態(tài)變?yōu)橐雅判驙顟B(tài)的過(guò)程，是由額外空間的輔助和元素本身的值決定的痕檬。計(jì)數(shù)排序的過(guò)程中不存在元素之間的比較和交換操作霎槐，根據(jù)元素本身的值，將每個(gè)元素出現(xiàn)的次數(shù)記錄到輔助空間后梦谜，通過(guò)對(duì)輔助空間內(nèi)數(shù)據(jù)的計(jì)算丘跌，即可確定每一個(gè)元素的最終位置。
是桶思想中的一種唁桩。

算法核心

• 1.根據(jù)代拍序列中最大元素和最小元素確定范圍闭树，已經(jīng)count數(shù)組的初始容量。
• 2.遍歷待排序序列荒澡，將每一個(gè)元素出現(xiàn)次數(shù)記錄到count數(shù)組报辱。
• 3.對(duì)額外數(shù)組進(jìn)行計(jì)算，得到每一個(gè)元素的排序后的位置仰猖。
• 4.將待排序序列按照count數(shù)組的位置輸出到結(jié)果數(shù)組上捏肢。

image

最優(yōu)最差情況

計(jì)數(shù)排序什么情況下最快？最大值和最小值差值小 什么情況下最慢饥侵？ 最大值和最小值差值大
適用于序列中的量非常大，但是數(shù)組取值范圍比較小衣屏。

算法關(guān)鍵

• 1.count數(shù)組的大小為max - min + 1 躏升，原序列中具體元素 對(duì)應(yīng)count中下標(biāo)關(guān)系：index = 原序列中的元素值 - min
• 2. count[i] = count[i]+count[i-1] 將count數(shù)組累加，得到的新count數(shù)組中狼忱，對(duì)應(yīng)下標(biāo)index的值value膨疏，就是原序列該元素最后出現(xiàn)的位置，如果需要保證穩(wěn)定性钻弄。對(duì)應(yīng)index - 1 就是元素出現(xiàn)的起始位置佃却。如果使用index -1 那么要考慮count數(shù)組0的位置，因?yàn)?不能再-1窘俺。
• 3. 拿到count數(shù)組后饲帅，遍歷原序列，根據(jù)count數(shù)組的位置 插入結(jié)果序列。

public class CountSort {
    public int[] countSort(int[] arr){
        // 找到最大值最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max,arr[i]);
            min = Math.min(min,arr[i]);
        }
       return destArr(arr,initCountArr(arr,max,min),min);
    }

    public int[] initCountArr(int[] arr,int max,int min){
        // count數(shù)組 長(zhǎng)度為: max - min + 1
        int[] count = new int[max - min + 1];
        // 得到arr每一個(gè)數(shù)字出現(xiàn)次數(shù)的數(shù)組count
        for (int i = 0; i < arr.length; i++) {
            // arr元素對(duì)應(yīng)的count數(shù)組下標(biāo)為  arr[i] - min
            count[arr[i] - min]++;
        }
        // 將count數(shù)組 i 和 i - 1 累加 這樣count數(shù)組的每一個(gè)下標(biāo)對(duì)應(yīng)的值灶泵，就是該下標(biāo)數(shù)字出現(xiàn)的最后位置
        for (int i = 1; i < count.length; i++) {
            count[i] = count[i] + count[i-1];

        }

        return count;
    }


    public int[] destArr(int[] arr,int[] count,int min){
        int[] result = new int[arr.length];
        //考慮到算法的穩(wěn)定性 count數(shù)組對(duì)應(yīng)下標(biāo)的前一位是arr數(shù)組中對(duì)應(yīng)數(shù)字的起始位置 所以用前一位的起始育八，如果有相同的就往后面排
        //這里要考慮到count數(shù)組第0位的往前找下標(biāo)越界的情況，所以第0位單獨(dú)處理赦邻。
        for (int i = 0,j = 0; i <arr.length; i++) {
                if(arr[i] - min == 0) {
                    result[j] = arr[i];
                    j++;
                }else {
                    result[count[arr[i] - min - 1]] = arr[i];
                    count[arr[i] - min - 1]++;
                }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arrInsertion = new int[]{66,2,2,41,45,31,66,6,8,21,15,30};
        System.out.println("計(jì)數(shù)排序的結(jié)果"+ Arrays.toString(new CountSort().countSort(arrInsertion)));
    }

復(fù)雜度

• 平均復(fù)雜度: O(n+k)
• 最好情況復(fù)雜度: O(n+k)
• 最壞情況復(fù)雜度: O(n+k)
• 空間復(fù)雜度: O(n+k)
• 排序方式: 內(nèi)排序
• 穩(wěn)定性: 穩(wěn)定

9.桶排序

按閾值拆分桶髓棋。每個(gè)桶用分別排序
缺點(diǎn)：桶用什么數(shù)據(jù)結(jié)構(gòu)去存儲(chǔ)。如果按數(shù)組 由于可能存在分配不均勻惶洲。 每個(gè)數(shù)組的長(zhǎng)度都要等于原序列長(zhǎng)度按声。也可以使用arrayList 按需擴(kuò)容。但是這樣排序的時(shí)間會(huì)浪費(fèi)在擴(kuò)容上恬吕。如果使用鏈表儒喊，會(huì)在排序的時(shí)候很耗時(shí)。

不太重要 理解思想

算法核心

• 1.設(shè)置一個(gè)定量得數(shù)組當(dāng)作桶币呵。
• 2.遍歷輸入數(shù)據(jù)怀愧，并把每個(gè)數(shù)據(jù)放到對(duì)應(yīng)的桶里去。
• 3.對(duì)每個(gè)不是空的桶進(jìn)行排序余赢。
• 4.從不是空的桶里把排好的數(shù)據(jù)拼接起來(lái)芯义。

image.png

最優(yōu)最差情況

桶排序什么情況下最快？當(dāng)數(shù)據(jù)正好一對(duì)一完全分配到桶中妻柒，只需一次遍歷就可以排好序列扛拨。時(shí)間復(fù)雜度O(n). 什么情況下最慢？當(dāng)數(shù)據(jù)每次只分到一個(gè)桶中举塔，時(shí)間復(fù)雜度為O(n²)

算法關(guān)鍵

具體過(guò)程不描述绑警。就是簡(jiǎn)單的分桶操作，具體桶的內(nèi)部是否需要再分桶或者是使用什么排序算法央渣，根據(jù)具體業(yè)務(wù)場(chǎng)景计盒。

復(fù)雜度

• 平均復(fù)雜度: O(n + k)
• 最好情況復(fù)雜度: O(n)
• 最壞情況復(fù)雜度: O(n²)
• 空間復(fù)雜度: O(n+k) 但實(shí)際上空間做到最好的話，就只能用鏈表芽丹，時(shí)間上就做不到最好北启。
• 排序方式: 內(nèi)排序
• 穩(wěn)定性: 穩(wěn)定

10.基數(shù)排序

基數(shù)排序(Radix Sort)是桶排序的擴(kuò)展，它的基本思想是：將整數(shù)按位數(shù)切割成不同的數(shù)字拔第，然后按每個(gè)位數(shù)分別比較咕村。
基數(shù)排序是一種多關(guān)鍵字排序。

算法核心

LSD：低位優(yōu)先：多次循環(huán)的計(jì)數(shù)排序蚊俺，可做數(shù)字排序（數(shù)字的最大長(zhǎng)度較短效率高）懈涛，相等長(zhǎng)度的字符串排序。

• 1.確定序列中值的最大位數(shù)泳猬，用于確定需要幾輪排序批钠。
• 2.內(nèi)部使用計(jì)數(shù)排序宇植，對(duì)應(yīng)count使用 0-9的范圍。

MSD：高位優(yōu)先：用遞歸來(lái)做价匠〉鄙矗可做字符串排序。

• 1.首先判斷待排序序列中最大位數(shù)踩窖，來(lái)判斷需要求余的長(zhǎng)度坡氯。
• 2.第一輪遍歷序列中是否滿足最大位數(shù)，不滿足放入0桶洋腮，滿足放入高位對(duì)應(yīng)的桶箫柳。
• 3.對(duì)非0桶內(nèi)的序列分別進(jìn)行排序，可以繼續(xù)分桶或者使用其他排序算法啥供。
• 4.非0桶排好后將結(jié)果序列與0桶中的序列遞歸調(diào)用排序方法（進(jìn)行下一位的排序）悯恍。直至0桶內(nèi)為0或1

image

算法關(guān)鍵

MSD代碼未列出。

public class RadixSort  {


    @Override
    public void sort(String[] arr) {
    }

    /** LSD低位優(yōu)先伙狐，適合做長(zhǎng)度相等字符串排序 */
    public String[] radixLSDSort(String[] arr) {
        if(arr.length < 2) {
            return arr;
        }
         int maxLength = arr[0].length();

        for (int i = 0; i < maxLength; i++) {

            //count數(shù)組初始化  26字母 + 1空位
            int[] count = new int[27];
            for (int j = 0; j < arr.length; j++) {

                int index = arr[j].length() - i - 1;
                int temp = arr[j].charAt(index);
                // 這里只考慮小寫涮毫，小寫字母a開始  ascii = 97 count第0位存放空
                count[temp - 96]++;
            }
            //count數(shù)組遞增
            for (int j = 1; j < count.length; j++) {
                count[j] += count[j - 1];
            }

            //原數(shù)組輸出
            String[] result = new String[arr.length];
            for (int j = 0; j < arr.length; j++) {
                int index = arr[j].length() - i - 1;
                int temp = arr[j].charAt(index);
                int value = count[temp - 96 - 1]++;
                result[value] = arr[j];
            }
            arr = result;
        }
        return arr;
    }

    /** LSD低位優(yōu)先，數(shù)字排序贷屎，長(zhǎng)短都可以 */
    public int[] radixLSDSort(int[] arr){
        //找到最大長(zhǎng)度
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max,arr[i]);
        }
        int maxLength = 0;
        while (max > 0){
            max /= 10;
            maxLength++;
        }

        for (int i = 0; i < maxLength; i++) {
            //初始化count數(shù)組
            int[] count = new int[11];
            for (int j = 0; j < arr.length; j++) {
               int value = (int) (arr[j] %  Math.pow(10,i + 1) / Math.pow(10,i));
                count[value + 1]++;
            }
            //count數(shù)組遞增
            for (int j = 1; j < count.length; j++) {
                count[j] += count[j - 1];
            }
            //原數(shù)組輸出
            int[] result = new int[arr.length];
            for (int j = 0; j < arr.length; j++) {
                int value = (int) (arr[j] %  Math.pow(10,i + 1) / Math.pow(10,i));
                result[count[value]++] = arr[j];
            }
            arr = result;
        }

        return arr;
    }



    public static void main(String[] args) {
        String[] stringArr = new String[]{"aaa", "aab", "aba","abc", "dab", "cad", "efe", "fff", "ggg", "hhh", "iii", "aaa"};
        int[] arrRadixArr = new int[]{0,66666666, 2, 3322, 43445, 31, 8, 6, 8, 22200, 564, 111};
        System.out.println(Arrays.toString(new RadixSort().radixLSDSort(stringArr)));
        System.out.println(Arrays.toString(new RadixSort().radixLSDSort(arrRadixArr)));
    }

復(fù)雜度

• 平均復(fù)雜度: O(n * k)
• 最好情況復(fù)雜度: O(n * k)
• 最壞情況復(fù)雜度: O(n * k)
• 空間復(fù)雜度: O(n + k)
• 排序方式: 內(nèi)排序
• 穩(wěn)定性: 穩(wěn)定

這三種排序算法都利用了桶的概念罢防，但對(duì)桶的使用方法上有明顯差異：
基數(shù)排序：根據(jù)鍵值的每位數(shù)字來(lái)分配桶
計(jì)數(shù)排序：每個(gè)桶只存儲(chǔ)單一鍵值
桶排序：每個(gè)桶存儲(chǔ)一定范圍的數(shù)值