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 = 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 = 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[max]) {
                max = j;
            }
            j++;
        }
        //找到了最大值的下标, 把最大值与最后一个值交换
        swap(array, max, end--); // end-- 最后一个元素固定了, 不用参与比较
    }
}

这个算法有没有可以优化的空间呢？

有！那么既然小屁孩能一次找出最大的球，那能不能让小屁孩一次找出两个球出来呢？分别是这些球中，最大的和最小的，最大的放在最右边，最小的放在最左边，那么我们每次就能确定两个球的最终位置，也就是我们一次能排序两个元素。图解：

代码实现如下：

public void selectSort(int[] array) {
    int left = 0;
    int right = array.length - 1;
    while (left  每次找最大最小值下标的时候, 可以不用算默认给的最大值和最小值下标
        for (int i = left + 1; i  array[maxIndex]) {
                maxIndex = i;
            }
            if (array[i] <blockquote><ul>
<li>
<strong>时间复杂度分析：</strong>虽然是优化了，但去小项之后，还是 O(n^2)</li>
<li>
<strong>空间复杂度分析：</strong>O(1)</li>
<li>
<strong>稳定性：</strong>不稳定</li>
<li>实际开发中用的不多</li>
</ul></blockquote><h2 id="堆排序">6、堆排序</h2><p>如果你有学习过优先级队列，或者看过博主优先级队列的文章，那么这个排序对于你来说还是很轻松的，当然在堆排序的讲解中，不会过多的去介绍堆的概念，如果对这部分概念还不理解，可以移至博主的上一篇文章进行学习。 </p><p>堆排序，简单来说，就是把一组数据，看成一个完全二叉树，再把这棵树，建大堆或者建小堆，接着进行排序的一种思路。至于如何建大堆或小堆，和向上调整算法以及向下调整算法，这里也不多介绍了，博主的上篇文章都详细介绍过。</p><p>这里我们来分析一下，排升序应该建什么堆？大堆！排降序建小堆！</p><p>这里我们来排升序，建大堆，因为大堆堆顶元素一定是堆中最大的，所以我们可以把堆顶元素和最后一个元素进行交换，这样我们就确认了最大值的位置，接着将交换后的堆顶元素进行向下调整，仍然使得该数组满足大堆的特性！图解如下：</p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/067/2bc60faf9fc0c95d70ba2ea59969f749-7.png?x-oss-process=image/resize,p_40" class="lazy" alt=""></p><p   style="max-width:90%"><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/067/b7212cc82d02b12aea3900b8247d02ae-8.png?x-oss-process=image/resize,p_40" class="lazy" alt=""></p><p>如上图步骤也很简单，先是将数组建成大堆，然后利用大堆来进行堆排序，首先将堆顶元素和最后一个元素交换，由此最大的元素就有序了，接着将该堆进行向下调整，使继续满足大堆性质，依次进行下去即可。</p><p><strong>代码实现：</strong></p><pre class="brush:php;toolbar:false">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  array[child]) {
            child++;
        }
        // 判断父节点是否大于较大的孩子节点
        if (array[parent] <blockquote><ul>
<li>
<strong>时间复杂度分析：</strong>建堆的时间复杂度优先级队列那期有说过为 O(n)，排序调整堆的时候，一共要调整 n-1 次，每次向下调整的时间复杂度是 logn，所以即 logn(n - 1)，即 O(n*logn)，加上面建堆的时间复杂度：O(n) + O(n*logn)，最终时间复杂度也就是：O(n*logn)。</li>
<li>
<strong>空间复杂度分析：</strong>O(1)</li>
<li>
<strong>稳定性：</strong>不稳定</li>
</ul></blockquote>

推荐学习：《java视频教程》

以上是Java資料結構常見排序演算法（總結分享）的詳細內容。更多資訊請關注PHP中文網其他相關文章！