丰富的线上&线下活动，深入探索云世界
做任务，得社区积分和周边
资深技术专家手把手带教
技术交流，直击现场
让创作激发创新
海量开发者使用工具、手册，免费下载
极速、全面、稳定、安全的开源镜像
开发手册、白皮书、案例集等实战精华
归并排序采用了分治法的思想，不断将两个有序的序列进行合并从而最终得到整个有序的序列，算法步骤如下：
直接上图：
我们先对序列进行划分操作：
然后对各个子序列进行回溯：
通过合并操作，得到最终的子序列。
快速排序也是利用了递归思想，算法步骤如下：
直接上图：
第一步：选取第一个数作为基准数。
第二步：从后往前找一个比基准数小的数放到前面。
第三步：从前往后找到一个比基准数大的树放到后面。
第五步：将该序列分成两半，左半部分是该序列左边界至 first -1 ，右半部分是 first +1 至右边界。
第六步：对左半部分即下标为 0 ~ 1 区间进行递归排序，由于已经是有序我们就直接跳过这里。
第七步：对右半部分即下标为 3 ~ 6 区间进行递归排序。
第八步：从后往前找到一个比基准数小的数放到前面。
第九步：从前往后找一个比基准数大的数放到后面，但是发现指针最终重合，故此次遍历结束，将基准数放到指针所指位置。
第十步：与上面相同，对该序列进行左右区间划分，再分别遍历。由于右半部分已经没有元素了，我们直接对左半部分即下标为 3 ~ 5 区间进行递归排序。
由于该序列已经有序，后续递归操作我们就不再展示了，直接来看代码。
在了解堆排序之前，我们先来看看什么是堆。
堆就是一个类似于完全二叉树的结构，同时它分为大顶堆和小顶堆，它们的性质分别是每个结点的值都大于（或小于）它的孩子结点。
下面就是一个大顶堆：
下面就是一个小顶堆：
那么我们如何利用堆的性质进行排序呢，算法步骤如下（这里讲解升序操作）：
可能会有小伙伴比较有疑惑，我们该如何确定已经排好序和没有排好序的元素呢。这就需要用到完全二叉树的性质：
在下标从 0 开始存储元素的顺序存储的数组当中，结点的左孩子下标等于该结点下标乘以 2 加 1 ，结点的右孩子下标等于该结点下标乘以 2 加 2 。
这样我们可以通过数组下标进行操作，先对前 n 个元素构建大顶堆。然后交换堆顶和最后一个元素，确定数组中第 n 个元素的序列，再对前 n - 1 个元素进行堆操作。
直接上图：
先来看看如何构建出大顶堆，我们要从第一个非叶子结点开始往上构建。因为如果从第一个结点开始往下构建的话，可能无法将最大的元素放到堆顶。
假设我们初始的序列为 { 21 , 343 , 122 , 84 , 5 , 117 , 4 } ，从第一个非叶子结点开始往上构建。
第一步：第一个非叶子结点为 122 ，每次都去找到该结点与其孩子结点中的最大值并进行交换，发现自身印记是最大值了，故找到上一个非叶子结点。
第二步：非叶子结点 343 已经是其和其孩子结点中的最大值，故不用交换。
第三步：非叶子结点 21 与其孩子结点进行比较，发现其孩子结点 343 更大，故进行交换。
第四步：交换后的结点不是叶子结点，故继续向下找到最大值。
至此，大顶堆已经构建完成，现在进行排序操作。
第一步：交换堆顶和最后一个元素。
第二步：对堆顶元素向下进行对操作，注意已经排好序的 343 不再参与到对操作之中。
第三步：交换堆顶和最后一个元素，并对堆顶元素向下进行堆操作。
第四步：交换堆顶和最后一个元素，并对堆顶元素向下进行堆操作。
第五步：交换堆顶和最后一个元素，并对堆顶元素向下进行堆操作。
第六步：交换堆顶和最后一个元素，并对堆顶元素向下进行堆操作。
第七步：交换堆顶和最后一个元素，并对堆顶元素向下进行堆操作。
第八步：交换堆顶和最后一个元素，并对堆顶元素向下进行堆操作。
至此，所有元素都排好序了，直接输出即可。
关注阿里云公众号或下载阿里云APP，关注云资讯，随时随地运维管控云服务