八大經(jīng)典排序算法原理及實(shí)現(xiàn)

該系列文章主要是記錄下自己暑假這段時(shí)間的學(xué)習(xí)筆記，暑期也在實(shí)習(xí)，抽空學(xué)了很多，每個(gè)方面的知識(shí)我都會(huì)另起一篇博客去記錄，每篇頭部主要是另起博客的鏈接。

JavaSE集合（已寫(xiě)）

JavaEE框架（未寫(xiě)）

虛擬機(jī)JVM運(yùn)行時(shí)區(qū)域及垃圾回收（已寫(xiě)）

Java并發(fā)（未寫(xiě)）

計(jì)算機(jī)網(wǎng)絡(luò)（已寫(xiě)）

八大經(jīng)典排序算法原理及實(shí)現(xiàn)（已寫(xiě)）

一、冒泡排序

1.1 冒泡排序原理

冒泡排序算法應(yīng)該是大家第一個(gè)接觸的算法，其原理都應(yīng)該懂，但我還是想以自己的語(yǔ)言來(lái)敘述下其步奏：

  • 第一輪從下標(biāo)為 0 到 n-1 的元素.即（0，n-1）,依次比較相鄰兩個(gè)元素，把最大（或最?。┑臄?shù)移動(dòng)到最右邊位置，即下標(biāo)為 n-1處
  • 第二輪再?gòu)南聵?biāo)為 0 到 n-2 的元素.即（0，n-2），依次比較相鄰兩個(gè)元素，把最大（或最小）的數(shù)移動(dòng)到 最右邊-1 位置，即下標(biāo)為 n-2 處
  • 一值重復(fù) n躺 即可達(dá)到排序效果
int[] bubbleSort(int[] arr){
    // 因?yàn)樾枰貜?fù)n躺，所以 i < arr.length
    for(int i = 0; i < arr.length; i++){
        // 這里由于是將最大或最小的數(shù)放在右邊，所以 j < arr.length - i
        for(int j = 1; j < arr.length - i; j++){
            // 如果前第一個(gè)數(shù)大于后一個(gè)數(shù)，則交換
            if(a[j-1] > a[j]){
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
    return arr;
}

1.2 冒牌時(shí)間復(fù)雜度分析

  • 這里嵌套兩層 for 循環(huán)，外層循環(huán) n 次；
  • 內(nèi)層最多時(shí)循環(huán) n - 1次、最少循環(huán) 0 次，平均循環(huán)(n-1)/2；
  • 所以循環(huán)體內(nèi)總的比較交換次數(shù)為：n*(n-1) / 2 = (n^2-n)/2

按照計(jì)算時(shí)間復(fù)雜度的規(guī)則，去掉常數(shù)、去掉最高項(xiàng)系數(shù)，其復(fù)雜度為O(N^2)
冒泡排序及其復(fù)雜度分析

1.3 冒泡排序空間復(fù)雜度分析

空間復(fù)雜度就是在交換元素時(shí)那個(gè)臨時(shí)變量所占的內(nèi)存

  • 最優(yōu)的空間復(fù)雜度為開(kāi)始元素已排序，則空間復(fù)雜度為 0；
  • 最差的空間復(fù)雜度為開(kāi)始元素為逆排序，則空間復(fù)雜度為 O(N);
  • 平均的空間復(fù)雜度為O(1)

1.4 冒泡排序算法的改進(jìn)

給定一個(gè)整數(shù)序列{6,1,2,3,4},每完成一次外層循環(huán)的結(jié)果為：

6,1,2,3,4
1,2,3,4,6 此時(shí) i = 0；
1,2,3,4,6 此時(shí) i = 1；
1,2,3,4,6 此時(shí) i = 2；
1,2,3,4,6 此時(shí) i = 3；

我們發(fā)現(xiàn)第一次外層循環(huán)之后就排序成功了，但是還是會(huì)繼續(xù)循環(huán)下去，造成了不必要的時(shí)間復(fù)雜度，怎么優(yōu)化？

  • 給定一個(gè) 整數(shù)型標(biāo)識(shí)符 flag ,當(dāng)某次外層循環(huán)中，內(nèi)循環(huán)里沒(méi)有發(fā)生相鄰元素的交換，則表示當(dāng)前數(shù)組已排序成功，直接跳出外層循環(huán)。
  • 所以最好的情況時(shí)間復(fù)雜度為O(N)
// 改進(jìn)的冒泡排序算法
int[] bubbleSort(int[] arr){
    int flag ;    
    for(int i = 0; i < arr.length; i++){
        flag = 0;
        for(int j = 1; j < arr.length - i; j++){
            if(a[j-1] > a[j]){
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                flag = 1;
            }
        }
        // flag = 0 ,則表示內(nèi)層循環(huán)中，沒(méi)有發(fā)生相鄰元素的交換，即已排序，直接跳出外層循環(huán)
        if(flag == 0)
            break;
    }
    return arr;
}

1.4 穩(wěn)定性分析

  • 穩(wěn)定性：排序后對(duì)于那些值相同的元素其相對(duì)位置沒(méi)有發(fā)生變化

冒泡排序都是相鄰元素的比較，當(dāng)相鄰元素相等時(shí)并不會(huì)交換，因此冒泡排序算法是穩(wěn)定性算法

二、插入排序

插入排序是對(duì)冒泡排序的一種改進(jìn)

2.1插入排序原理

插入排序的思想是數(shù)組是部分有序的，再將無(wú)序的部分插入有序的部分中去,如圖：
（圖片來(lái)自這里）

插入排序
插入排序

int[] insertionSort(int[] a){
    for (int i = 0; i < a.length-1; i++) {
        // 第i+1個(gè)元素插入到前i個(gè)已排序數(shù)中
        for(int j = i + 1; j >= 0; j--) {
            if(a[j] < a[j-1]){
                int temp = a[j];
                a[j] = a[j-1];
                a[j-1] = temp;
            }
        }
    }
    return a;
}

2.2 時(shí)間復(fù)雜度分析

  • 如上代碼。兩次for循環(huán)，第一層是循環(huán) n 次；
  • 第二層循環(huán)中，最好循環(huán) 1 次，最壞循環(huán) n 次，平均循環(huán)（n-1）/2次
  • 所以總的循環(huán)體內(nèi)比較的平均次數(shù)為（n^2-n）/ 2，按照時(shí)間復(fù)雜度的計(jì)算規(guī)則，其平均時(shí)間時(shí)間復(fù)雜度為O(N)

2.3 空間復(fù)雜度分析

空間復(fù)雜度就是在交換元素時(shí)那個(gè)臨時(shí)變量所占的內(nèi)存

  • 最優(yōu)的空間復(fù)雜度為開(kāi)始元素已排序，則空間復(fù)雜度為 0；
  • 最差的空間復(fù)雜度為開(kāi)始元素為逆排序，則空間復(fù)雜度最壞時(shí)為 O(N);
  • 平均的空間復(fù)雜度為O(1)

2.4 插入排序的優(yōu)化

插入排序的優(yōu)化，有兩種方案：

  • 希爾插入排序
  • 二分插入排序

文章后面會(huì)給出這兩種排序算法

2.5 插入排序的穩(wěn)定性

由于插入排序也是相鄰元素的比較，遇到相等的相鄰元素時(shí)不會(huì)發(fā)生交換，也不會(huì)造成相等元素之間的相對(duì)位置發(fā)生變化

三、選擇排序

3.1 選擇排序原理

其原理是從未排序的元素中選出最小值(最大值)放在已排序元素的后面

  • 第一輪從下標(biāo)為 1 到下標(biāo)為 n-1 的元素中選取最小值，若小于第一個(gè)數(shù)，則交換
  • 第二輪從下標(biāo)為 2 到下標(biāo)為 n-1 的元素中選取最小值，若小于第二個(gè)數(shù)，則交換
  • 依次類(lèi)推下去......
```
int[] selectionSort(int[] a,int n) {
        for (int i = 0; i < a.length; i++) {
            int min = a[i]; //每次循環(huán)默認(rèn)第i個(gè)元素為最小值
            int num = i; // num 用來(lái)記錄未排序元素里面的最小值下標(biāo)
            for(int j = i+1; j < a.length; j++){
                if(a[j] < min){
                    min = a[j];
                    num = j;
                }
            }
            // num != i，則表示已在無(wú)排序元素里選到比a[i]更小的值
            if(num != i){
                a[num] = a[i];
                a[i] = min;
            }
        }
        return a;
    }

```

3.2 選擇排序時(shí)間復(fù)雜度

  • 外層循環(huán) n 次；
  • 內(nèi)層循環(huán)中，最壞循環(huán) n-1 次，最好循環(huán) 0 次，平均循環(huán) (n-1)/2 次
  • 整個(gè)循環(huán)體中循環(huán) (n^2 - n) / 2 次，所以平均時(shí)間復(fù)雜度為 O(N)

3.3 選擇排序空間復(fù)雜度

空間復(fù)雜度就是在交換元素時(shí)那個(gè)臨時(shí)變量所占的內(nèi)存

  • 最優(yōu)的空間復(fù)雜度為開(kāi)始元素已排序，則空間復(fù)雜度為 0；
  • 最差的空間復(fù)雜度為開(kāi)始元素為逆排序，則空間復(fù)雜度最壞時(shí)為 O(N);
  • 平均的空間復(fù)雜度為O(1)

3.4 選擇排序的優(yōu)化

3.5 選擇排序的穩(wěn)定性

選擇排序是不穩(wěn)定的，比如 3 6 3 2 4，第一次外層循環(huán)中就會(huì)交換第一個(gè)元素3和第四個(gè)元素2，那么就會(huì)導(dǎo)致原序列的兩個(gè)3的相對(duì)位置發(fā)生變化

四、希爾排序

希爾排序算是改良版的插入排序算法，所以也稱(chēng)為希爾插入排序算法

4.1 希爾排序算法原理

其原理是將序列分割成若干子序列（由相隔某個(gè)增量的元素組成的），分別進(jìn)行直接插入排序；接著依次縮小增量繼續(xù)進(jìn)行排序，待整個(gè)序列基本有序時(shí)，再對(duì)全體元素進(jìn)行插入排序，我們知道當(dāng)序列基本有序時(shí)使用直接插入排序的效率很高。
上述描述只是其原理，真正的實(shí)現(xiàn)可以按下述步奏來(lái)：

  • 以 32 43 24 18 49 28 10 59 18 41 序列為例
  • 第一次 gap = 10 / 2 = 5；則從第6個(gè)元素開(kāi)始，依次與前面相距間隔為5的元素比較

32 43 24 18 49 28 10 59 18 41 —> 28 43 24 18 49 32 10 59 18 41
28 43 24 18 49 32 10 59 18 41 —> 28 10 24 18 49 32 43 59 18 41
28 10 24 18 49 32 43 59 18 41 —> 28 10 24 18 49 32 43 59 18 41
28 10 24 18 49 32 43 59 18 41 —> 28 10 24 18 49 32 43 59 18 41
28 10 24 18 49 32 43 59 18 41 —> 28 10 24 18 41 32 43 59 18 49

  • 這樣第一趟就得到 28 10 24 18 41 32 43 59 18 49 的序列，后面再縮小 gap = gap / 2 = 2，同上述步驟一樣依次與前面相距間隔為 2 的元素就行比較
    int[] shellSort(int[] A, int n){
        int gap = n/2;// 初始步長(zhǎng)
        while(gap > 0){
            // 從數(shù)組下標(biāo)為 gap的元素開(kāi)始排序
            for(int i = gap; i < n; i++){ 
                // 每個(gè)元素只與自己組內(nèi)的元素進(jìn)行直接排序，組內(nèi)相鄰元素比較
                for(int j = i-gap; j>=0 ; j -= gap){
                    if (A[j] > A[j+gap]) {
                        int temp = A[j+gap];
                        A[j+gap] = A[j];
                        A[j] = temp;
                    }
                }
            }
            gap /= 2;
        }
        return A;
    }

4.2 希爾排序時(shí)間復(fù)雜度分析

希爾排序的效率取決于增量值gap的選取，這涉及到數(shù)學(xué)上尚未解決的難題，但是某些序列中復(fù)雜度可以為O(N1.3)，當(dāng)然最好肯定是O(N)，最壞是O(N2)

4.3 希爾排序空間復(fù)雜度分析

空間復(fù)雜度就是在交換元素時(shí)那個(gè)臨時(shí)變量所占的內(nèi)存

  • 最優(yōu)的空間復(fù)雜度為開(kāi)始元素已排序，則空間復(fù)雜度為 0；
  • 最差的空間復(fù)雜度為開(kāi)始元素為逆排序，則空間復(fù)雜度最壞時(shí)為 O(N);
  • 平均的空間復(fù)雜度為O(1)

4.4 希爾排序的優(yōu)化

4.5 希爾排序的穩(wěn)定性

希爾排序并不只是相鄰元素的比較，有許多跳躍式的比較，難免會(huì)出現(xiàn)相同元素之間的相對(duì)位置發(fā)生變化，所以希爾排序是不穩(wěn)定的

五、堆排序

5.1 什么是堆？

理解堆排序，就必須得先知道什么是堆？

  • 堆一般指的是二叉堆，顧名思義，二叉堆是完全二叉樹(shù)或者近似完全二叉樹(shù)

二叉樹(shù)的特點(diǎn)：

  • 父結(jié)點(diǎn)的鍵值總是小于（大于）任何一個(gè)子結(jié)點(diǎn)
  • 每一個(gè)結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)都是一個(gè)二叉堆

當(dāng)父節(jié)點(diǎn)的值總是大于子結(jié)點(diǎn)時(shí)為最大堆；反之為最小堆，下圖就為一個(gè)二叉堆

最小堆示例

5.1.1 堆的存儲(chǔ)

一般用數(shù)組來(lái)表示堆，下標(biāo)為 i 的結(jié)點(diǎn)的父結(jié)點(diǎn)下標(biāo)為(i-1)/2；其左右子結(jié)點(diǎn)分別為 (2i + 1)、(2i + 2)

5.1.2 堆調(diào)整

怎么將給定的數(shù)組序列按照堆的性質(zhì)，調(diào)整為堆？

// 從節(jié)點(diǎn)i開(kāi)始調(diào)整，n為節(jié)點(diǎn)總數(shù) 從0開(kāi)始計(jì)算 i 的子節(jié)點(diǎn)為 2*i+1 和 2*i+2,父節(jié)點(diǎn)為(i-1)/2
    void heapAdjust(int[] data, int i, int n) {
        int temp = data[i];
        int childLeft = 2 * i + 1;
        int childRight = 2 * i + 2;
        while (childLeft < n) {
            // 先從兩個(gè)子節(jié)點(diǎn)中選擇最小的    
            if (childRight < n && data[childRight] < data[childLeft])
                childLeft++;

            // 如果子節(jié)點(diǎn)大于父節(jié)點(diǎn)，則退出
            if (data[childLeft] >= temp)
                break;
            // 如果子節(jié)點(diǎn)小于父節(jié)點(diǎn)，則交換
            else {
                data[i] = data[childLeft];
                i = childLeft;
                childLeft = 2 * i + 1;
                childRight = 2 * i + 2;
            }
        }
        data[i] = temp;
    }

5.2 建立堆

這里以建立最小堆為示例，



很明顯對(duì)于其葉子結(jié)點(diǎn)來(lái)說(shuō)，已經(jīng)是一個(gè)合法的子堆，所以做堆調(diào)整時(shí)，子節(jié)點(diǎn)沒(méi)有必要進(jìn)行，這里只需從結(jié)點(diǎn)為A[4] = 50的結(jié)點(diǎn)開(kāi)始做堆調(diào)整，即從（n/2 - 1）位置處向上開(kāi)始做堆調(diào)整：


    // 建立最小堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        // 調(diào)用堆調(diào)整函數(shù)
        heapAdjust(A, i, n);
    }

5.3 堆排序

  • 堆排序其實(shí)就是將序列建立堆之后，將堆頂元素和堆尾第 n-i 位置元素交換，再做 (0,n-i) 堆調(diào)整；
  • 循環(huán) n 次之后，即完成排序;
  • 由于每次都是將最小的數(shù)據(jù)并入到后面的有序區(qū)間，故操作完成后整個(gè)數(shù)組就有序了。有點(diǎn)類(lèi)似于直接選擇排序
    for (int i = 1; i < n; i++) {
        // 調(diào)換第一個(gè)數(shù)和最后一個(gè)數(shù)
        swap(A, 0, n - i);
        // 調(diào)整堆
        heapAdjust(A, 0, n - i);
    }

5.4 堆排序整個(gè)完整代碼：

    int[] heapSort(int[] A, int n) {
        // 首先建立最小堆，父節(jié)點(diǎn)若大于等于0，則調(diào)整堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapAdjust(A, i, n);
        }
        for (int i = 1; i < n; i++) {
            // 調(diào)換第一個(gè)數(shù)和最后一個(gè)數(shù)
            swap(A, 0, n - i);
            // 調(diào)整堆
            heapAdjust(A, 0, n - i);
        }
        return A;
    }

    // 從節(jié)點(diǎn)i開(kāi)始調(diào)整，n為節(jié)點(diǎn)總數(shù) 從0開(kāi)始計(jì)算 i的子節(jié)點(diǎn)為 2*i+1 和 2*i+2,父節(jié)點(diǎn)為(i-1)/2
    void heapAdjust(int[] data, int i, int n) {
        int temp = data[i];
        int childLeft = 2 * i + 1;
        int childRight = 2 * i + 2;
        while (childLeft < n) {
            // 先從兩個(gè)子節(jié)點(diǎn)中選擇最小的    
            if (childRight < n && data[childRight] < data[childLeft])
                childLeft++;

            // 如果子節(jié)點(diǎn)大于父節(jié)點(diǎn)，則退出
            if (data[childLeft] >= temp)
                break;
            // 如果子節(jié)點(diǎn)小于父節(jié)點(diǎn)，則交換
            else {
                data[i] = data[childLeft];
                i = childLeft;
                childLeft = 2 * i + 1;
                childRight = 2 * i + 2;
            }
        }
        data[i] = temp;
    }
    void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

5.5 堆排序的時(shí)間復(fù)雜度

由于每次重新恢復(fù)堆的時(shí)間復(fù)雜度為O(logN)，共N - 1次重新恢復(fù)堆操作，再加上前面建立堆時(shí)N / 2次向下調(diào)整，每次調(diào)整時(shí)間復(fù)雜度也為O(logN)，二次操作時(shí)間相加還是O(N logN)。故堆排序的時(shí)間復(fù)雜度為O(N * logN)。

5.6 堆排序的空間復(fù)雜度

空間復(fù)雜度就是在交換元素時(shí)那個(gè)臨時(shí)變量所占的內(nèi)存

  • 最優(yōu)的空間復(fù)雜度為開(kāi)始元素已排序，則空間復(fù)雜度為 0；
  • 最差的空間復(fù)雜度為開(kāi)始元素為逆排序，則空間復(fù)雜度最壞時(shí)為 O(N);
  • 平均的空間復(fù)雜度為O(1)

5.7 堆排序的優(yōu)化

5.8 堆排序的穩(wěn)定性

由于堆排序也是跨越式的交換數(shù)據(jù)，會(huì)導(dǎo)致相同元素之間的相對(duì)位置發(fā)生變化，則算法不穩(wěn)定。比如 5 5 5 ,堆化數(shù)組后將堆頂元素5與堆尾元素5交換，使得第一個(gè)5和第三個(gè)5的相對(duì)位置發(fā)生變化

六、歸并排序

6.1 歸并排序的原理

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。

  • 顧名思義，我們先看看遞歸操作，其目的是為了將序列一直劃分到 n 個(gè)子序列，再將相鄰兩個(gè)子序列進(jìn)行合并
    // 劃分序列
    void sort(int[] data, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;
            // 遞歸劃分序列
            sort(data, left, middle);
            sort(data, middle + 1, right);
            // 合并
            merge(data, middle, left, right);
        }
    }

  • 遞歸理解可以看這張圖：


  • 再看合并操作，將兩個(gè)已排序的兩個(gè)數(shù)組合并到一個(gè)數(shù)組里。著了采用了一個(gè)臨時(shí)數(shù)組來(lái)存儲(chǔ)元素，所以會(huì)導(dǎo)致該排序算法的空間復(fù)雜度為O(N)

    // 合并相鄰兩個(gè)數(shù)組
void merge(int[] data, int middle, int left, int right) {
    int leftIndex = left; // 定義左邊數(shù)組的第一個(gè)下標(biāo)
    int rightIndex = middle + 1; // 定義右邊數(shù)組的第一個(gè)下標(biāo)
    int[] tempArray = new int[right - left + 1]; // 定義一個(gè)暫時(shí)存儲(chǔ)的數(shù)組
    int tempIndex = 0; // 定義暫存數(shù)組的下標(biāo)
    while (leftIndex <= middle && rightIndex <= right) {
        if (data[leftIndex] <= data[rightIndex]) {
            tempArray[tempIndex++] = data[leftIndex++];
        } else {
            tempArray[tempIndex++] = data[rightIndex++];
        }
    }
    // 剩下的直接放入
    while (leftIndex <= middle) {
        tempArray[tempIndex++] = data[leftIndex++];
    }
    while (rightIndex <= right) {
        tempArray[tempIndex++] = data[rightIndex++];
    }
    // 返回?cái)?shù)組給data
    int temp = 0;
    while ((left + temp) <= right) {
        data[left + temp] = tempArray[temp];
        temp++;
    }
}

6.2 歸并排序時(shí)間復(fù)雜度分析

  • 因?yàn)椴还茉卦谑裁辞闆r下都要做這些步驟，所以花銷(xiāo)的時(shí)間是不變的，所以該算法的最優(yōu)時(shí)間復(fù)雜度和最差時(shí)間復(fù)雜度及平均時(shí)間復(fù)雜度都是一樣的為：O( nlogn )

6.3 歸并排序空間復(fù)雜度分析

  • 歸并的空間復(fù)雜度就是那個(gè)臨時(shí)的數(shù)組和遞歸時(shí)壓入棧的數(shù)據(jù)占用的空間：n + logn；所以空間復(fù)雜度為: O(n)
  • 以時(shí)間換空間：網(wǎng)上很多blog分享空間復(fù)雜度只有O(1)的歸并排序法；因?yàn)閭鹘y(tǒng)的歸并排序所消耗的空間主要是在歸并函數(shù)（把兩個(gè)有序的函數(shù)合并成一個(gè)有序的函數(shù)），所以如果要讓空間復(fù)雜度為 O(1) ，那么也只能在歸并函數(shù)中做文章了。其主要思想就是借助于快速排序（其實(shí)就是相當(dāng)于歸并函數(shù)被快速排序函數(shù)替換了）；這樣的方法雖然可以減少內(nèi)存的消耗，但是卻會(huì)在時(shí)間上帶來(lái)?yè)p失，因?yàn)檫@樣時(shí)間復(fù)雜度卻變成了 O(n^2) 了；所以這種方法并不是一個(gè)兩全其美的idea；

6.4 歸并排序的穩(wěn)定性

  • 歸并排序算法中，歸并最后到底都是相鄰元素之間的比較交換，并不會(huì)發(fā)生相同元素的相對(duì)位置發(fā)生變化，故是穩(wěn)定性算法

七、快速排序

快速排序在應(yīng)該是大家經(jīng)?？吹?、聽(tīng)到的算法，但是真正默寫(xiě)出來(lái)是有難度的。希望大家看了下面挖坑填數(shù)方法后，能快速寫(xiě)出、快速排序。

7.1 快速排序原理

  • 先從序列中選取一個(gè)數(shù)做為基準(zhǔn)數(shù)；
  • 再遍歷原序列，大于這個(gè)基準(zhǔn)數(shù)的放在右邊，小于這個(gè)基準(zhǔn)數(shù)的方法在左邊
  • 再對(duì)左右兩邊分別進(jìn)行上述兩個(gè)步驟，直到各個(gè)區(qū)間只有一個(gè)數(shù)

其原理就這么幾句話，但是現(xiàn)實(shí)起來(lái)并不是這么簡(jiǎn)單，我們采取流行的一種方式挖坑填數(shù)分治法

7.2 挖坑填數(shù)分治法

對(duì)于序列： 72 6 57 88 60 42 83 73 48 85

  • 初始時(shí)，i = 0; j = 9; X = a[i] = 72
  • 由于已經(jīng)將a[0]中的數(shù)保存到X中，可以理解成在數(shù)組a[0]上挖了個(gè)坑，可以將其它數(shù)據(jù)填充到這來(lái)。
  • 從j開(kāi)始向前找一個(gè)比X小或等于X的數(shù)。當(dāng)j=8，符合條件，將a[8]挖出再填到上一個(gè)坑a[0]中。a[0]=a[8]; i++; 這樣一個(gè)坑a[0]就被搞定了，但又形成了一個(gè)新坑a[8]，這怎么辦了？簡(jiǎn)單，再找數(shù)字來(lái)填a[8]這個(gè)坑。這次從i開(kāi)始向后找一個(gè)大于X的數(shù)，當(dāng)i=3，符合條件，將a[3]挖出再填到上一個(gè)坑中a[8]=a[3]; j--;

數(shù)組變?yōu)椋?strong>48 6 57 88 60 42 83 73 88 85
再重復(fù)上面的步驟，先從后向前找，再?gòu)那跋蚝笳遥?/p>

  • 從j開(kāi)始向前找，當(dāng)j=5，符合條件，將a[5]挖出填到上一個(gè)坑中，a[3] = a[5]; i++;
  • 從i開(kāi)始向后找，當(dāng)i=5時(shí)，由于i==j退出。
  • 此時(shí)，i = j = 5，而a[5]剛好又是上次挖的坑，因此將X填入a[5]。

數(shù)組變?yōu)椋?strong>48 6 57 42 60 72 83 73 88 85
可以看出a[5]前面的數(shù)字都小于它，a[5]后面的數(shù)字都大于它。因此再對(duì)a[0…4]和a[6…9]這二個(gè)子區(qū)間重復(fù)上述步驟就可以了

挖坑填數(shù)法總結(jié)

  • i =L; j = R; 將基準(zhǔn)數(shù)挖出形成第一個(gè)坑a[i]。
  • j--由后向前找比它小的數(shù)，找到后挖出此數(shù)填前一個(gè)坑a[i]中。
  • i++由前向后找比它大的數(shù)，找到后也挖出此數(shù)填到前一個(gè)坑a[j]中。
  • 再重復(fù)執(zhí)行2，3二步，直到i==j，將基準(zhǔn)數(shù)填入a[i]中。
public  int[] quickSort(int[] A, int n) {
        // write code here
        sort(A, 0, n - 1);
        return A;
    }

    void sort(int[] data, int left, int right) {
        if(left < right){
            int i = left;
            int j = right;
            int x = data[i];// data[i]即 data的第一個(gè)坑
            while(i < j){
                // 先從右到左找小于 x 的數(shù)來(lái)填坑 data[i]
                while(i < j && data[j] >= x)
                    j--;
                if (i < j) {
                    // data[j] 填入到 坑中，且data[j]形成新坑
                    data[i++] = data[j];
                }
                // 再?gòu)淖蟮接姓掖笥?x 的數(shù)來(lái)填坑 data[j]
                while(i < j && data[i] < x)
                    i++;
                if (i < j) {
                    // data[j] 填入到 坑中，且data[i]形成新坑
                    data[j--] = data[i];
                }
            }
            // 當(dāng) i=j 時(shí)，退出while循環(huán)，此時(shí)將 x 填入到坑data[i]中
            data[i] = x; 
            sort(data, left, i-1);
            sort(data, i+1, right);
        }
    }

7.3 快速排序時(shí)間復(fù)雜度

  • 在最優(yōu)的情況下，快速排序算法的時(shí)間復(fù)雜度為O(NlogN)
  • 在最壞的情況下，待排序的序列為正序或者逆序，快速排序算法的時(shí)間復(fù)雜度為O(N)

7.4 快速排序空間復(fù)雜度

空間復(fù)雜度，主要是遞歸造成的?？臻g的使用:

  • 最好情況，遞歸樹(shù)的深度為log2n，其空間復(fù)雜度也就為O(logn);
  • 最壞情況，需要進(jìn)行n‐1遞歸調(diào)用，其空間復(fù)雜度為O(n);
  • 平均情況，空間復(fù)雜度也為O(logn)。

7.5 快速排序的優(yōu)化

快速排序的優(yōu)化主要在于基準(zhǔn)數(shù)的選取

7.6 快速排序的穩(wěn)定性

快速排序也是跨越式比較及交換數(shù)據(jù)，易導(dǎo)致相同元素之間的相對(duì)位置發(fā)生變化，所以快速排序不穩(wěn)定

八、二分排序

8.1 二分查找排序原理

前面也說(shuō)了二分查找排序是改進(jìn)的插入排序，不同之處在于，在有序區(qū)間查找新元素插入位置時(shí)，為了減少比較次數(shù)提高效率，采用二分查找算法進(jìn)行插入位置的確定
具體步驟，設(shè)數(shù)組為a[0…n]：

  1. 將原序列分成有序區(qū)和無(wú)序區(qū)。a[0…i-1]為有序區(qū)，a[i…n] 為無(wú)序區(qū)。（i從1開(kāi)始）
  2. 從無(wú)序區(qū)中取出第一個(gè)元素，即a[i]，使用二分查找算法在有序區(qū)中查找要插入的位置索引j。
  3. 將a[j]到a[i-1]的元素后移，并將a[i]賦值給a[j]。
  4. 重復(fù)步驟2~3，直到無(wú)序區(qū)元素為0個(gè)。
    static void binarySort(int[] arr, int n){
        for (int i = 1; i < n; i++){
            int temp = arr[i];
            int low = 0; // 有序區(qū)域最小位置
            int high = i-1; // 有序區(qū)域最大位置
            int mid = -1;
            // 二分查找插入位置
            while (low <= high){
                mid = low + (high - low)/ 2;
                if (temp >= arr[mid]) { // 相等的元素也是插在后面
                    low = mid + 1;
                }else {
                    high = mid - 1;    
                }
            }
            // 向后移動(dòng)數(shù)據(jù)
            for (int j = i - 1; j >= low; j--) 
                arr[j+1] = arr[j];
            arr[low] = temp; // 插入temp
        }
    }

8.2 二分插入排序的時(shí)間復(fù)雜度

二分查找插入位置，因?yàn)椴皇遣檎蚁嗟戎?，而是基于比較查插入合適的位置，所以必須查到最后一個(gè)元素才知道插入位置。
二分查找最壞時(shí)間復(fù)雜度：當(dāng)2^X>=n時(shí)，查詢結(jié)束，所以查詢的次數(shù)就為x，而x等于log2n（以2為底，n的對(duì)數(shù)）。即O(log2n)
所以，二分查找排序比較次數(shù)為：x=log2n
二分查找插入排序耗時(shí)的操作有：比較 + 后移賦值。時(shí)間復(fù)雜度如下：

  • 最好情況：查找的位置是有序區(qū)的最后一位后面一位，則無(wú)須進(jìn)行后移賦值操作，其比較次數(shù)為：log2n 。即O(log2n)
  • 最壞情況：查找的位置是有序區(qū)的第一個(gè)位置，則需要的比較次數(shù)為：log2n，需要的賦值操作次數(shù)為n(n-1)/2加上 (n-1) 次。即O(n^2)
  • 漸進(jìn)時(shí)間復(fù)雜度（平均時(shí)間復(fù)雜度）：O(n^2)

8.3 二分插入排序的空間復(fù)雜度

  • 從實(shí)現(xiàn)原理可知，二分查找插入排序是在原輸入數(shù)組上進(jìn)行后移賦值操作的（稱(chēng)“就地排序”），所需開(kāi)辟的輔助空間跟輸入數(shù)組規(guī)模無(wú)關(guān)，所以空間復(fù)雜度為：O(1)

8.4 二分插入排序的穩(wěn)點(diǎn)性

二分查找排序在交換數(shù)據(jù)時(shí)時(shí)進(jìn)行移動(dòng)，當(dāng)遇到有相等值插入時(shí)也只會(huì)插入其后面，不會(huì)影響其相等元素之間的相對(duì)位置，所以是穩(wěn)定的

各個(gè)排序算法的比較

各種排序算法的比較

各個(gè)算法的聯(lián)系

感謝MoreWindows提供的圖

最后感謝以下內(nèi)容

白話經(jīng)典算法排序
冒泡排序選擇排序
快速排序復(fù)雜度分析
優(yōu)化的插入排序

未完，持續(xù)更新中......

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 概述 排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部...
    蟻前閱讀 5,297評(píng)論 0贊 52
  • 概述：排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部...
    每天刷兩次牙閱讀 3,818評(píng)論 0贊 15
  • 概述排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的...
    Luc_閱讀 2,370評(píng)論 0贊 35
  • 我不知道你現(xiàn)在在經(jīng)歷著怎樣的辛苦，挑燈夜戰(zhàn)或是忙于生計(jì)。到了某個(gè)年紀(jì)后，再看人生，其實(shí)是沒(méi)有“巔峰”可言的...
    波妞c閱讀 204評(píng)論 0贊 0
  • 【每日一思】注意力是每個(gè)人可控制的稀缺資源，今天請(qǐng)你和我玩一個(gè)項(xiàng)目，叫做：記錄你的注意力開(kāi)銷(xiāo)。讓我們看看你在這一天...
    柚子粒閱讀 245評(píng)論 0贊 0

友情鏈接更多精彩內(nèi)容