//排序數組生成堆的方法
? 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;
? ? ? }
? ? }
? }
? //刪除堆定元素后從新創(chuàng)建堆的方法
? void sortPile(List sortArray, int totalSize, int rootIndex){
? ? int parent = rootIndex;
? ? int child = parent*2+1;//左孩子的下標
? ? //如果孩子節(jié)點下標大于父節(jié)點的录别，說明已經不滿足條件了色解，已經成堆了
? ? while (child < totalSize) {
? ? ? //選出左右孩子中最小的那個
? ? ? if ((child + 1 < totalSize) && (sortArray[child+1] > sortArray[child])) {
? ? ? ? child ++;
? ? ? }
? ? ? //如果最小的孩子比父節(jié)點的小,需要交換位置
? ? ? if (sortArray[child] > sortArray[parent]) {
? ? ? ? int replaceObject = sortArray[child];
? ? ? ? sortArray[child] = sortArray[parent];
? ? ? ? sortArray[parent] = replaceObject;
? ? ? ? parent = child;//父節(jié)點交換到了孩子節(jié)點
? ? ? ? child = parent*2+1;//計算新的孩子節(jié)點
? ? ? }else
? ? ? {
? ? ? ? //不滿足的話就跳出循環(huán)
? ? ? ? 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);//創(chuàng)建大頂堆
? ? ? ? ? }
? ? ? ? ? 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}");
