待续>📚 八大排序算法合集——两万字，8张动图，450行代码。大厂面试必备。
🌲 配套源码地址：《八大排序》源码，提取码：5ehp

哈喽，大家好，我是一条~

今天给大家带来《糊涂算法》专栏的第二期内容——排序算法的讲解。相信无论是初学者学习还是大厂面试，都少不了排序算法这关，即使没学过算法，对冒泡排序也不会陌生。

今天，一条就带大家彻底跨过**「排序算法」这道坎，保姆级教程建议收藏**。⭐️

准备

古语云：“兵马未动，粮草先行”。想跟着一条一块把「排序算法」弄明白的,建议先准备好以下代码模板。

📢 观看本教程需知道基本循环语法、两数交换、双指针等前置知识。

📚 建议先看完代码和逐步分析后再尝试自己写。

• 新建一个Java工程,本文全篇也基于Java语言实现代码。
• 建立如下目录结构

• 在MainTest测试类中编写测试模板。

/** * 测试类 * Author：一条 * Date：2021/09/23 */
public class MainTest {
    public static void main(String[] args) {
        //待排序序列
        int[] array={6,10,4,5,2,8};
        //调用不同排序算法
				// BubbleSort.sort(array);

        // 创建有100000个随机数据的数组
        int[] costArray=new int[100000];
        for (int i = 0; i < 100000; i++) {
            // 生成一个[0,100000) 的一个数
            costArray[i] = (int) (Math.random() * 100000);
        }

        Date start = new Date();
        //过长，先注释掉逐步打印
				//BubbleSort.sort(costArray);
        Date end = new Date();
        System.out.println("耗时："+(end.getTime()-start.getTime())/1000+"s");
    }
}

该段代码内容主要有两个功能：

• 调用不同的排序算法进行测试
• 测试不同排序算法将10w个数排好序需要的时间。更加具象的理解时间复杂度的不同

堆排序

此章节对基础知识要求较高，初学者可跳过。

基本思想

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种/*/选择排序，//*它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。

堆

堆是具有以下性质的完全二叉树：

• 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
• 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

主要利用堆顶元素最大或最小的特性，通过不断构建大顶堆，交换堆顶和堆尾，断尾重构的方式实现排序。

动图讲解

代码实现

public class HeapSort {
    public static void sort(int[] array) {
        //创建堆
        for (int i = (array.length - 1) / 2; i >= 0; i--) {
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(array, i, array.length);
        }

        //调整堆结构+交换堆顶元素与末尾元素
        for (int i = array.length - 1; i > 0; i--) {
            //将堆顶元素与末尾元素进行交换
            int temp = array[i];
            array[i] = array[0];
            array[0] = temp;

            //重新对堆进行调整
            adjustHeap(array, 0, i);
        }
    }

    /** * 调整堆 * @param array 待排序列 * @param parent 父节点 * @param length 待排序列尾元素索引 */
    private static void adjustHeap(int[] array, int parent, int length) {
        //将temp作为父节点
        int temp = array[parent];
        //左孩子
        int lChild = 2 * parent + 1;
        while (lChild < length) {
            //右孩子
            int rChild = lChild + 1;
            // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
            if (rChild < length && array[lChild] < array[rChild]) {
                lChild++;
            }
            // 如果父结点的值已经大于孩子结点的值，则直接结束
            if (temp >= array[lChild]) {
                break;
            }
            // 把孩子结点的值赋给父结点
            array[parent] = array[lChild];
            //选取孩子结点的左孩子结点,继续向下筛选
            parent = lChild;
            lChild = 2 * lChild + 1;
        }
        array[parent] = temp;
        System.out.println(Arrays.toString(array));
    }
}

输出结果

逐步分析

1. 构建初始堆，将待排序列构成一个大顶堆(或者小顶堆)，升序大顶堆，降序小顶堆；
2. 将堆顶元素与堆尾元素交换，并断开(从待排序列中移除)堆尾元素。
3. 重新构建堆。
4. 重复2~3，直到待排序列中只剩下一个元素(堆顶元素)。

耗时测试

算法优化

优化点关键就在于我们以什么手法找到顶部元素该有的位置，有兴趣同学可以继续研究。

点击查看更多排序算法