//排序数组生成堆的方法
void createPile(List sortArray, int childIndex)
{
int child = childIndex;
int parent = (child-1) ~/ 2;
while (child > 0) {
if (sortArray[child] > sortArray[parent]) {
int replaceObject = sortArray[child];
sortArray[child] = sortArray[parent];
sortArray[parent] = replaceObject;
child = parent;
parent = (child-1) ~/ 2;
}else
{
break;
}
}
}
//删除堆定元素后从新创建堆的方法
void sortPile(List sortArray, int totalSize, int rootIndex){
int parent = rootIndex;
int child = parent*2+1;//左孩子的下标
//如果孩子节点下标大于父节点的，说明已经不满足条件了，已经成堆了
while (child < totalSize) {
//选出左右孩子中最小的那个
if ((child + 1 < totalSize) && (sortArray[child+1] > sortArray[child])) {
child ++;
}
//如果最小的孩子比父节点的小,需要交换位置
if (sortArray[child] > sortArray[parent]) {
int replaceObject = sortArray[child];
sortArray[child] = sortArray[parent];
sortArray[parent] = replaceObject;
parent = child;//父节点交换到了孩子节点
child = parent*2+1;//计算新的孩子节点
}else
{
//不满足的话就跳出循环
break;
}
}
}
//待排序数组
var sortArray = [1,2,5,1000,500,200,49,100,50,40,30,20];
//打印待排序数组
print(sortArray);
for (var i = 0; i < sortArray.length; i++) {
createPile(sortArray, i);//创建大顶堆
}
for (var i = 0; i < sortArray.length; i++) {
//把堆的第一个元素和最后一个元素交换位置，堆顶的最大元素放到了最后边
int replaceObject = sortArray[0];
int lastIndex = sortArray.length-1-i;
sortArray[0] = sortArray[lastIndex];
sortArray[lastIndex] = replaceObject;
//从新建大顶堆
sortPile(sortArray, sortArray.length-i-1, 0);
}
print("排完序的数组${sortArray}");
网友评论