【Java 数据结构】常见排序算法(上)

Love The Way You Lie 2024-03-30 10:31 62阅读 0赞

![b4e6ca8983a34017be11d504193bfa0e.png][] 篮球哥温馨提示：编程的同时不要忘记锻炼哦！

## 稳定的排序算法，可以设计成不稳定的. ##

--------------------

**目录**

1、 认识排序

2、常见排序的分类

3、直接插入排序

4、希尔排序(缩小增量排序)

5、选择排序

6、堆排序

--------------------

## **1、 认识排序** ##

在学校中，如果我们要参加运动会，或者军训的时候，会按照身高从矮到高进行站队，比如上课老师手上拿的考勤表，通常是按照学号从低到高进行排序的。再比如编程语言排行榜，也是在排序。

![ffd24f337df14fef8dc32532a1d77fb4.png][]

生活中有相当多的排序场景，由此可知，排序还是很重要的， 本章就会介绍常见的一些排序算法。

所谓排序呢，就拿我们上面的举例来说，会按照某个或某些关键字的大小，递增或者递减排列起来的操作，这就是排序，这里面也涉及到**排序的稳定性**，举个例子：

**比如有这样的一组数据：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、常见排序的分类** ##

![579a52fc48154c23b62937215f48c433.png][]

这张图，概括了我们后续要讲的排序算法，接着正式进入本章的学习吧！(排序算法章节，默认都是**升序排序**) **注：后续所说的复杂度 log，都是以2为底，特殊的会标注出来。**

--------------------

## **3、直接插入排序** ##

现在想请各位小伙伴，想象一下自己在摸扑克牌，摸了第一张牌放在了自己的手中，接着再摸一张，把这张牌跟手上的一张牌进行比较，把它放到合适的位置， 接着再摸一张，把这张牌跟手上的两张牌进行比较，放到合适的位置。

这就是直接插入排序，简单来说，我们每次取的元素，会往一个有序的序列中插入，也就是每次摸牌之前，手上的牌都是排好序的，我们只需要把新摸到的牌，依次与手上有序的牌进行比较，把它放入合适的位置就行！

**这里我们用一副静态的图来简单演示下：**

![5727183867164688834ada61fc606c07.png][]

大致的思想我们已经明白了，接下来我们就需要用代码来实现他：

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 个号码牌为一组，进行直接插入排序。

**听到这有点没理解，没关系，我们就通过画图来把我上述说的内容再次理解下：**

![22159773e3384a8fa58e7c63187ab25c.png][]

由上图我们可以发现，当间隔 > 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、选择排序** ##

这个排序是个很简单的排序，你想象一下，有个小屁孩，喜欢玩小球，我给他安排了个任务，把这一排小球从小到大排列起来，摆给我看，于是小屁孩就找，每次从一排小球中找出最大的，放到最后，固定不动，那是不是也就是说，每次能确定一个最大的石子的最终位置了。我们来看图：

![bde0e04a8f2146969486208a9829f6d4.png][]

通过图片我们也能看出来，每次找到最大值于最后一个值交换，所以每趟都能把最大的放到最后固定不动，每趟能排序一个元素出来，那这样用代码来实现就很简单了：

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-- 最后一个元素固定了, 不用参与比较
        }
    }

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

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

![ef6c289d962f4ce28769225978e0d2fa.png][]

**代码实现如下：**

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、堆排序** ##

如果你有学习过优先级队列，或者看过博主优先级队列的文章，那么这个排序对于你来说还是很轻松的，当然在堆排序的讲解中，不会过多的去介绍堆的概念，如果对这部分概念还不理解，可以移至博主的上一篇文章进行学习。

堆排序，简单来说，就是把一组数据，看成一个完全二叉树，再把这棵树，建大堆或者建小堆，接着进行排序的一种思路。至于如何建大堆或小堆，和向上调整算法以及向下调整算法，这里也不多介绍了，博主的上篇文章都详细介绍过。

这里我们来分析一下，排升序应该建什么堆？大堆！排降序建小堆！

这里我们来排升序，建大堆，因为大堆堆顶元素一定是堆中最大的，所以我们可以把堆顶元素和最后一个元素进行交换，这样我们就确认了最大值的位置，接着将交换后的堆顶元素进行向下调整，仍然使得该数组满足大堆的特性！图解如下：

![fc25760dda7641f4bfbd30241bffd628.png][]

![25c07fc5787146eaaf557970404d4480.png][]

如上图步骤也很简单，先是将数组建成大堆，然后利用大堆来进行堆排序，首先将堆顶元素和最后一个元素交换，由此最大的元素就有序了，接着将该堆进行向下调整，使继续满足大堆性质，依次进行下去即可。

**代码实现：**

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 数据结构】常见排序算法(下)**

[b4e6ca8983a34017be11d504193bfa0e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/3c14564b9139426ebe4e8d95e5f8a3af.png
[ffd24f337df14fef8dc32532a1d77fb4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/781e5fec56e9485f9c770d114653ab5b.png
[579a52fc48154c23b62937215f48c433.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7a87e6b509c14955bda23b4182c2e482.png
[5727183867164688834ada61fc606c07.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d3d549f10bf14391ad2b468e9a13af36.png
[22159773e3384a8fa58e7c63187ab25c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/54f0e459eb3a439d90e26d5d677621c4.png
[bde0e04a8f2146969486208a9829f6d4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/85907c03651149a3a9d2fca5705e5880.png
[ef6c289d962f4ce28769225978e0d2fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9faa77dd4d3d45799e5f5ad51155e441.png
[fc25760dda7641f4bfbd30241bffd628.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/c3b53f7db27348ddbde7215a2d6604f5.png
[25c07fc5787146eaaf557970404d4480.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/28a557f3b3004793807cc3970dea1431.png