Java數(shù)據(jù)結(jié)構(gòu)之常見排序算法（下）

更新時(shí)間：2023年01月08日 15:06:57 作者：程序猿教你打籃球

這篇文章主要介紹了Java數(shù)據(jù)結(jié)構(gòu)之常見排序算法（下），與之相對(duì)有（上），想了解的朋友可以去本網(wǎng)站掃搜，在這兩篇文章里涵蓋關(guān)于八大排序算法的所有內(nèi)容,需要的朋友可以參考下

上期回顧

上期我們主要介紹了排序的基本認(rèn)識(shí)，以及四個(gè)排序，分別是直接插入排序，希爾排序，選擇排序，堆排序，從這些排序中，了解了算法的實(shí)現(xiàn)，以及復(fù)雜度，和排序穩(wěn)定性的相關(guān)知識(shí)。

本期我們將繼續(xù)講解剩下的排序內(nèi)容。

注：后續(xù)所說的復(fù)雜度 log，都是以2為底，特殊的會(huì)標(biāo)注出來。

冒泡排序

這個(gè)排序肯定是見多不怪了，我記得我在學(xué)校學(xué)習(xí)C語言的階段，第一個(gè)接觸的排序就是冒泡排序，它本身也是個(gè)很簡(jiǎn)單的排序，這里就直接上代碼了：

public void bubbleSort(int[] array) {
    // 外循環(huán)控制比較的趟數(shù)
    for (int i = 0; i < array.length - 1; i++) {
        boolean flag = true;
        // 內(nèi)循環(huán)控制需要比較的元素個(gè)數(shù)
        for (int j = 0; j < array.length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
                flag = false;
            }
        }
        if (flag) {
            return;
        }
    }
}

不過這里我們需要注意，此處采用的 flag 是對(duì)該排序做的一種優(yōu)化，如果當(dāng)進(jìn)入內(nèi)循環(huán)之后，發(fā)現(xiàn)沒有發(fā)生交換，則表示此時(shí)的數(shù)據(jù)已經(jīng)有序了，不需要接著去比較了。

時(shí)間復(fù)雜度分析：這個(gè)排序就很簡(jiǎn)單了，O(n^2)
空間復(fù)雜度分析：O(1)
穩(wěn)定性：穩(wěn)定

快速排序

這個(gè)排序算是我們比較重要的一個(gè)排序了，快速排序是Hoare在1962年提出的一種二叉樹結(jié)構(gòu)的交換排序法，如果你還沒有接觸過二叉樹相關(guān)的知識(shí)，可以先去本網(wǎng)站的相關(guān)二叉樹文章中學(xué)習(xí)學(xué)習(xí)。

理解快速排序的二叉樹結(jié)構(gòu)

如何理解快速排序的二叉樹結(jié)構(gòu)呢？

可以這樣來想象一下：

你面前有一組數(shù)字，令第一個(gè)數(shù)作為基準(zhǔn)值，你需要將這個(gè)基準(zhǔn)值放到某個(gè)位置上，滿足基準(zhǔn)值的左邊都比這個(gè)基準(zhǔn)值小，右邊都比基準(zhǔn)值大，因此由基準(zhǔn)值為界限又被劃為了左右兩個(gè)區(qū)間，這兩個(gè)區(qū)間再次重復(fù)上述的操作。

這樣一來就可以看作一棵二叉樹！

而如何確定基準(zhǔn)值的位置，這就是我們快速排序要實(shí)現(xiàn)的算法！

本期我們一共會(huì)講解三種版本，方便大家學(xué)習(xí)快速排序。

下面我們就用一張圖，來描述下上述我們所說的理論部分。

這里先不關(guān)心博主畫圖用的是哪種版本的方法，主要來驗(yàn)證下我們上面所說的，每個(gè)區(qū)間所找的基準(zhǔn)值，最終放到固定位置之后，基準(zhǔn)值的左邊比它小，基準(zhǔn)值的右邊比它大。

最終我們來從左往右看上圖，其實(shí)就排序成功了。

當(dāng)然光看圖可能了解的不是很通透，那么下面，我們結(jié)合著這張圖，來實(shí)現(xiàn)快速排序的三種算法。

為了實(shí)參傳遞的統(tǒng)一性，我們快速排序的形參統(tǒng)一為以下格式，調(diào)用被封裝的 quick 方法：

public void quickSort(int[] array) { 
    quick(array, 0, array.length - 1);
}

Hoare 法

我上面畫的那幅圖就是 Hoare 法，主要邏輯是，令區(qū)間第一個(gè)數(shù)為基準(zhǔn)值，定義兩個(gè)變量，分別表示區(qū)間左邊起始位置下標(biāo)，和右邊起始位置下標(biāo)(區(qū)間最后一個(gè)數(shù)的下標(biāo))，先從右邊開始找比基準(zhǔn)值小的，再去左邊找比基準(zhǔn)值大的，找到之后，交換這兩個(gè)值，當(dāng)這兩個(gè)下標(biāo)相遇了，就把基準(zhǔn)值與其中一個(gè)下標(biāo)交換即可，這樣就能達(dá)到，基準(zhǔn)值的左邊都比它小，右邊都比它大。

代碼如下：

private void quick(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = partitionHoare(array, left, right);
    quick(array, left, pivot - 1); //左區(qū)間
    quick(array, pivot + 1, right); //右區(qū)間
}
private int partitionHoare(int[] array, int left, int right) {
    int pivot = array[left]; //將該區(qū)間第一個(gè)數(shù)作為基準(zhǔn)值
    int begin = left;
    int end = right;
    while (begin < end) {
        // 右邊找比基準(zhǔn)小的數(shù)的下標(biāo), 為什么要取 >= 呢？
        while (begin < end && array[end] >= pivot) {
            end--;
        }
        // 左邊找比基準(zhǔn)大的數(shù)的下標(biāo)
        while (begin < end && array[begin] <= pivot) {
            begin++;
        }
        // 交換
        swap(array, begin, end);
    }
    swap(array, left, begin);
    return begin; //返回基準(zhǔn)值當(dāng)前所處的下標(biāo), 左邊都比它小, 右邊都比它大
}

單看 quick 方法，有點(diǎn)像二叉樹的前序遍歷，確實(shí)也是這樣的，前面我們也說過，快排是一種二叉樹的結(jié)構(gòu)，結(jié)合著代碼再去看那幅圖，是不是理解的更通透了呢？

這里有兩個(gè)問題，我們來看 partitionHoare 方法實(shí)現(xiàn)里面：

1. 為什么要從右邊開始找？

2. 為什么要取等于號(hào)，直接 > 或 < 不可以嗎？

3. 外面的循環(huán)不是限制了 begin < end 嗎？為什么里面的 while 還要限制呢？

如果左邊作為基準(zhǔn)值的話，只能從右邊開始找，如果從左邊開始找，當(dāng) begin 和 end 相遇之后的值，要比基準(zhǔn)值大，因?yàn)?begin 和 end 交換后，end 位置的值已經(jīng)比基準(zhǔn)值要大了
如果不取等于號(hào)，可能會(huì)造成死循環(huán)，你設(shè)想下不取等于號(hào)時(shí)，區(qū)間里第一個(gè)元素和最后一個(gè)元素相同的情況下。
如果這組數(shù)本來就是升序的呢？右邊 end 找不到比基準(zhǔn)值小的數(shù)，如果基準(zhǔn)就是最小的數(shù)呢？?jī)?nèi)部 whild 不限制的話 end 是不是會(huì)自減成為負(fù)數(shù)？導(dǎo)致下標(biāo)不合法了？

上面這三點(diǎn)或許是小伙伴們有疑問的地方，這里給大家伙解釋一下，那么再來思考個(gè)問題，什么情況下快速排序的效率最低呢？

當(dāng)數(shù)組有序的情況下，快速排序的時(shí)間效率最差！試想一下，如果每次找的基準(zhǔn)值都是最小的話，劃分區(qū)間的時(shí)候，是不是就成了一棵沒有左樹的二叉樹了?。款愃朴谝环N鏈表的結(jié)構(gòu)了，見下圖：

為了解決這種極端情況下，快速排序劃分不均勻的問題，于是便有了三數(shù)取中的算法，這算是對(duì)快速排序的一種優(yōu)化，三數(shù)取中到底是啥，請(qǐng)接著往后看：

三數(shù)取中

三數(shù)取中，是針對(duì)快速排序極端情況下，為了均勻的分割區(qū)間而采用的一種優(yōu)化，其步驟是，取該區(qū)間的第一個(gè)值，最后一個(gè)值，以及該區(qū)間中間位置的值，求出這三個(gè)值中第二大的數(shù)，與第一個(gè)值交換，這樣一來，只要基準(zhǔn)值不是最小的，就一定程度上能使區(qū)間分割的更均勻。

簡(jiǎn)單來說，就是有三個(gè)數(shù)的下標(biāo)，讓你求出第二大的值的下標(biāo)嘛，這個(gè)還是比較簡(jiǎn)單的，我就直接來放代碼了：

private int findMidValOfIndex(int[] array, int left, int right) {
    int mid = (left + right) >> 1;
    if (array[left] < array[right]) {
        if (array[left] < array[mid]) {
            // 走到這里面, left位置一定是最小的值
            // 我們這里只需要判斷 mid 和 right 哪個(gè)位置小即可
            if (array[mid] < array[right]) {
                //mid是第二大的值
                return mid;
            } else {
                return right;
            }
        } else {
            // 走到這里, 則left位置小于等于right位置, 并大于mid位置, 則left是第二大的值
            return left;
        }
    } else { // 走這個(gè)else表示left位置大于等于right位置
        if (array[left] > array[mid]) {
            // 走到這里表示 left 位置一定是最大的值,
            // 我們只需要判斷 mid 和 right 位置哪個(gè)大即可
            if (array[mid] > array[right]) {
                return mid;
            } else  {
                return right;
            }
        } else {
            //走到這表示 left位置大于right位置, 并小于等于mid位置, 則left是第二大的值
            return left;
        }
    }
}

這樣的話，在我們 quick 方法中，求到了第二大值下標(biāo)后，與 left 位置交換下即可：

private void quick(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }
    // 三數(shù)取中
    int mid = findMidValOfIndex(array, left, right);
    swap(array, left, mid);
    int pivot = partitionHoare(array, left, right);
    quick(array, left, pivot - 1);
    quick(array, pivot + 1, right);
}

那這樣一來，我們上面的效率最低的例子是不是就可以得到改善了？

但是這樣優(yōu)化還是不夠，因?yàn)楫?dāng)我們數(shù)據(jù)量夠大的時(shí)候，二叉樹的層數(shù)就越高，而越往后，區(qū)間被分割的越小，里面的數(shù)據(jù)也就越接近有序，但是越接近有序了，還會(huì)往下分割，這樣會(huì)造成大量的壓棧操作，遞歸本身就是在壓棧的過程嘛，為了減少這樣的情況，又有一個(gè)優(yōu)化辦法：小區(qū)間優(yōu)化。

小區(qū)間優(yōu)化

數(shù)據(jù)量大的時(shí)候，分割到區(qū)間越小，則表示數(shù)據(jù)越接近有序了，前面我們認(rèn)識(shí)了一個(gè)數(shù)據(jù)越接近有序效率越快的排序，那就是直接插入排序，所以我們可以進(jìn)行小區(qū)間優(yōu)化，那么簡(jiǎn)單來說，就是當(dāng)區(qū)間的數(shù)據(jù)個(gè)數(shù)小于某個(gè)值的時(shí)候，采用直接插入排序算法。

private void quick(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }
    // 小區(qū)間優(yōu)化 -> 如果待排序的數(shù)據(jù)小于15個(gè),我們直接使用直接插入排序
    if ((right - left + 1) < 15) {
        insertSort(array);
        return;
    }
    // 三數(shù)取中
    int mid = findMidValOfIndex(array, left, right);
    swap(array, left, mid);
    int pivot = partitionHoare(array, left, right);
    quick(array, left, pivot - 1);
    quick(array, pivot + 1, right);
}

時(shí)間復(fù)雜度分析：在我們有了三數(shù)取中優(yōu)化的情況下，可以達(dá)到 O(n*logn)，如果沒有三數(shù)取中，極端最壞的情況下，能達(dá)到 O(n^2)，但是我們通常說的快排都是優(yōu)化過的，也就是 O(n*logn)。
空間復(fù)雜度分析：每次遞歸都會(huì)壓棧，隨之開辟空間，那么快排類似于二叉樹的前序遍歷，左子樹遍歷完了，再有右子樹，也就是會(huì)壓棧，也會(huì)出棧，那么最大壓棧多少呢？顯然是樹的高度，即 O(logn)。
穩(wěn)定性：不穩(wěn)定
快速排序整體的綜合性能和使用場(chǎng)景都是比較好的

到這，快速排序基本上就實(shí)現(xiàn)完成了，但是還有兩個(gè)版本，我們接著往后看。

挖坑法

這個(gè)方法很簡(jiǎn)單，主要思路就是，一樣有兩個(gè)引用，begin 和 end，end 從右找比基準(zhǔn)小的，begin從左找比基準(zhǔn)大的，當(dāng) end 找到比基準(zhǔn)小的，直接覆蓋掉 begin 的位置，接著 begin 找到了比基準(zhǔn)大的接著去覆蓋 end 位置，相遇后，將基準(zhǔn)值覆蓋掉 begin 和 end 任意一個(gè)位置即可。

直接看代碼：

private int partitionPivot(int[] array, int left, int right) {
    int pivot = array[left];
    int begin = left;
    int end = right;
    while (begin < end) {
        while (begin < end && array[end] >= pivot) {
            end--;
        }
        array[begin] = array[end];
        while (begin < end && array[begin] <= pivot) {
            begin++;
        }
        array[end] = array[begin];
    }
    array[begin] = pivot;
    return begin;
}

我們平時(shí)所見到的快速排序，大多數(shù)都是挖坑法居多。

前后指針法

這個(gè)算法用的很少很少，思路就是，定義一個(gè) cur 和 prev，cur 起始位置為 left+1，只要 cur 不大于 right，就往前走，找到比基準(zhǔn)小的值就停下來，與 ++prev 位置的值進(jìn)行交換，這樣一來，比基準(zhǔn)小的值跑到前面來了，cur 走完了之后，再把基準(zhǔn)值與 prev 位置的值交換，也就滿足了基準(zhǔn)值左邊比它小，右邊比它大。

private int partitionPointer(int[] array, int left, int right) {
    int prev = left;
    int cur = left + 1;
    while (cur <= right) {
        // && 后面的避免自己跟自己交換
        if (array[cur] < array[left] && ++prev != cur) {
            swap(array, prev, cur);
        }
        cur++;
    }
    swap(array, left, prev);
    return prev;
}

注意事項(xiàng)

這三種方法，每種方法第一次分割后的結(jié)果可能都不相同，所以未來如果碰到類似讓你求快排第一次分割后結(jié)果的序列，優(yōu)先考慮挖坑法，再Hoare法，最后考慮前后指針法。

但是博主還是希望看到這篇文章的小伙伴，能把這三種版本都掌握，不怕學(xué)的多，就怕你不學(xué)。

歸并排序

這個(gè)排序如何去想象呢，就類似于，你拿到一組數(shù)的時(shí)候，從中間砍一刀，變成了兩個(gè)區(qū)間，接著把這兩個(gè)區(qū)間分別再砍一刀，變成了四個(gè)區(qū)間，一直重復(fù)下去，當(dāng)區(qū)間的元素個(gè)數(shù)砍成了一個(gè)的時(shí)候，那么這個(gè)區(qū)間就有序了，接著我們開始進(jìn)行二路歸并，也就是說把兩個(gè)有序區(qū)間，合并成一個(gè)有序區(qū)間，這樣一來，是不是整體就有序了？

我們看圖：

歸并排序也需要對(duì)遞歸有一定的學(xué)習(xí)，按照上圖來看，我們肯定是要先遞歸到每個(gè)區(qū)間只有一個(gè)元素的時(shí)候才能進(jìn)行歸并的，歸并的邏輯就是，將兩個(gè)有序序列合并成一個(gè)有序序列嘛，這還是蠻簡(jiǎn)單的。

我們來看代碼：

public void mergeSort(int[] array) {
    mergeSortChild(array, 0, array.length - 1);
}
private void mergeSortChild(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }
 
    int mid = (left + right) >> 1;
    mergeSortChild(array, left, mid);
    mergeSortChild(array, mid + 1, right);
    merge(array, left, mid, right);
}
private void merge(int[] array, int left, int mid, int right) {
    // 準(zhǔn)備歸并 -> 將傳過來的兩個(gè)有序區(qū)間, 合并成一個(gè)有序區(qū)間
    int begin1 = left;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = right;
    int[] tmp = new int[right - left + 1];
    int k = 0;
    while (begin1 <= end1 && begin2 <= end2) {
        if (array[begin1] < array[begin2]) {
            tmp[k++] = array[begin1++];
        } else {
            tmp[k++] = array[begin2++];
        }
    }
    // 跳出循環(huán)之后, begin1 和 begin2 區(qū)間總有一個(gè)區(qū)間還有剩余的元素未拷貝進(jìn)tmp
    while (begin1 <= end1) {
        tmp[k++] = array[begin1++];
    }
    while (begin2 <= end2) {
        tmp[k++] = array[begin2++];
    }
    // 將tmp的數(shù)據(jù)拷回array中
    for (int i = 0; i < k; i++) {
        array[i + left] = tmp[i];
    }
}