堆排序
堆排序是通过构建堆来对元素进行排序的。主要分为两个步骤：堆的构建和下沉排序。
第一步堆的构建：就是将无序的元素构建成堆，这一步完成之后，元素就成为堆有序的元素。这一步骤可以通过上浮或下沉来完成。因此，当我们完成堆的构建之后，最大的元素就在二叉树的根节点上。此时，就该进行第二步了。
第二步就是下沉排序：此时，我们已经得到了一个堆有序的元素集合，我们要做的就是通过把最大的元素也就是根节点上的元素与最后一个元素交换位置，交换之后“堆有序”的状态被打破，我们需要再次通过下沉排序来将根节点上的元素下沉到合适的位置，但与第一次构建堆时不同的是，这次下沉的范围应该把最后一个位置排除掉，因为那里放着最大的元素，那个就是它最终的位置。不断重复这个过程，下沉排序的范围也在一直缩小，最终只剩下了根节点自己，堆排序也就完成了。
堆（二叉堆）：二叉堆是一组能够用堆有序的二叉树排序的元素，并在数组中按照层级存储（不适用数组第一个位置）
为什么不适用第一个位置：为了方便表示结点的父结点和子结点。只要不适用第一个结点也就是下标为0的位置，那么任何一个元素，比如i的父结点位置就是i/2向下取整,子结点位置就是2i和2i+1
堆有序：当一颗二叉树的每个结点都大于等于他的两个子结点时，它被称为堆有序。 上浮和下沉：两种达到堆有序的方法。结点不断地和父结点交换位置到达堆有序叫做上浮，不断的跟子结点交换位置达到堆有序叫做下沉。
查看堆排序动画演示请回复：堆排序动画
public class Heap {
public static int temp;
public static void sort(int[] array){
int N = array.length;
int[] newarray = new int[N+1];
System.arraycopy(array, 0, newarray, 1, N);
sort(newarray,true);
System.arraycopy(newarray, 1, array, 0, N);
}
public static void sort(int[] array,boolean flag){
int N = array.length-1;
//堆的构建
for (int i=N/2;i>=1;i--){
sink(array,i,N);
}
//下沉排序
while (N>1){
temp = array[1];
array[1]=array[N];
array[N]=temp;
sink(array,1,--N);
}
}
//小的元素下沉
private static void sink(int[] array, int k, int N) {
while (2*k<=N){
int j = 2*k;
if (j<N&&array[j]<array[j+1])j++;
if (array[k]>=array[j])break;
temp = array[k];
array[k] = array[j];
array[j] = temp;
k=j;
}
}
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-05-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读