选择排序算法：堆排序-Heap Sort

基本思想

• 排序思想
  用最大堆排序的基本思想：

  1. 先将初始文件R[1..n]建成一个最大堆，此堆为初始的无序堆。

  2. 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得 到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key。

  3. 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。 然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由 此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系 R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。

  算法实现
  最大堆排序算法，Java实现，代码如下所示：

public abstract class Sorter {
public abstract void sort(int[] array);     
}

public class HeapSorter extends Sorter {
public void sort(int[] array) {
          heapSort(array);  
     }

private void heapSort(int[] array) {
int temp; // 用于交换的暂存单元
     buildMaxHeap(array); // 执行初始建堆，并调整

for (int i = array.length - 1; i > 0; i--) {
// 交换堆顶元素array[0]和堆中最后一个元array[i]
     temp = array[0];
     array[0] = array[i];
     array[i] = temp;
// 每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
     adjustHeapFixdown(array, 0, i);
     }
}

//建立最大堆 
void buildMaxHeap(int[] array)  
{  
// 求出当前堆中最后一个存在孩子结点的索引
int pos = (array.length - 1) / 2;
// 从该结点结点开始，执行建堆操作
for (int i = pos; i >= 0; i--)  
// 在建堆过程中，及时调整堆中索引为i的结点
        adjustHeapFixdown(array, i, array.length);  
}

// 从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2 
void adjustHeapFixdown(int[] array, int i, int n)  
{  
int j, temp;  

    temp = array[i];  
// 当前待调整结点的左孩子结点的索引(i+1为当前调整结点的右孩子结点的索引)
    j = 2 * i + 1;  
while (j < n)  
    {  
if (j + 1 < n && array[j + 1] > array[j]) //在左右孩子中找最大的 
            j++;  
// 如果当前待调整结点大于等于它的左右孩子，则不需要调整，直接退出
if (array[j] <= temp)  
break;  
//把较大的子结点往上移动,替换它的父结点
        array[i] = array[j];      
// 重新设置待调整的下一个结点的索引 
        i = j;  
        j = 2 * i + 1;  
    }  
// 当前待调整的结点放到比其大的孩子结点位置上
    array[i] = temp;  
}  

排序过程

第一步：初始建堆
首先执行的初始建堆（在建堆的过程中需要调整堆）。

第二步：第一次交换

第三步：调整堆

算法分析

• 时间复杂度

  堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成。
  堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

• 空间复杂度

  堆排序过程中，需要调整堆，交换待排序记录需要一个临时存储单元，所以空间复杂度为O(1)。

• 排序稳定性

堆排序是不稳定的排序方法。