排序算法总结之堆排序

一，堆排序介绍堆是一个优先级队列，对于大顶堆而言，堆顶元素的权值最大。将待排序的数组建堆，然后不断地删除堆顶元素，就实现了排序。关于堆，参考：数据结构--堆的实现之深入分析 http://www.linuxidc.com/Linux/2016-05/131796.htm下面的堆排序算法将数组中的元素从小到大排序，用大顶堆来实现。二，堆排序算法分析 现给定了一维数组，需要将数组中的元素使用堆排序。首先，得创建一个堆，可以在这个给定的一维数组上建堆。对N个元素建堆的时间复杂度为O（N）堆排序具体的细节实现有两种方式：一种方式是将堆顶元素删除后，放到一个辅助数组中，然后进行堆调整使之成为一个新。继续删除堆顶元素，直至将堆中所有的元素都出堆，此时排序完成。这种方式需要一个额外的辅助空间O（N）另一种方式是：将每次删除的堆顶元素放到数组的末尾。因为，对于堆的基本操作 delMin/delMax 而言（delMin针对的是小顶堆，delMax针对的是大顶堆，原理一样）是将堆中的最后一个元素替换堆顶元素，然后向下进行堆调整。因此，可以利用这个特点将每次删除的堆顶元素保存在数组末尾，当所有的元素都出堆后，数组就排好序了。这种方式不需要额外的辅助空间，空间复杂度为O（1）三，堆排序算法实现public class HeapSort {

public static <T extends Comparable<？ super T>> void heapSort（T[] arr）{
//build heap
for（int i = arr.length/2 - 1; i >= 0; i--）
percDown（arr, i, arr.length）;

for（int i = arr.length - 1; i >= 0; i--）
{
swapReference（arr, 0, i）;//delete Max

percDown（arr, 0, i）;// 从根开始向下堆调整
}
}

private static <T extends Comparable<？ super T>> void swapReference（T[] arr, int from, int to）{
T tmp;
tmp = arr[from];
arr[from] = arr[to];
arr[to] = tmp;
}

//求解 i 的左孩子
private static int leftChild（int i）{
return 2*i + 1;
}

/**
*
* @param arr 存储堆的一维数组
* @param i 从 i 位置开始进行向下堆调整
* @param n 堆中元素的个数（不是数组的长度）
*/
private static <T extends Comparable<？ super T>> void percDown（T[] arr, int i, int n）{
int child;
T tmp;//保存当前待调整的结点，当找到了合适的位置后，需要将之放入到合适位置，以保持堆序性质

for（tmp = arr[i]; leftChild（i） < n; i = child）
{
child = leftChild（i）;
if（child ！= n-1 && arr[child].compareTo（arr[child+1]） < 0）
child++;//右孩子更大
if（tmp.compareTo（arr[child]） < 0）
arr[i] = arr[child];//父节点下移
else
break;//父节点比左右孩子都大时,不需要再向下移动了
}
arr[i] = tmp;//将节点放入合适的位置
}

//for test purpose
public static void main（String[] args） {
Integer[] arr = {31,41,59,26,53,58,97};
heapSort（arr）;
for （Integer i : arr） {
System.out.print（i + " "）;
}
}
}有几个细节地方解释一下：①在第3行的heapSort方法中，第5-6行是建堆操作，因为数组中的元素是从下标0开始存储的，故最后一个非叶子结点的下标为：arr.length/2 - 1②第9-14行是进行堆排序的操作。swapReference方法相当于删除堆顶元素，因为它把堆顶元素交换到数组的末尾去了，此时堆顶元素不再是最大值（大顶堆）。删除了堆顶元素之后，就要进行堆调整以保持堆序性质，故percDown方法完成向下进行堆调整的功能。③在堆调整的过程中，需要求解某个结点的左右孩子结点的位置。故有一个leftChild方法用来求解左孩子的位置（注意元素是从数组下标0开始存储的）④percDown方法实现向下的堆调整功能。第37行 tmp 变量保存当前待调整的结点，当找到了合适的位置后，需要将之放入到合适位置，以保持堆序性质。对于建堆而言，待调整的结点是从非叶结点开始，直至根的那些结点。对于删除堆顶元素而言，则总是从堆顶元素起开始调整（待调整的结点是根）⑤第39行的for循环实现得非常巧妙，首先tmp保存当前待调整的结点 arr[i]，然后判断 arr[i] 是否有左孩子，如果有左孩子的话，又在第42行的if语句中判断它是否还有右孩子（child ！= n-1），然后左右孩子进行比较，child记录下权值大的那个孩子。⑥第44-45行的if语句完成的功能是：将权值大的孩子与父结点比较，如果父结点的权值小，则需要将那个较大的孩子上移到父结点的位置（也相当于父结点下移到孩子的位置）如果父结点的权值大，已经找到了合适的位置了。说明不需要再进行堆调整了，执行else break;⑦第49行，就待调整的结点入到到合适的位置i处。整个过程并没有用交换操作，而是用的是赋值操作来隐式地实现了交换操作完成的功能，这是一个优化。 四，堆排序算法复杂度分析对N个元素建堆的时间复杂度为O（N），删除堆顶元素的时间复杂度为O（logN），尽管随着元素的不断删除，堆的调度越来越小，但是总的而言，删除堆所有元素的时间复杂度为O（NlogN）故堆排序的时间复杂度为O（NlogN），空间复杂度为O（1）其实，堆排序是一个非常稳定的算法，最坏和平均情况下的时间复杂度都为O（NlogN）此外，对于堆排序而言，数据的初始顺序对它的复杂度没有影响。不管数组初始时就是有序的还是逆序的，它都会先建堆，变成了堆序的性质。本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-05/131795.htm