堆排序
空间复杂度O(1)
时间复杂度O(nlogn)
插入:从队尾插入
删除:由队尾元素代替
然后进行heapadjust();
void BuildMaxheap(int num[], int len) {
int i = 0;
for (i = len / 2;; i--) {//从分支节点开始,
HeapAdjust(num,i,len);
}
}
void HeapAdjust(int num[], int k, int len) {
num[0] = num[k];
for (int i =k*2 ; i < len; i *= 2) {//
if (num[i] < num[i + 1] && i < len)
i++;//选取值较大的结点
if (num[i] > num[0]) {//将节点值大的放到前面
num[k] = num[i];
k = i;
}
else break;
}
num[k] = num[0];
}
void HeapSort(int num[], int len) {
BuildMaxheap(num,len);
for (int i = len; i > 1; i--) {
swap(num[1], num[i]);
HeapAdjust(num, 1, i - 1);
}
}