堆排序算法

winzhi

// Heap Sort
(*
先将数组元素建堆，形成完全二叉树结构；
然后子父节点比较交换，使得父节点最大，建立大根堆；
再交换堆首和堆尾，并移出堆尾(最大值)；重新建立大根堆；
循环往复，直至所有元素移出。
*)


FOR #i := #Length / 2 - 1 TO 0 BY -1 DO   // 初始化，i从最后一个父节点开始调整
    "Heapify"(asc := #Asc_Des,
              start := #i,
              end := #Length - 1,
              ARR := #Sort_Arr);
END_FOR;

// 先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
//
FOR #i := #Length - 1 TO 1 BY -1 DO
    #swap := #Sort_Arr[0];
    #Sort_Arr[0] := #Sort_Arr[#i];
    #Sort_Arr[#i] := #swap;
    "Heapify"(asc := #Asc_Des,
              start := 0,
              end := #i - 1,
              ARR := #Sort_Arr);
END_FOR;