1.堆
堆，其实是一个完全二叉树，分为大顶堆和小顶堆。
大顶堆：每个节点的值都大于或者等于其左右子节点的值
小顶堆：每个节点的值都小于或者等于其左右子节点的值
注意：堆中某个节点的左右子节点的值的大小关系没有要求，即左子节点的值可以大于、可以等于、也可以小于右子节点的值。
升序采用大顶堆、降序采用小顶堆。
2.堆排序
首先将 n 个元素的待排序序列构建成一个大顶堆，这样待排序序列的第一个元素(即大顶堆的根节点)就是最大的元素。
然后，将这个最大的元素与最后一个元素交换(即，根节点与最后一个叶子结点交换)
对剩下的前 n-1 个元素(即，除去最大元素的剩下的元素)重新执行上述步骤。
3.代码如下
构建大顶堆
从最后一个非叶子节点开始，叶子结点自然不用调整，最后一个非叶子节点为array.length/2-1.
交换 外汇常见问题http://www.fx61.com/faq
交换完成之后，剩下的元素还需要调整成堆结构
public class HeapSort {
public static void main(String[] args) {
int[] array = {4,6,8,5,9,7,3,1,2};
heapSort(array);
System.out.println(Arrays.toString(array));
}
public static void heapSort(int[] array){
int temp = 0;
for (int i = array.length/2-1; i >= 0 ; i--) {
toHeap(array,i,array.length);
}
for (int j = array.length-1; j > 0 ; j--) {
temp = array[j];
array[j] = array[0];
array[0] = temp;
toHeap(array,0,j);
}
}
public static void toHeap(int[] array, int i, int length){
int temp = array[i];
for (int k = 2*i+1; k < length; k = k*2+1){
if (k+1
k++;
}
if (array[k]>temp){
array[i] = array[k];
i = k;
}else {
break;
}
}
array[i] = temp;
}
}
时间复杂度
最好、最坏、平均时间复杂度都为 O(nlogn)，是不稳定排序。
|
|
收藏
淘帖
踩
