数据结构-排序-堆排序
面5笔5堆排序的原理?
是对直接选择排序的改进,不稳定,时间复杂度 O(nlogn),空间复杂度 O(1)。
将待排序记录看作完全二叉树,可以建立大根堆或小根堆,大根堆中每个节点的值都不小于它的子节点值,小根堆中每个节点的值都不大于它的子节点值。
以大根堆为例,在建堆时首先将最后一个节点作为当前节点,如果当前节点存在父节点且值大于父节点,就将当前节点和父节点交换。
在移除时首先暂存根节点的值,然后用最后一个节点代替根节点并作为当前节点,如果当前节点存在子节点且值小于子节点,就将其与值较大的子节点进行交换,调整完堆后返回暂存的值。
public void add(int[] nums, int i, int num){
nums[i] = num;
int curIndex = i;
while (curIndex > 0) {
int parentIndex = (curIndex - 1) / 2;
if (nums[parentIndex] < nums[curIndex])
swap(nums, parentIndex, curIndex);
else break;
curIndex = parentIndex;
}
}
public int remove(int[] nums, int size){
int result = nums[0];
nums[0] = nums[size - 1];
int curIndex = 0;
while (true) {
int leftIndex = curIndex * 2 + 1;
int rightIndex = curIndex * 2 + 2;
if (leftIndex >= size) break;
int maxIndex = leftIndex;
if (rightIndex < size && nums[maxIndex] < nums[rightIndex])
maxIndex = rightIndex;
if (nums[curIndex] < nums[maxIndex])
swap(nums, curIndex, maxIndex);
else break;
curIndex = maxIndex;
}
return result;
}