Java數據結構常見排序算法有哪些

今天小編給大家分享一下Java數據結構常見排序算法有哪些的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

1、 認識排序

在學校中，如果我們要參加運動會，或者軍訓的時候，會按照身高從矮到高進行站隊，比如上課老師手上拿的考勤表，通常是按照學號從低到高進行排序的。再比如編程語言排行榜，也是在排序。

生活中有相當多的排序場景，由此可知，排序還是很重要的， 本章就會介紹常見的一些排序算法。

所謂排序呢，就拿我們上面的舉例來說，會按照某個或某些關鍵字的大小，遞增或者遞減排列起來的操作，這就是排序，這里面也涉及到排序的穩定性，舉個例子：

比如有這樣的一組數據：B  D  A  C  A  F，要按照他們的 ascll 碼來排序，這里出現了兩個 A，我們把第一個出現的 A 稱為 A1，第二個出現的 A 稱為 A2。

假定排序后結果為：A1  A2  B  C  D  F，那么這個排序算法就是穩定的。

假設排序后結果為：A2  A1  B  C  D  F，那么這個排序算法就是不穩定的。

簡而言之，如果待排序的數據中，有兩個相同的元素，排序結束后，這兩個元素的關系沒有發生改變，比如 A1 排序前在 A2 前面，排完序后，A1 還在 A2 前面，這就是穩定的排序算法。

注意：一個不穩定的排序算法，天生就是不穩定的，但是一個穩定的排序算法，你可以把它設計成不穩定的。

2、常見排序的分類

這張圖，概括了我們后續要講的排序算法，接著正式進入本章的學習吧！(排序算法章節，默認都是升序排序) 注：后續所說的復雜度 log，都是以2為底，特殊的會標注出來。

3、直接插入排序

現在想請各位小伙伴，想象一下自己在摸撲克牌，摸了第一張牌放在了自己的手中，接著再摸一張，把這張牌跟手上的一張牌進行比較，把它放到合適的位置， 接著再摸一張，把這張牌跟手上的兩張牌進行比較，放到合適的位置。

這就是直接插入排序，簡單來說，我們每次取的元素，會往一個有序的序列中插入，也就是每次摸牌之前，手上的牌都是排好序的，我們只需要把新摸到的牌，依次與手上有序的牌進行比較，把它放入合適的位置就行！

這里我們用一副靜態的圖來簡單演示下：

大致的思想我們已經明白了，接下來我們就需要用代碼來實現他：

public void insertSort(int[] array) {
    // 外循環控制趟數, 第一張牌默認有序, 所以 i 從 1 開始
    for (int i = 1; i < array.length; i++) {
        int tmp = array[i]; //當前摸到的牌
        // 每次從手中牌的最后一張牌開始比較, 一直比到第一張牌
        int j = i - 1;
        for (; j >= 0; j--) {
            //如果當前位置的牌,大于我摸到的牌,就往后挪
            if (array[j] > tmp) {
                array[j + 1] = array[j];
            } else {
                break;
            }
        }
        // 把摸到的牌放到對應位置上
        array[j + 1] = tmp;
    }
}

• 時間復雜度分析：外循環一共要 n - 1 次，內循環每次最差的情況下要比較 1....n 次，那么去掉 n 前面的小項，也就是 (n - 1) * n 次，即 n^2 - n，去掉最小項，最后的時間復雜度為 O(n^2)

• 空間復雜度分析：只是開辟了一個 tmp 的變量 i，j，常數，即空間復雜度：O(1)

• 穩定性：穩定

• 該排序再數據越接近有序的情況，時間效率越高。

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

這個排序是直接插入排序的一種優化，你可以想象一下，你面前有并排放好的 8 個愛心號碼牌，但是它們是無序的，我們要給號碼牌分組，按要求，第一次間隔為 4 個號碼牌的為一組，分完組后進行直接插入排序，第二次間隔為 2 個號碼牌的為一組，進行直接插入排序，第三次間隔為 1 個號碼牌為一組，進行直接插入排序。

聽到這有點沒理解，沒關系，我們就通過畫圖來把我上述說的內容再次理解下：

由上圖我們可以發現，當間隔 > 1 的時候，都是預排序，也就是讓我們的數據更接近有序，但是當間隔為 1 的時候，就是直接插入排序了，前面我們說過，直接插入排序，再數據接近有序的時候時間效率是很快的。由此可見，希爾排序，是直接插入排序的優化版。

如何在代碼中實現呢？間隔的值如何取呢？代碼中把這個間隔的值稱為 gap，這個 gap 的取值方法有很多，有的人提出 gap 為奇數好，有的提出 gap 為偶數好，我們就采取一種比較簡單的方法來取 gap 值，首次取數組長度一半的值為 gap，后續 gap /= 2，即可。當 gap 為 1，也就是直接插入排序了。

代碼實現如下：

public void shellSort(int[] array) {
    // gap初始值設置成數組長度的一半
    int gap = array.length >> 1;
    // gap 為 1 的時候直接插入排序
    while (gap >= 1) {
        shell(array, gap);
        gap >>= 1; // 更新 gap 值 等價于 -> gap /= 2;
    }
}
private void shell(int[] array, int gap) {
    for (int i = gap; i < array.length; i++) {
        int tmp = array[i];
        int j = i - gap;
        for (; j >= 0; j -= gap) {
            if (array[j] > tmp) {
                array[j + gap] = array[j];
            } else {
                break;
            }
        }
        array[j + gap] = tmp;
    }
}

如果實在是不好理解，就結合上邊講的直接插入排序來理解，相信你能理解到的。

• 時間復雜度分析：希爾排序的時間復雜度不好分析， 這里我們就大概記一下，約為 O(n^1.3)，感興趣的話，可以查閱一下相關書籍。

• 空間復雜度分析：仍然開辟的是常數個變量，空間復雜度為 O(1)

• 穩定性：不穩定

5、選擇排序

這個排序是個很簡單的排序，你想象一下，有個小屁孩，喜歡玩小球，我給他安排了個任務，把這一排小球從小到大排列起來，擺給我看，于是小屁孩就找，每次從一排小球中找出最大的，放到最后，固定不動，那是不是也就是說，每次能確定一個最大的石子的最終位置了。我們來看圖：

通過圖片我們也能看出來，每次找到最大值于最后一個值交換，所以每趟都能把最大的放到最后固定不動，每趟能排序一個元素出來，那這樣用代碼來實現就很簡單了：

public void selectSort(int[] array) {
    int end = array.length - 1;
    // 剩最后一個元素的時候, 不用比較了, 已經有序了
    // 所以 i < array.length - 1
    for (int i = 0; i < array.length - 1; i++) {
        int max = 0;
        int j = 0;
        while (j <= end) {
            if (array[j] > array[max]) {
                max = j;
            }
            j++;
        }
        //找到了最大值的下標, 把最大值與最后一個值交換
        swap(array, max, end--); // end-- 最后一個元素固定了, 不用參與比較
    }
}

這個算法有沒有可以優化的空間呢？

有！那么既然小屁孩能一次找出最大的球，那能不能讓小屁孩一次找出兩個球出來呢？分別是這些球中，最大的和最小的，最大的放在最右邊，最小的放在最左邊，那么我們每次就能確定兩個球的最終位置，也就是我們一次能排序兩個元素。圖解：

代碼實現如下：

public void selectSort(int[] array) {
    int left = 0;
    int right = array.length - 1;
    while (left < right) {
        int maxIndex = left;
        int minIndex = left;
        // i = left + 1 -> 每次找最大最小值下標的時候, 可以不用算默認給的最大值和最小值下標
        for (int i = left + 1; i <= right; i++) {
            if (array[i] > array[maxIndex]) {
                maxIndex = i;
            }
            if (array[i] < array[minIndex]) {
                minIndex = i;
            }
        }
        swap(array, minIndex, left);
        // 如果最大值為 left 的位置情況的話, 走到這, 最大值已經被交換到 min 位置上了
        if (maxIndex == left) {
            // 更新最大值的位置
            maxIndex = minIndex;
        }
        swap(array, maxIndex, right);
        left++;
        right--;
    }
}

• 時間復雜度分析：雖然是優化了，但去小項之后，還是 O(n^2)

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

• 穩定性：不穩定

• 實際開發中用的不多

6、堆排序

如果你有學習過優先級隊列，或者看過博主優先級隊列的文章，那么這個排序對于你來說還是很輕松的，當然在堆排序的講解中，不會過多的去介紹堆的概念，如果對這部分概念還不理解，可以移至博主的上一篇文章進行學習。

堆排序，簡單來說，就是把一組數據，看成一個完全二叉樹，再把這棵樹，建大堆或者建小堆，接著進行排序的一種思路。至于如何建大堆或小堆，和向上調整算法以及向下調整算法，這里也不多介紹了，博主的上篇文章都詳細介紹過。

這里我們來分析一下，排升序應該建什么堆？大堆！排降序建小堆！

這里我們來排升序，建大堆，因為大堆堆頂元素一定是堆中最大的，所以我們可以把堆頂元素和最后一個元素進行交換，這樣我們就確認了最大值的位置，接著將交換后的堆頂元素進行向下調整，仍然使得該數組滿足大堆的特性！圖解如下：

如上圖步驟也很簡單，先是將數組建成大堆，然后利用大堆來進行堆排序，首先將堆頂元素和最后一個元素交換，由此最大的元素就有序了，接著將該堆進行向下調整，使繼續滿足大堆性質，依次進行下去即可。

代碼實現：

public void heapSort(int[] array) {
    // 建大堆 從最后一個非葉子節點開始向下調整
    // 非葉子節點下標 = (孩子節點下標 - 1) / 2
    for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
        shiftDown(array, parent, array.length);
    }
    // 建大堆完成后, 每次堆頂元素與最后一個元素交換, 鎖定最大元素的位置
    for (int len = array.length - 1; len > 0; len--) {
        swap(array, 0, len); //根節點與最后一個元素交換
        shiftDown(array, 0, len); //根節點位置向下調整
    }
}
private void shiftDown(int[] array, int parent, int len) {
    int child = parent * 2 + 1;
    while (child < len) {
        if (child + 1 < len && array[child + 1] > array[child]) {
            child++;
        }
        // 判斷父節點是否大于較大的孩子節點
        if (array[parent] < array[child]) {
            swap(array, parent, child);
            // 更新下標的位置
            parent = child;
            child = parent * 2 + 1;
        } else {
            return;
        }
    }
}

• 時間復雜度分析：建堆的時間復雜度優先級隊列那期有說過為 O(n)，排序調整堆的時候，一共要調整 n-1 次，每次向下調整的時間復雜度是 logn，所以即 logn(n - 1)，即 O(n*logn)，加上面建堆的時間復雜度：O(n) + O(n*logn)，最終時間復雜度也就是：O(n*logn)。

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

• 穩定性：不穩定

以上就是“Java數據結構常見排序算法有哪些”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。