三种经典排序算法：堆排序、快速排序与归并排序的详解

一、堆排序（Heap Sort）

堆排序是一种利用堆数据结构进行排序的算法。它通过构建最大堆或最小堆，然后不断地将堆顶元素与末尾元素交换，再调整堆结构，以达到排序的目的。

1. 构建最大堆：首先，将数组调整为最大堆。最大堆的特点是每个节点的值都不小于其子节点的值。调整堆的过程是从最后一个非叶子节点开始，依次向上调整，确保满足堆的性质。
2. 交换与调整：将堆顶元素（最大值）与末尾元素交换，然后调整剩余元素为最大堆。
3. 重复步骤：重复步骤2，直到整个数组有序。

优点：时间复杂度为O(nlogn)，在所有元素都不同的情况下最快。
缺点：比较次数较多，空间复杂度为O(1)。

二、快速排序（Quick Sort）

快速排序是一种分治策略的排序算法。它将数组分为两部分，左边的部分都比基准值小，右边的部分都比基准值大，然后对左右两部分递归进行快速排序。

1. 选取基准值：随机选取数组中的一个元素作为基准值。
2. 分区：重新排列数组，所有比基准值小的元素放在基准值的左边，所有比基准值大的元素放在基准值的右边。这个操作称为分区操作。
3. 递归排序左右子数组：对基准值左边的子数组和右边的子数组分别递归进行快速排序。

优点：平均时间复杂度为O(nlogn)，最坏情况下时间复杂度为O(n^2)。
缺点：需要额外的空间，在最坏情况下可能退化为O(n^2)。

三、归并排序（Merge Sort）

归并排序是一种采用分治策略的排序算法。它将一个数组分成两个子数组，分别对子数组进行排序，然后将两个有序的子数组合并成一个有序的数组。

1. 分解：将数组分解成两个子数组，直到每个子数组只包含一个元素。
2. 递归排序子数组：递归地对子数组进行归并排序。
3. 合并：将两个有序的子数组合并成一个有序的数组。合并的过程是依次取两个子数组的第一个元素比较，将较小的元素放入新数组中，直到其中一个子数组为空，然后将另一个子数组的剩余部分全部放入新数组中。

优点：时间复杂度稳定为O(nlogn)，空间复杂度为O(n)，是稳定的排序算法。
缺点：由于合并过程中需要额外的空间，所以空间复杂度较高。