堆排序
算法介绍
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序。 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。 将堆的节点编号作为一维数组下标可以得到
如图所示，堆具有如下特征： 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] 堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列。
代码
public class heap_sort{
public static void sort(int[] array
){
for(int i
= array
.length
/2 - 1; i
> 0; i
--){
adjust_heap(array
,i
,array
.length
);
}
for(int j
= array
.length
-1; j
> 0; j
--){
swap(array
,0,j
);
adjust_heap(array
,0,j
);
}
}
public static void adjust_heap(int array
, int index
, int len
){
int temp
= array
[index
];
for(int i
= index
; i
< len
; i
= i
*2 + 1){
if(i
+ 1 < len
&& array
[i
] < array
[i
+1])
i
++;
if(array
[i
] > temp
){
array
[index
] = array
[i
];
index
= i
;
}
else
break;
}
array
[index
] = temp
;
}
public static void swap(int[] array
, int i
, int j
){
int temp
= array
[i
];
array
[i
] = array
[j
];
array
[j
] = temp
;
}
}
复杂度分析
堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。它的最坏，最好，平均时间复杂度均为O(nlogn) 且为不稳定排序。
