//排序数组生成堆的方法
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];
//存放排好序的数据
var finishArray = [];
//打印待排序数组
print(sortArray);
for (var i = 0; i < sortArray.length; i++) {
createPile(sortArray, i);//创建小顶堆
}
while (sortArray.length > 0) {
//取出小顶堆的堆顶元素
finishArray.add(sortArray.first);
//交换堆顶元素和堆底元素位置
int replaceObject = sortArray[0];
sortArray[0] = sortArray[sortArray.length-1];
sortArray[sortArray.length-1] = replaceObject;
//移除堆底元素，也就是小顶堆的堆顶元素
sortArray.removeAt(sortArray.length-1);
//从新生成小顶堆
sortPile(sortArray, sortArray.length, 0);
}
print("排完序的数组${finishArray}");
网友评论