堆排序JAVA实现（堆排序java）

堆排序是一种稳定的排序方法吗？

是不稳定的排序算法

堆排序

我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。

在一个长为n 的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, ...1这些个父节点选择元素时，就会破坏稳定性。

有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。

为什么堆排序只有一个辅助单元？

设有n个待排序的记录关键字，则在堆排序中需要1个辅助记录单元。

　　堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

堆排序只需要一个辅助单元是因为它是一种原地排序算法，不需要额外的空间来存储排序结果。堆排序通过构建最大堆或最小堆来实现排序，堆的结构可以直接在原始数组上进行操作，不需要额外的空间。

在排序过程中，只需要一个辅助单元来交换堆顶元素和当前待排序元素，然后调整堆结构即可。这种设计使得堆排序具有较小的空间复杂度，适用于大规模数据的排序。

在快速排序、堆排序、归并排序中，什么排序是稳定的？

归并排序是稳定的“快速排序和堆排序都不稳定.不稳定：就是大小相同的两个数，经过排序后，最终位置与初始位置交换了。

快速排序：27 23 27 3以第一个27作为pivot中心点，则27与后面那个3交换，形成3 23 27 27，排序经过一次结束，但最后那个27在排序之初先于初始位置3那个27，所以不稳定。

堆排序：比如：3 27 36 27，如果堆顶3先输出，则，第三层的27（最后一个27）跑到堆顶，然后堆稳定，继续输出堆顶，是刚才那个27，这样说明后面的27先于第二个位置的27输出，不稳定。”“2 归并排序（MergeSort）

归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。”

以Ai与Aj为例子快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_indexij都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。

交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列5 3 3 4 3 8 9 10 11，现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j]交换的时刻。