//排序數(shù)組生成堆的方法
? 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;//左孩子的下標(biāo)
? ? //如果孩子節(jié)點(diǎn)下標(biāo)大于父節(jié)點(diǎn)的，說(shuō)明已經(jīng)不滿足條件了，已經(jīng)成堆了
? ? while (child < totalSize) {
? ? ? //選出左右孩子中最小的那個(gè)
? ? ? if ((child + 1 < totalSize) && (sortArray[child+1] < sortArray[child])) {
? ? ? ? child ++;
? ? ? }
? ? ? //如果最小的孩子比父節(jié)點(diǎn)的小,需要交換位置
? ? ? if (sortArray[child] < sortArray[parent]) {
? ? ? ? int replaceObject = sortArray[child];
? ? ? ? sortArray[child] = sortArray[parent];
? ? ? ? sortArray[parent] = replaceObject;
? ? ? ? parent = child;//父節(jié)點(diǎn)交換到了孩子節(jié)點(diǎn)
? ? ? ? child = parent*2+1;//計(jì)算新的孩子節(jié)點(diǎn)
? ? ? }else
? ? ? {
? ? ? ? //不滿足的話就跳出循環(huán)
? ? ? ? break;
? ? ? }
? ? }
? }
//待排序數(shù)組
? ? ? ? ? var sortArray = [1,2,5,1000,500,200,49,100,50,40,30,20];
? ? ? ? ? //存放排好序的數(shù)據(jù)
? ? ? ? ? var finishArray = [];
? ? ? ? ? //打印待排序數(shù)組
? ? ? ? ? print(sortArray);
? ? ? ? ? for (var i = 0; i < sortArray.length; i++) {
? ? ? ? ? ? createPile(sortArray, i);//創(chuàng)建小頂堆
? ? ? ? ? }
? ? ? ? ? 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("排完序的數(shù)組${finishArray}");
