尚洁雯
十大经典排序算法(一)
十大经典排序算法(2)
00-1010 Heapsort是指利用堆的数据结构设计的一种排序算法。堆叠是一种近乎完整的二叉树结构，同时满足堆叠的性质：即子节点的键值或索引始终小于(或大于)其父节点。堆排序可以说是一种利用堆的概念进行排序的选择性排序。有两种方法：
Top heap:每个节点的值大于等于其子节点的值，用于堆排序算法中的升序；Top heap:每个节点的值小于或等于其子节点的值，用于堆排序算法中的降序；堆排序的平均时间复杂度为 (nlogn)。
00-1010:构建要排序成H堆的序列[0.n-1]，根据(升降需求)选择大顶桩或小顶桩；交换反应器的头部(最大值)和尾部；将堆大小减少1，并调用shift_down(0)将新数组的顶部数据调整到相应的位置；重复步骤2，直到堆大小为1。
7 堆排序（Heap Sort）
详细注释
下图是深度为4的完整二叉树。
堆(二进制堆)可以看作是一棵完整的二叉树。完整二叉树的一个“优秀”属性是，除底层之外的每一层都是满的，这使得堆可以用数组来表示(普通的二叉树通常用链表作为基本容器来表示)，每个节点对应数组中的一个元素。
下图显示了堆和数组之间的关系。
给定某个节点的索引I，很容易计算出该节点的父节点和子节点的索引：
父子节点的父(i)=i/2 //i下标Left(i)=2i //i下标Right(i)=2i 1 //i下标heap(二进制堆)分为最大堆(大顶堆)和最小堆(小顶堆)两种类型。
大堆
堆中的最大元素值出现在根节点(堆的顶部)。堆中每个父节点的元素值大于或等于其子节点(如果存在)。
定堆
堆中的最小元素值出现在根节点(堆的顶部)。堆中每个父节点的元素值小于或等于其子节点(如果有)
。
堆排序是指取出最大堆顶的最大个数，将剩余堆调整到最大堆，再取出堆顶的最大个数。这个过程一直持续到只剩下一个堆。在堆中定义以下操作：
调整堆在继续下面的讨论之前，我们应该注意一个问题：数组都是从零开始的，这意味着我们的堆数据结构模型将会改变：
因此，应相应调整几个计算公式：
Parent(i)=(i-1)/2 //i父节点下标Left(i)=2i 1 //i Left子节点下标Right(i)=2i 2 //i Right子节点下标
算法描述
最大堆调整(Max‐Heapify)用于保留最大堆的属性并创建最大堆。
4a24e94b6a24be1d89685c2?from=pc”>
由于一次调整后，堆仍然违反堆性质，所以需要递归的测试，使得整个堆都满足堆性质。
/**
* 最大堆调整
*
* @param index 检查起始的下标
* @param heapSize 堆大小
*/
public void heapify(int[] array, int index, int heapSize) {
int left = 2 * index + 1;// 左孩子的下标（如果存在的话）
int right = 2 * index + 2;// 左孩子的下标（如果存在的话）
int iMax = index;// 寻找3个节点中最大值节点的下标
if (left < heapSize && array[left] > array[index]) {
iMax = left;
}
if (right < heapSize && array[right] > array[iMax]) {
iMax = right;
}
if (iMax != index) {
swap(array, iMax, index);
heapify(array, iMax, heapSize);
}
}
public void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
递归在调用递归子函数的时候，会先将传给子函数的参数压栈，然后将当前指令的下一条指令的地址压栈，以便子函数执行完后返回到原函数中继续执行，在原函数继续执行之前还涉及到清理子函数的栈。因此，递归的效率比迭代低一点点。其实上面的调整堆也可以用迭代来实现：
public void heapify(int[] array, int index, int heapSize) {
int left, right, iMax;
while (true) {
left = 2 * index + 1;// 左孩子的下标（如果存在的话）
right = 2 * index + 2;// 左孩子的下标（如果存在的话）
iMax = index;// 寻找3个节点中最大值节点的下标
if (left < heapSize && array[left] > array[index]) {
iMax = left;
}
if (right < heapSize && array[right] > array[iMax]) {
iMax = right;
}
if (iMax != index) {
swap(array, iMax, index);
index = iMax;
} else {
break;
}
}
}
建堆
创建最大堆（Build-Max-Heap）的作用是将一个数组改造成一个最大堆，接受数组和堆大小两个参数，Build-Max-Heap 将自下而上的调用 Max-Heapify 来改造数组，建立最大堆。因为 Max-Heapify 能够保证下标 i 的结点之后结点都满足最大堆的性质，所以自下而上的调用 Max-Heapify 能够在改造过程中保持这一性质。如果最大堆的数量元素是 n，那么 Build-Max-Heap 从 Parent(n) 开始，往上依次调用 Max-Heapify。流程如下：
public void buildHeap(int[] array) {
int n = array.length;// 数组中元素的个数
for (int i = n / 2 – 1; i >= 0; i–)
heapify(array, i, n);
}
堆排序
堆排序（Heap-Sort）先调用Build-Max-Heap将原数组改造为最大堆，这个时候堆顶元素最大，将其与堆底（当前堆对应数组的最后一个元素）交换，堆的大小减去1，当前堆堆底后面的元素已经排好序。然后，从堆顶元素开始检查，调用Max-Heapify保持最大堆性质，这样可以将第二大的元素调到堆顶，然后将其与当前堆堆底元素交换。重复这个过程n-1次，直到堆中只有1个元素为止。整个流程如下：
完整代码实现
public class HeapSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int len = arr.length;
buildMaxHeap(arr, len);
for (int i = len – 1; i > 0; i–) {
swap(arr, 0, i);
len–;
heapify(arr, 0, len);
}
return arr;
}
private void buildMaxHeap(int[] arr, int len) {
for (int i = (int) Math.floor(len / 2); i >= 0; i–) {
heapify(arr, i, len);
}
}
private void heapify(int[] arr, int i, int len) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest, len);
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
参考
http://lioncruise.github.io/2016/10/30/heap-sort/