Java數(shù)據(jù)結(jié)構(gòu)之常見排序算法怎么實現(xiàn)

這篇文章主要介紹“Java數(shù)據(jù)結(jié)構(gòu)之常見排序算法怎么實現(xiàn)”的相關(guān)知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“Java數(shù)據(jù)結(jié)構(gòu)之常見排序算法怎么實現(xiàn)”文章能幫助大家解決問題。

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

冒泡排序

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

public void bubbleSort(int[] array) {
    // 外循環(huán)控制比較的趟數(shù)
    for (int i = 0; i < array.length - 1; i++) {
        boolean flag = true;
        // 內(nèi)循環(huán)控制需要比較的元素個數(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 是對該排序做的一種優(yōu)化，如果當(dāng)進入內(nèi)循環(huán)之后，發(fā)現(xiàn)沒有發(fā)生交換，則表示此時的數(shù)據(jù)已經(jīng)有序了，不需要接著去比較了。

• 時間復(fù)雜度分析：這個排序就很簡單了，O(n^2)

• 空間復(fù)雜度分析：O(1)

• 穩(wěn)定性：穩(wěn)定

快速排序

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

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

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

可以這樣來想象一下：

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

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

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

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

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

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

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

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

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

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

 Hoare 法

我上面畫的那幅圖就是 Hoare 法，主要邏輯是，令區(qū)間第一個數(shù)為基準(zhǔn)值，定義兩個變量，分別表示區(qū)間左邊起始位置下標(biāo)，和右邊起始位置下標(biāo)(區(qū)間最后一個數(shù)的下標(biāo))，先從右邊開始找比基準(zhǔn)值小的，再去左邊找比基準(zhǔn)值大的，找到之后，交換這兩個值，當(dāng)這兩個下標(biāo)相遇了，就把基準(zhǔn)值與其中一個下標(biāo)交換即可，這樣就能達到，基準(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ū)間第一個數(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 方法，有點像二叉樹的前序遍歷，確實也是這樣的，前面我們也說過，快排是一種二叉樹的結(jié)構(gòu)，結(jié)合著代碼再去看那幅圖，是不是理解的更通透了呢？

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

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

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

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

1. 如果左邊作為基準(zhǔn)值的話，只能從右邊開始找，如果從左邊開始找，當(dāng) begin 和 end 相遇之后的值，要比基準(zhǔn)值大，因為 begin 和 end 交換后，end 位置的值已經(jīng)比基準(zhǔn)值要大了

2. 如果不取等于號，可能會造成死循環(huán)，你設(shè)想下不取等于號時，區(qū)間里第一個元素和最后一個元素相同的情況下。

3. 如果這組數(shù)本來就是升序的呢？右邊 end 找不到比基準(zhǔn)值小的數(shù)，如果基準(zhǔn)就是最小的數(shù)呢？內(nèi)部 whild 不限制的話 end 是不是會自減成為負(fù)數(shù)？導(dǎo)致下標(biāo)不合法了？

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

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

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

三數(shù)取中

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

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

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 哪個位置小即可
            if (array[mid] < array[right]) {
                //mid是第二大的值
                return mid;
            } else {
                return right;
            }
        } else {
            // 走到這里, 則left位置小于等于right位置, 并大于mid位置, 則left是第二大的值
            return left;
        }
    } else { // 走這個else表示left位置大于等于right位置
        if (array[left] > array[mid]) {
            // 走到這里表示 left 位置一定是最大的值,
            // 我們只需要判斷 mid 和 right 位置哪個大即可
            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)化還是不夠，因為當(dāng)我們數(shù)據(jù)量夠大的時候，二叉樹的層數(shù)就越高，而越往后，區(qū)間被分割的越小，里面的數(shù)據(jù)也就越接近有序，但是越接近有序了，還會往下分割，這樣會造成大量的壓棧操作，遞歸本身就是在壓棧的過程嘛，為了減少這樣的情況，又有一個優(yōu)化辦法：小區(qū)間優(yōu)化。

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

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

private void quick(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }
    // 小區(qū)間優(yōu)化 -> 如果待排序的數(shù)據(jù)小于15個,我們直接使用直接插入排序
    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);
}

• 時間復(fù)雜度分析：在我們有了三數(shù)取中優(yōu)化的情況下，可以達到 O(n*logn)，如果沒有三數(shù)取中，極端最壞的情況下，能達到 O(n^2)，但是我們通常說的快排都是優(yōu)化過的，也就是 O(n*logn)。

• 空間復(fù)雜度分析：每次遞歸都會壓棧，隨之開辟空間，那么快排類似于二叉樹的前序遍歷，左子樹遍歷完了，再有右子樹，也就是會壓棧，也會出棧，那么最大壓棧多少呢？顯然是樹的高度，即 O(logn)。

• 穩(wěn)定性：不穩(wěn)定

• 快速排序整體的綜合性能和使用場景都是比較好的

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

 挖坑法

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

直接看代碼：

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ù)都是挖坑法居多。

前后指針法

這個算法用的很少很少，思路就是，定義一個 cur 和 prev，cur 起始位置為 left+1，只要 cur 不大于 right，就往前走，找到比基準(zhǔn)小的值就停下來，與 ++prev 位置的值進行交換，這樣一來，比基準(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;
}

注意事項

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

歸并排序

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

我們看圖：

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

我們來看代碼：

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)備歸并 -> 將傳過來的兩個有序區(qū)間, 合并成一個有序區(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ū)間總有一個區(qū)間還有剩余的元素未拷貝進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];
    }
}

• 時間復(fù)雜度分析：O(n*logn)

• 空間復(fù)雜度分析：最多會開辟數(shù)組長度個空間即 O(n)

• 穩(wěn)定性：穩(wěn)定

• 堆排序主要用于外排序

關(guān)于“Java數(shù)據(jù)結(jié)構(gòu)之常見排序算法怎么實現(xiàn)”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會為大家更新不同的知識點。