一、堆排序

对所有记录建立最大值堆（也可以用最小值堆），取出堆顶的最大记录，重新建堆。不断重复这一操作，直到堆为空得到有序序列。与归并排序类似，堆排序不依赖于原始数组的有序程度，避免了快速排序的最差情况。