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

---

目录

1、 认识排序

2、常见排序的分类

3、直接插入排序

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

5、选择排序

6、堆排序

---

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 的变量 ij常数即空间复杂度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 数据结构】常见排序算法(下)