Java數據結構之常見排序算法怎么實現

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

注：后續所說的復雜度 log，都是以2為底，特殊的會標注出來。

冒泡排序

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

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

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

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

• 穩定性：穩定

快速排序

這個排序算是我們比較重要的一個排序了，快速排序是Hoare在1962年提出的一種二叉樹結構的交換排序法，如果你還沒有接觸過二叉樹相關的知識，可以先去本網站的相關二叉樹文章中學習學習。

理解快速排序的二叉樹結構

如何理解快速排序的二叉樹結構呢？

可以這樣來想象一下：

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

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

而如何確定基準值的位置，這就是我們快速排序要實現的算法！

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

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

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

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

當然光看圖可能了解的不是很通透，那么下面，我們結合著這張圖，來實現快速排序的三種算法。

為了實參傳遞的統一性，我們快速排序的形參統一為以下格式，調用被封裝的 quick 方法：

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

 Hoare 法

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

代碼如下：

private void quick(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = partitionHoare(array, left, right);
    quick(array, left, pivot - 1); //左區間
    quick(array, pivot + 1, right); //右區間
}
private int partitionHoare(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--;
        }
        // 左邊找比基準大的數的下標
        while (begin < end && array[begin] <= pivot) {
            begin++;
        }
        // 交換
        swap(array, begin, end);
    }
    swap(array, left, begin);
    return begin; //返回基準值當前所處的下標, 左邊都比它小, 右邊都比它大
}

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

這里有兩個問題，我們來看 partitionHoare 方法實現里面：

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

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

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

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

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

3. 如果這組數本來就是升序的呢？右邊 end 找不到比基準值小的數，如果基準就是最小的數呢？內部 whild 不限制的話 end 是不是會自減成為負數？導致下標不合法了？

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

當數組有序的情況下，快速排序的時間效率最差！試想一下，如果每次找的基準值都是最小的話，劃分區間的時候，是不是就成了一棵沒有左樹的二叉樹了啊？類似于一種鏈表的結構了，見下圖：

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

三數取中

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

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

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 方法中，求到了第二大值下標后，與 left 位置交換下即可：

private void quick(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }
    // 三數取中
    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);
}

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

但是這樣優化還是不夠，因為當我們數據量夠大的時候，二叉樹的層數就越高，而越往后，區間被分割的越小，里面的數據也就越接近有序，但是越接近有序了，還會往下分割，這樣會造成大量的壓棧操作，遞歸本身就是在壓棧的過程嘛，為了減少這樣的情況，又有一個優化辦法：小區間優化。

小區間優化

數據量大的時候，分割到區間越小，則表示數據越接近有序了，前面我們認識了一個數據越接近有序效率越快的排序，那就是直接插入排序，所以我們可以進行小區間優化，那么簡單來說，就是當區間的數據個數小于某個值的時候，采用直接插入排序算法。

private void quick(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }
    // 小區間優化 -> 如果待排序的數據小于15個,我們直接使用直接插入排序
    if ((right - left + 1) < 15) {
        insertSort(array);
        return;
    }
    // 三數取中
    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);
}

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

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

• 穩定性：不穩定

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

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

 挖坑法

這個方法很簡單，主要思路就是，一樣有兩個引用，begin 和 end，end 從右找比基準小的，begin從左找比基準大的， 當 end 找到比基準小的，直接覆蓋掉 begin 的位置，接著 begin 找到了比基準大的接著去覆蓋 end 位置，相遇后，將基準值覆蓋掉 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;
}

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

前后指針法

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

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;
}

注意事項

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

歸并排序

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

我們看圖：

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

我們來看代碼：

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) {
    // 準備歸并 -> 將傳過來的兩個有序區間, 合并成一個有序區間
    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++];
        }
    }
    // 跳出循環之后, begin1 和 begin2 區間總有一個區間還有剩余的元素未拷貝進tmp
    while (begin1 <= end1) {
        tmp[k++] = array[begin1++];
    }
    while (begin2 <= end2) {
        tmp[k++] = array[begin2++];
    }
    // 將tmp的數據拷回array中
    for (int i = 0; i < k; i++) {
        array[i + left] = tmp[i];
    }
}

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

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

• 穩定性：穩定

• 堆排序主要用于外排序

關于“Java數據結構之常見排序算法怎么實現”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。