插入排序

直接插入排序

• 算法基本思想：（從大到小排序）
  在一個(gè)非遞減的有序數(shù)組中，要新增一個(gè)元素x，有兩個(gè)方法：
  1.從數(shù)組的頭部開(kāi)始向后遍歷，尋找第一個(gè)比x 大的元素y，從y元素開(kāi)始的所有元素全部向后移動(dòng)，最后將x元素插入數(shù)組。（×）
  2.從數(shù)組的尾部開(kāi)始向后向前遍歷，尋找第一個(gè)比x小的元素k，從k元素開(kāi)始，后面每個(gè)元素都向后移動(dòng)，最后將元素x插入數(shù)組。（√）
  

那么我們應(yīng)該選擇哪種方式呢？
其實(shí)仔細(xì)思考一下，我們很容易會(huì)想到選擇第2種方式，原因也很簡(jiǎn)單：在尋找第一個(gè)比x小的元素k時(shí)，我們可以邊把比 x 大的元素往后移動(dòng)。

因此，我們對(duì)一個(gè)數(shù)組排序時(shí)，可以從第2個(gè)元素開(kāi)始，看作是把元素插入一個(gè)已經(jīng)有序的數(shù)組中。
具體代碼如下：

public static void insertSort1(int[] array) {
        for(int i = 1; i < array.length; i++) {
            // 記錄 i 下標(biāo)的元素，防止比 i下標(biāo) 大的元素向后移動(dòng)將其覆蓋
            int tmp = array[i];
            // 從下標(biāo)為 i-1的元素開(kāi)始遍歷， 比 array[i]大的元素都向后移動(dòng)
            int j = i -1;
            for(; j >= 0; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                } else {
    		// 此時(shí)array[j] < array[i]，且 j + 1下標(biāo) 為 array[i] 在已排序元素中的位置
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

時(shí)間復(fù)雜度：O(n2)。最好情況是數(shù)組已經(jīng)有序，只需比較n-1次，時(shí)間復(fù)雜度為O(n)；最壞情況是數(shù)組為待排序順序的逆序，需要(n-1)(n-1)…1次，時(shí)間復(fù)雜度為O(n2)。
空間復(fù)雜度：O(1)。記錄每次待排序的元素的額外空間。
穩(wěn)定性：穩(wěn)定。
適用情況：數(shù)組基本有序的情況下。

折半插入排序

• 算法基本思想：（從大到小排序）
  折半插入排序的本質(zhì)也是在一個(gè)已經(jīng)有序的數(shù)組的插入一個(gè)元素，與直接插入排序的唯一區(qū)別是：折半插入排序是利用二分查找找到那個(gè)合適的插入位置。

• 二分查找的基本步驟：
  將要插入元素跟區(qū)間的中間元素對(duì)比，將待查找的區(qū)間縮小為之前的一半，直到找到要查找的元素，或者區(qū)間被縮小為0（即 left>right ，數(shù)組中不存在指定元素）。
  
  
  
  注意事項(xiàng)：
  （1）若插入元素在數(shù)組不存在（如上圖所示情況），則插入元素的下標(biāo)應(yīng)為 right+1，因此需要將 right+1 下標(biāo) 開(kāi)始的所有元素全部向后移動(dòng)。
  （2）若插入元素與 mid 下標(biāo)的元素相等，為了操作的統(tǒng)一性，我們可以使 right=mid-1，這樣一來(lái)，待插入元素的下標(biāo)也為 right+1 ，接下來(lái)同樣將 right+1 下標(biāo) 開(kāi)始的所有元素全部向后移動(dòng)。

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

    public static void binaryInsertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int left = 0, right = i - 1;
            int mid = (left + right) / 2;
            int target = array[i];      // 待插入的元素
            // 1. 找到合適的插入位置
            while(left <= right) {
                mid = (left + right) / 2;
                if(array[mid] < target) left = mid + 1;
             // 出現(xiàn) array[mid] == target,同樣進(jìn)行此操作，可保證 元素插入下標(biāo)的一致性
                else right = mid -1;	
            }
            // 2. 在已排序好的數(shù)組區(qū)間中，將mid開(kāi)始的元素，從后向前依次向后移動(dòng)
            for (int j = i - 1; j >= right + 1; j--) {
                array[j+1] = array[j];
            }
            // 3. 將 array[i] 插入到 mid 位置
            array[right + 1] = target;
        }
    }

時(shí)間復(fù)雜度：O(n2)。在平均情況下，折半插入排序 的元素移動(dòng)次數(shù)與 直接插入排序 相同， 僅減少了元素間的比較次數(shù)，因此時(shí)間復(fù)雜度仍為O(n2)。
空間復(fù)雜度：O(1)。記錄每次待排序的元素的額外空間。
穩(wěn)定性：穩(wěn)定。
適用情況：數(shù)組基本有序且數(shù)組元素較多，可一定程度減少元素間的比較次數(shù)。

希爾排序(縮小增量排序)

• 算法基本原理:
  希爾排序本質(zhì)上是一種優(yōu)化的"插入排序"，其主要思想是“分組”和“縮小增量”。
  “分組”即將一個(gè)待排序的數(shù)組分為多組數(shù)據(jù)，對(duì)每組數(shù)據(jù)分別進(jìn)行插入排序，使得當(dāng)前排序完成后，每個(gè)小組的數(shù)據(jù)變得局部有序，整個(gè)數(shù)組基本有序，從而達(dá)到預(yù)排序的效果（以便提高最終直接插入排序的效率）.
  “縮小增量”即在整個(gè)數(shù)組的預(yù)排序過(guò)程中，逐漸減少分組數(shù)量，增大每組的數(shù)據(jù)量，直到分組數(shù)量n=1時(shí)，針對(duì)之前的預(yù)排序結(jié)果，進(jìn)行一次直接插入排序。

關(guān)于分組？
對(duì)于前面的分組，并不是如下圖的“逐段分割”式分組方式。(×)

但事實(shí)上，通過(guò)上述例子我們可以看出，經(jīng)過(guò)幾次“預(yù)排序”，似乎并沒(méi)有達(dá)到預(yù)期的基本有序的效果，因?yàn)?1 和 2 這樣較小的數(shù)字依然在后面， 12 這個(gè)比較大的數(shù)子也仍然處于中間的位置，沒(méi)有加快直接插入排序的速度。

這樣的“逐段式”分組方式顯然是不夠合理的，因此這里正確的分組的方式是：將每間隔距離為“增量”大小 gap 的元素分為一組（如下圖）。(√)

這樣"跳躍式"的分組的好處是:若較大的元素在前面,通過(guò)"跳躍式"分組后,較大的元素有機(jī)會(huì)通過(guò)插入排序直接移動(dòng)到后面;若較小的元素在后面,通過(guò)"跳躍式"分組后,較小的元素有機(jī)會(huì)通過(guò)插入排序直接移動(dòng)到前面.

關(guān)于分組后插入排序的方式？
分組后，并不是依次對(duì)每組元素進(jìn)行插入排序，而是從第一組的第 2 個(gè)元素 即下標(biāo)為 gap 的元素開(kāi)始，之后的每個(gè)元素進(jìn)行間距為“增量”大小的插入排序。（如下圖， gap = 3）

關(guān)于 gap 的取值?
gap 的取值有很多種方式,不同取值方式所得到排序時(shí)間復(fù)雜度有所不同,目前并沒(méi)有一種確定的最佳增量序列,但唯一確定的是最后一個(gè)增量應(yīng)為 1 。在本文的代碼實(shí)現(xiàn)中，當(dāng)待排序排序的元素個(gè)數(shù)為 n， gap 的初始值為 n/2，隨后每次 gap = gap/2， 直到 gap 為1，完成排序。

希爾排序的具體代碼實(shí)現(xiàn)如下：

	public static void shellSort(int[] array){
        // 當(dāng)前數(shù)組只有一個(gè)元素，不需要進(jìn)行排序
        if(array.length < 2) return;
        
        // 保證第一次的 gap = n/2,最后一次排序 gap = 1
        int gap = array.length;
        while(gap > 1) {
            gap = gap / 2;
            shell(array, gap);
        }
    }
    private static void shell(int[] array, int gap) {
        for(int i = gap; i < array.length; i++) {
            int tmp = array[i];
            // 若array[j] > tmp，則該元素向前移動(dòng)
   			// j 繼續(xù)向前移動(dòng) gap 個(gè)位置，重復(fù)上述過(guò)程，直到 array[j] <= tmp 或 j < 0  
            int j = i - gap;
            for(; j >= 0; j -= gap) {
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

時(shí)間復(fù)雜度：O(n ^ 1.25) - O(1.6 * n ^ 1.25)。
空間復(fù)雜度：O(1)。
穩(wěn)定性：不穩(wěn)定。
適用情況：適合初始記錄無(wú)序，元素個(gè)數(shù) n 較大時(shí)的情況。

選擇排序

簡(jiǎn)單選擇排序

• 算法基本原理：（從大到小排序）
  （若要求從小到大排序）每次從待排序數(shù)組的區(qū)間中順序遍歷，記錄最大元素的下標(biāo)，然后與待排序數(shù)組區(qū)間的最后一個(gè)元素交換。
  
  
  具體代碼如下：

    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            // 需要找 n - 1 次， 每次從第一個(gè)元素開(kāi)始向后遍歷
            int maxIndex = 0;
            for (int j = 1; j < array.length - i; j++) {
                if(array[j] > array[maxIndex]) maxIndex = j;
            }
            swap(array, array.length - 1 - i, maxIndex);
        }
    }
    private static void swap(int[] array, int x, int y) {
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }

時(shí)間復(fù)雜度：O(n2)。在任何情況下，第 i 趟尋找最大的元素時(shí)，都需要比較 n - i 次，因此n - 1趟排序的時(shí)間復(fù)雜度為O(n2)。
空間復(fù)雜度：O(1)。需要一個(gè)額外空間進(jìn)行元素交換。
穩(wěn)定性：不穩(wěn)定（可通過(guò)代碼改善變得穩(wěn)定）。
適用情況：無(wú)論數(shù)組的有序性如何，簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度都為O(n2)，只適合數(shù)據(jù)量小的排序，一般不推薦使用。

堆排序

堆的說(shuō)明：將數(shù)組按下標(biāo)從小到大抽象成為一顆二叉樹(shù)，再通過(guò)一定的調(diào)整手段，使該二叉樹(shù)具有以下特點(diǎn)：每顆樹(shù)根結(jié)點(diǎn)的值 > 其左右子樹(shù)根結(jié)點(diǎn)的值（大根堆） 或者 每顆樹(shù)根結(jié)點(diǎn)的值 < 其左右子樹(shù)根結(jié)點(diǎn)的值（小根堆） 。（如下圖所示）

• 算法基本思想：（從大到小排序）

1. 把待排序數(shù)組調(diào)整成一個(gè)大根堆，每次將堆頂元素（即根結(jié)點(diǎn)）與待排序堆的最后一個(gè)元素交換
2. 接著將剩下待排序數(shù)組重新調(diào)整成堆（重新上述步驟，最終完成排序）。（如下圖）
   
   
   那么如何將數(shù)組調(diào)整成大根堆呢？（以最開(kāi)始的原數(shù)組為例）
3. 從二叉樹(shù)的最后一個(gè)非終端結(jié)點(diǎn)（即度不為0的結(jié)點(diǎn)）開(kāi)始，將它前面的每個(gè)結(jié)點(diǎn)都進(jìn)行向上調(diào)整。（這里是下標(biāo)0-2的結(jié)點(diǎn)）
4. 對(duì)每個(gè)結(jié)點(diǎn)（這里暫且將該結(jié)點(diǎn)稱(chēng)作root結(jié)點(diǎn)）進(jìn)行調(diào)整時(shí)，需把 root結(jié)點(diǎn) 值的大小與其左右孩子進(jìn)行比較，若 root結(jié)點(diǎn) 的值較小，則將較大的孩子結(jié)點(diǎn)與 root結(jié)點(diǎn) 的值交換。（注意：若交換的孩子結(jié)點(diǎn)也有孩子，仍需繼續(xù)將該孩子進(jìn)行比較和調(diào)整，當(dāng)且僅當(dāng) root結(jié)點(diǎn) 所在的整顆樹(shù)都調(diào)整成為大根堆，該結(jié)點(diǎn)才算調(diào)整完成）。
   
   

建立大根堆的具體代碼如下：

		// array為原始數(shù)組
    private static void createBigHeap(int[] array) {
    	// 最后一個(gè)非終端結(jié)點(diǎn)下標(biāo)為(array.length-2) / 2
    	// 對(duì)下標(biāo)為(array.length-2) / 2 到 下標(biāo)為0的結(jié)點(diǎn)依次進(jìn)行“向上調(diào)整 ”
        for(int parent = (array.length-2) / 2; parent >= 0; parent-- ) {
            shiftDown(array,parent, array.length);
        }
    }

	// root表示當(dāng)前調(diào)整的數(shù)的根結(jié)點(diǎn)下標(biāo)，len表示待調(diào)整的整個(gè)數(shù)組的長(zhǎng)度
    private static void shiftDown(int[] array, int root, int len) {
        int parent = root;
        int child = root * 2 + 1;
        // 防止出現(xiàn)需要多次調(diào)整的情況
        while(child < len) {
       // child + 1 判斷該結(jié)點(diǎn)是否有右孩子，有則通過(guò)比較選出左右孩子的較大值
            if(child + 1 < len && array[child] < array[child+1]) {
                child = child + 1;
            }
       		// 判斷是否需要交換
            if(array[child] > array[parent]) {
                swap(array,child,parent);
                parent = child;
                child = parent * 2 + 1;
            }else {
                break;
            }
        }
    }

經(jīng)過(guò)上述調(diào)整的大根堆，就可以正式開(kāi)始堆排序：

1. 把待排序數(shù)組調(diào)整成一個(gè)大根堆，每次將堆頂元素（即根結(jié)點(diǎn)）與待排序堆的最后一個(gè)元素交換。
2. 接著將剩下待排序數(shù)組重新調(diào)整成堆。（重新1，2步驟）

堆排序具體代碼如下：

public static void heapSort2(int[] array) {
		// 建立大根堆
        createBigHeap(array);
        int end = array.length - 1;
        while(end > 0) {
        	// 交換堆頂元素 與 待排序區(qū)間的末尾元素
            swap(array, 0, end);
            // 重新調(diào)整將剩下區(qū)間調(diào)整成大根堆
            shiftDown(array, 0, end);
            end--;
        }
    }

時(shí)間復(fù)雜度：O(nlog? n)。最壞情況下的時(shí)間時(shí)間復(fù)雜度為也穩(wěn)定在O(n * log? n)。
空間復(fù)雜度：O(1)。需要一個(gè)額外空間進(jìn)行元素交換。
穩(wěn)定性：不穩(wěn)定。
適用情況：堆排序是一種較快的排序算法，它與快速排序，歸并排序的平均時(shí)間都為O(nlog? n)，適用于數(shù)據(jù)量較大時(shí)的排序。

交換排序

冒泡排序

• 算法基本思想：（從大到小排序）
  通過(guò)兩兩比較相鄰記錄的關(guān)鍵字，如果后一個(gè)元素的值大于前一個(gè)元素，則將兩個(gè)元素進(jìn)行交換，從而使關(guān)鍵字大的元素如煮開(kāi)水時(shí)的“氣泡”一樣逐漸向上“漂浮”（右移）。

• 算法步驟：
  （1）具有 n 個(gè)元素的數(shù)組，進(jìn)行 n-1 趟冒泡排序。
  （2）每趟冒泡排序從第一個(gè)元素開(kāi)始向后遍歷，相鄰兩兩元素比較，將關(guān)鍵字大的元素交換到后面，直到當(dāng)前排序區(qū)間最大元素到區(qū)間末尾，這趟冒泡排序結(jié)束。

第一趟的交換過(guò)程如下圖：（某待排序數(shù)組）



當(dāng)?shù)诙伺判蛲瓿珊?，?shù)組的元素分布情況如下：

不難發(fā)現(xiàn)，在第二趟排序結(jié)束后，數(shù)組已經(jīng)屬于有序狀態(tài)，很明顯進(jìn)行接下來(lái)的幾趟排序是“多此一舉”的。
因此我們可以對(duì)普通的冒泡排序做一個(gè)小小的優(yōu)化：即設(shè)置一個(gè)標(biāo)志位 flag = 1，當(dāng)次輪排序過(guò)程發(fā)生了元素交換，則將 flag 置為 0，當(dāng)本趟排序完成后，若 flag == 1，則代表數(shù)組已經(jīng)有序，直接跳出整個(gè)循環(huán)，完成排序操作。

冒泡排序代碼實(shí)現(xiàn)如下：

	public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            // 判斷是否繼續(xù)冒泡排序
            int flag = 1;       
            for (int j = 0; j < array.length - 1 - i; j++) {
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                    flag = 0;
                }
            }
            if(flag == 1) break;
        }
    }

時(shí)間復(fù)雜度：O(n2)。即使設(shè)置標(biāo)志位對(duì)冒泡排序進(jìn)行優(yōu)化，但排序的平均時(shí)間復(fù)雜度仍為O(n2)。
空間復(fù)雜度：O(1)。需要一個(gè)額外空間進(jìn)行元素交換。
穩(wěn)定性：穩(wěn)定。
適用情況：適合數(shù)據(jù)量較小的數(shù)據(jù)排序，當(dāng)數(shù)據(jù)規(guī)模較大時(shí)，排序效率較低。

快速排序

• 算法基本思想：
  快速排序由冒泡排序改進(jìn)而成?？焖倥判虿捎谩胺种巍钡乃枷?，即把一個(gè)大問(wèn)題分解成為多個(gè)子問(wèn)題，通過(guò)解決每個(gè)子問(wèn)題，從而解決整個(gè)大問(wèn)題。
  在每個(gè)子問(wèn)題中，需要選一個(gè)元素值 pivot 作為“基準(zhǔn)”，通過(guò)一定次數(shù)的兩兩元素交換，最終將某個(gè)區(qū)間區(qū)間分為兩個(gè)區(qū)間，左區(qū)間的元素全部不大于 pivot，右區(qū)間的元素全部不小于 pivot。

• 快速排序區(qū)間劃分的兩個(gè)常見(jiàn)方式：
  （1） Hoare法（2）“挖坑”法

Hoare法

1. 在待排序區(qū)間中，選取第一個(gè)元素作為基準(zhǔn)值 pivotkey ，定義 left 和 right 兩個(gè)“指針”，其中l(wèi)eft 指向待排序區(qū)間的第一個(gè)元素，right 指向待排序區(qū)間的最后一個(gè)元素。right 指針向左遍歷尋找第一個(gè)小于 pivot 的元素，left 指針向右遍歷尋找第一個(gè)大于 pivot 的元素， 隨后交換 left 和 right 所指向的元素。
2. 重復(fù)上述步驟，直至 left 指針和 right 指針相遇。將 基準(zhǔn)元素pivot 與 right（left）指針交換，完成分區(qū)操作。
3. 將 pivot 左區(qū)間和右區(qū)間分為兩個(gè)新的待排序區(qū)間，重復(fù)1，2步驟，最終完成排序。

具體的排序過(guò)程如下圖所示：




下面的分區(qū)過(guò)程省略。

通過(guò)以上過(guò)程我們不難看出：快速排序是一個(gè)采用遞歸思想的排序過(guò)程。

注意：當(dāng)你也嘗試著去模擬上述的過(guò)程，你也許會(huì)發(fā)現(xiàn)：好像將left（right）“指針”指向的元素 與 第一個(gè)元素交換后，并不會(huì)出現(xiàn)分區(qū)的現(xiàn)象。

那么造成這種現(xiàn)象的原因是否與 left“指針” 和 right“指針” 移動(dòng)的先后順序有關(guān)呢？
答案是肯定的，這種情況是因?yàn)樵谀承?shù)據(jù)先移動(dòng) left“指針”造成的。因此，在每次尋找符合交換條件的元素時(shí)，應(yīng)先讓 right“指針”向左尋找待交換的元素。

注意： left“指針”要尋找比 pivotkey 大的元素，right“指針”要尋找比 pivotkey 小的元素，那循環(huán)找元素的條件能否直接寫(xiě)成 array[left] < pivotkey 和 array[right] > pivotkey呢？
答案是否定的。原因是數(shù)組可能出現(xiàn) 元素值key == pivotkey 的情況，如果寫(xiě)成上述判斷條件，可能會(huì)出現(xiàn)排序出差的情況。

Hoare法具體的代碼實(shí)現(xiàn)如下：

    public static void quiackSort(int[] array) {
        quick(array, 0, array.length - 1);
    }
    
    private static void quick(int[] array, int left, int right) {
        //代表此時(shí) 此時(shí)排序區(qū)間 只有一個(gè)元素 或者 排序區(qū)間不存在
        if(left >= right) return;
        
        // 在 partition方法中，完成分區(qū)操作，并返回 pivot的下標(biāo)
        int pivot = partition(array, left, right);
        // 對(duì) pivot 的左右區(qū)間進(jìn)行遞歸操作
        quick(array,pivot + 1, right);
        quick(array,left, pivot - 1);
    }
    
    private static int partition(int[] array, int left, int right) {
        int tmp = array[left];
        int i = left;	// 記錄基準(zhǔn)值的下標(biāo)
        while(left < right) {
            //必須先讓 right 去尋找比tmp小的元素， 因?yàn)檫@樣可以防止 一個(gè)大的元素 被錯(cuò)誤地放到 數(shù)組的前面
            while(left < right && array[right] >= tmp) right--;
            while(left < right && array[left] <= tmp) left++;
            
            //此時(shí) left 和 right 分別指向 大于和小于 tmp的元素
            swap(array,left,right);
        }
        swap(array, i, right);
        return right;
    }

“挖坑”法

1. 在待排序區(qū)間中，選取第一個(gè)元素作為基準(zhǔn)值 pivotkey ，用一個(gè)臨時(shí)變量 tmp 存儲(chǔ) pivotkey，同時(shí)定義 left 和 right 兩個(gè)“指針”，其中 left 指向待排序區(qū)間的第一個(gè)元素，right 指向待排序區(qū)間的最后一個(gè)元素。
   因基準(zhǔn)元素 pivot 的值已經(jīng)用 tmp 存儲(chǔ)起來(lái)，故挖坑法顧名思義，已經(jīng)空出來(lái)的 pivot 位置就相當(dāng)于一個(gè)“坑”，當(dāng) right “指針” 找到比 pivotkey 小的元素時(shí)，right 位置的元素可以直接“入坑”，與此同時(shí)right 位置就成為了一個(gè)新的“坑”；此時(shí) left “指針”開(kāi)始尋找比 pivotkey 大的元素，同樣 left 指向的元素“入到新坑”。
2. 重復(fù)上述步驟，直到 left 和 right “指針”相遇，將 tmp 的值放入 兩“指針” 的相遇位置，此時(shí)分區(qū)操作完成。
3. 將 pivot 左區(qū)間和右區(qū)間分為兩個(gè)新的待排序區(qū)間，重復(fù)1，2步驟，最終完成排序。

具體的排序過(guò)程如下圖所示：（數(shù)組的初始序列為：8，10，0，20，5，1，6，9）

“挖坑”法具體的代碼實(shí)現(xiàn)如下：

    public static void quickSort2(int[] array) {
        quick2(array, 0, array.length - 1);
    }
    private static void quick2(int[] tmpArray, int left, int right) {
        if(left >= right) return;       //代表此時(shí) 此時(shí)排序區(qū)間 只有一個(gè)元素 或者 排序區(qū)間不存在

        // 在 partition方法中，完成分區(qū)操作，并返回 pivot的下標(biāo)
        int pivot = partition2(tmpArray, left, right);
        // 對(duì) pivot 的左右區(qū)間進(jìn)行遞歸操作
        quick2(tmpArray, left, pivot - 1);
        quick2(tmpArray, pivot + 1, right);
    }
    private static int partition2(int[] tmpArray, int left, int right) {
        int tmp = tmpArray[left];
        while(left < right) {
            //必須先讓 right 去尋找比tmp小的元素， 因?yàn)檫@樣可以防止 一個(gè)大的元素 被錯(cuò)誤地放到 數(shù)組的前面
            while(left < right && tmpArray[right] >= tmp) right--;
            // right “指針” 入左坑
            swap(tmpArray, left, right);
            while(left < right && tmpArray[left] <= tmp) left++;
            // left “指針” 入右坑
            swap(tmpArray, left, right);
        }
        tmpArray[left] = tmp;
        return left;
    }

時(shí)間復(fù)雜度：O(n log n)。在數(shù)組原來(lái)有序的情況下（非遞減或非遞增），快速排序的遞歸過(guò)程會(huì)變成單分支樹(shù)的遞歸，退化成冒泡排序，即最壞情況下時(shí)間復(fù)雜度為O(n2)；但平均時(shí)間復(fù)雜度仍為O(n log n)。
空間復(fù)雜度：O(1)。需要一個(gè)額外空間進(jìn)行元素交換或值存儲(chǔ)。
穩(wěn)定性：不穩(wěn)定。
適用情況：雖然快速排序存在退化成冒泡排序的可能性，但絕大多數(shù)情況下，數(shù)據(jù)均為亂序狀態(tài)，因此快速排序可以稱(chēng)為“內(nèi)部排序”中最快的排序方法。

歸并排序

• 基本算法思想：
  將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)有序表的過(guò)程稱(chēng)為歸并排序。將含有 n 個(gè)元素的待排序數(shù)組，看成是 n 個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度為1，接著將這 n 個(gè)子序列進(jìn)行兩兩歸并，得到 n/2(n/2+1) 個(gè)長(zhǎng)度為 2或1 的有序子序列；再將這 n/2 個(gè)有序子序列 進(jìn)行兩兩歸并，得到 n/4 個(gè)有序子序列……重復(fù)上述步驟，最終得到一個(gè)長(zhǎng)度為 n 的有序的序列，此時(shí)數(shù)組排序完成。

具體的排序過(guò)程如下圖所示：（數(shù)組的初始序列為：8，10，20，0，5，1，6）

從上圖不難看出，只要知道每次兩兩歸并時(shí)，每個(gè)子數(shù)組的起始下標(biāo) start 和終點(diǎn)坐標(biāo) end ，我們即可根據(jù)學(xué)過(guò)的合并兩個(gè)有序列表的方法，最終將整個(gè)數(shù)組排列成有序序列。

那么如何將含 n 個(gè)元素的數(shù)組分成 n 個(gè)子序列，再進(jìn)行合并呢？
答案是：”采用“分而治之”的思想。先得到待排序數(shù)組中間元素的下標(biāo) mid ，將數(shù)組第一個(gè)元素的下標(biāo) start 到 mid 這個(gè)區(qū)間分為一個(gè)區(qū)間，將 mid+1 到 數(shù)組最后一個(gè)元素的下標(biāo) end 這個(gè)區(qū)間分為另一個(gè)區(qū)間。遞歸重復(fù)上述步驟，直到 start >= end，停止遞歸操作，開(kāi)始合并的過(guò)程。每次合并的左區(qū)間都為 start - mid，右區(qū)間為 mid+1 - end。

歸并排序具體的代碼實(shí)現(xiàn)如下：

    public static void mergeSort(int[] array) {
        merge(array, 0 , array.length - 1);
    }
    private static void merge(int[] array, int left, int right) {
        if(left >= right) return;

        //分解小區(qū)間
        int mid = (left + right) / 2;
        merge(array, left, mid);
        merge(array, mid + 1, right);

        //合并小區(qū)間的有序數(shù)組
        int start1 = left;
        int start2 = mid + 1;
        int[] mergeArray = new int[right - left + 1];
        int k = 0;
        while(start1 <= mid && start2 <= right) {
            if(array[start1] <= array[start2]) {
                mergeArray[k++] = array[start1++];
            }else {
                mergeArray[k++] = array[start2++];
            }
        }
        while(start1 <= mid) {
            mergeArray[k++] = array[start1++];
        }
        while(start2 <= right) {
            mergeArray[k++] = array[start2++];
        }
        //將mergeArray數(shù)組中的元素 放回到 原來(lái)數(shù)組的合并區(qū)間內(nèi)
        k = 0;
        while (left <= right) {
            array[left++] = mergeArray[k++];
        }
    }

時(shí)間復(fù)雜度：O(n log n)。
空間復(fù)雜度：O（n）。

基數(shù)排序

• 算法基本原理：
  基數(shù)排序是一種非比較的排序方法，它通過(guò)若干次“分配”與“收集”對(duì)整個(gè)序列進(jìn)行排序?；鶖?shù)排序利用了“桶”的思想，需要將待排序元素“分解”成若干個(gè)關(guān)鍵字，并準(zhǔn)備若干個(gè)桶，使得桶的范圍能夠覆蓋每次關(guān)鍵字出現(xiàn)的所有可能情況，根據(jù)每個(gè)元素關(guān)鍵字的值依次放入對(duì)應(yīng)的桶，并將元素按桶的順序和元素放入的順序依次取出，進(jìn)行下次“分配”，直至所有關(guān)鍵字完成“分配”和“收集”。

例如：要對(duì)整數(shù)類(lèi)型的數(shù)組進(jìn)行排序，數(shù)組中的元素分別為：12，44，8，26，40，99，3，76，60，25。我們可以將每個(gè)元素的十位和個(gè)位“分解”成2個(gè)關(guān)鍵字，因?yàn)槊總€(gè)關(guān)鍵字的范圍是0~9，因此我們每次需要先準(zhǔn)備10個(gè)桶，每個(gè)桶依次存放關(guān)鍵字為 0 ~ 9 的元素。
接著采用“最低位優(yōu)先法”，即先匹配個(gè)位這個(gè)關(guān)鍵字，將元素依次放入對(duì)應(yīng)的桶，按桶的順序和元素放入的順序依次取出后，接著“分配”并“收集”十位這個(gè)關(guān)鍵字，最終完成排序。（如下圖）

計(jì)數(shù)排序的具體代碼實(shí)現(xiàn)如下：

	public static void radixSort(int[] array) {
        // 1. 先獲得所有元素中的最大位數(shù)
        int count = 1;          // 記錄最大位數(shù)
        int multiple = 10;      // 記錄當(dāng)前倍數(shù)
        for (int x : array) {
            while (x / multiple > 0) {
                multiple *= 10;
                count++;
            }
        }

        // 2. 采用“最低位優(yōu)先法”進(jìn)行 count 次“分配”與“收集”
        multiple = 1;       // 描述當(dāng)前關(guān)鍵字的取值方式
        for (int i = 0; i < count; i++) {
            // 準(zhǔn)備 0~9，總共10個(gè)桶存放元素
            int[][] buckets = new int[10][0];
            for (int j = 0; j < 10; j++) {
                buckets[j] = new int[0];
            }
            // 針對(duì)關(guān)鍵字進(jìn)行“分配”
            for (int x : array) {
                int key = x / multiple % 10;
                int len = buckets[key].length;
                buckets[key] = Arrays.copyOf(buckets[key], len + 1);
                buckets[key][len] = x;
            }
            // 對(duì)元素按順序收集
            int k = 0;
            for (int j = 0; j < 10; j++) {
                // 遍歷每個(gè)桶
                for (int x : buckets[j]) {
                    array[k++] = x;
                }
            }
            multiple *= 10;
        }
    }

時(shí)間復(fù)雜度：O(d (n+t))。對(duì)于 n 個(gè)元素的序列（假設(shè)每個(gè)元素含有 d 個(gè)關(guān)鍵字，每個(gè)關(guān)鍵字的取值范圍有 t 個(gè)值），每一趟“分配”的時(shí)間復(fù)雜度為O(n)，每一趟“收集”的時(shí)間復(fù)雜度為O(t)，要進(jìn)行 d 趟“分配”與“收集”,因此總的時(shí)間復(fù)雜度為O(d (n+t))。
空間復(fù)雜度：O(n+d)。
穩(wěn)定性：穩(wěn)定。
適用情況：有較為苛刻的要求，需要知道各個(gè)關(guān)鍵字的主次關(guān)系和每個(gè)關(guān)鍵字的所有可能取值范圍。

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

• 算法基本思想：

1. 遍歷待排序數(shù)組，記錄數(shù)組中的最大值 max 和最小值 min。
2. 申請(qǐng)一個(gè)空間大小為 max-min+1 的計(jì)數(shù)數(shù)組，計(jì)數(shù)數(shù)組的下標(biāo)通過(guò)一定的轉(zhuǎn)換可以代表待排序數(shù)組的每個(gè)元素大小，鍵值記錄數(shù)字中每個(gè)元素出現(xiàn)的次數(shù)。對(duì)待排序數(shù)組進(jìn)行遍歷，統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)。
3. 對(duì)計(jì)數(shù)數(shù)組進(jìn)行順序遍歷，假如數(shù)組中某元素的值 n 大于0，通過(guò)元素的下標(biāo)，將 n 個(gè)轉(zhuǎn)換后的元素值放入到待排序數(shù)組中。待計(jì)數(shù)數(shù)組遍歷完畢，最終完成排序操作。

注意：計(jì)數(shù)數(shù)組下標(biāo) = array[i] - array[min]

待排序數(shù)組與計(jì)數(shù)數(shù)組的關(guān)系如下:
具體代碼實(shí)現(xiàn)如下：

	public static void countSort(int[] array) {
        int minVal = array[0];
        int maxVal = array[0];
        // 找到數(shù)組元素的最大值和最小值
        for (int i = 1; i < array.length; i++) {
            if(array[i] < minVal) minVal = array[i];
            if(array[i] > maxVal) maxVal = array[i];
        }
        int[] countArray = new int[maxVal - minVal + 1];
        // 記錄每個(gè)元素出現(xiàn)的次數(shù)
        count(array, countArray , minVal);
        //把排序好的數(shù)據(jù)寫(xiě)回到 tmpArray 數(shù)組中
        int k = 0;
        for (int i = 0; i < countArray.length; i++) {
            while(countArray[i] > 0) {
                array[k++] = i + minVal;
                countArray[i]--;
            }
        }
    }
    private static void count(int[] array, int[] countArray, int minVal) {
        for (int i = 0; i < array.length; i++) {
            countArray[array[i] - minVal]++;
        }
    }

時(shí)間復(fù)雜度：O(n + k)，計(jì)數(shù)的時(shí)間復(fù)雜度不僅數(shù)組元素的個(gè)數(shù) n 有關(guān)，也取決于數(shù)組中最大和最小元素的區(qū)間 k。
空間復(fù)雜度：O(K)。（針對(duì)當(dāng)前代碼實(shí)現(xiàn)方式）
穩(wěn)定性：不穩(wěn)定。（針對(duì)當(dāng)前代碼實(shí)現(xiàn)方式）
適用情況：當(dāng)待排序數(shù)組數(shù)據(jù)量較大且數(shù)據(jù)分布較集中時(shí)，計(jì)數(shù)排序的適用程度較高。當(dāng)數(shù)據(jù)分別較分散，差值很大時(shí)應(yīng)使用其他排序算法。

以上就是本篇文章的全部?jī)?nèi)容了，如果這篇文章對(duì)你有些許幫助，你的點(diǎn)贊、收藏和評(píng)論就是對(duì)我最大的支持。
另外，文章可能存在許多不足之處，也希望你可以給我一點(diǎn)小小的建議，我會(huì)努力檢查并改進(jìn)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-717509.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)——9大基礎(chǔ)排序】一文掌握九大經(jīng)典排序（配有詳細(xì)圖文說(shuō)明?。。。┑奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！