[Unity][Heap sort]用Unity动态演示堆排序的过程
How Heap Sort Works
最近做了一个用Unity3D动态演示堆排序过程的程序。
I've made this app to show how heap sort works recently.
效果图(Demo)
一图抵千言。
A picture paints a thousand words.
堆排序(Heap Sort)
堆排序总是建立这样一个二叉树：其父结点总大于其子结点。
Step 1: The first step of heap sort is to build a binary tree in which the parent node's value is always greater than its children nodes' value.
首先建堆。
It's called building the heap.
每轮将根结点与最后一个结点互换，然后对剩余部分建堆。
Step 2: Ater that, we swap the root node and the last node that hasn't been swapped yet.
Step 3: build the heap again like in step 1.
Step 4: if not all nodes are swapped in Step 2, goto Step2. Otherwise goto step 5.
Step 5: the heap sort is finished.
private static void HeapSortAscending1<T>(this IList<T> arr)
where T : IComparable
{
for (int i = arr.Count / - ; i >= ; i--)
{
arr.HeapAdjustAscending1(i, arr.Count);
}
for (int i = arr.Count - ; i > ; i--)
{
T temp = arr[];
arr[] = arr[i];
arr[i] = temp;
arr.HeapAdjustAscending1(, i);
}
}
private static void HeapAdjustAscending1<T>(this IList<T> arr, int nonLeafNodeToBeAdjusted, int unRangedCount)
where T:IComparable
{
int leftChild = nonLeafNodeToBeAdjusted * + ;
int rightChild = nonLeafNodeToBeAdjusted * + ;
int max = nonLeafNodeToBeAdjusted;
if (nonLeafNodeToBeAdjusted < unRangedCount / ) // 是非叶节点(None leaf node)
{
if (leftChild < unRangedCount && arr[leftChild].CompareTo(arr[max]) > )
{ max = leftChild; }
if (rightChild < unRangedCount && arr[rightChild].CompareTo(arr[max]) > )
{ max = rightChild; }
if (max!=nonLeafNodeToBeAdjusted)
{
T temp = arr[max];
arr[max] = arr[nonLeafNodeToBeAdjusted];
arr[nonLeafNodeToBeAdjusted] = temp;
arr.HeapAdjustAscending1(max, unRangedCount);
}
}
}
Heap sort
下载(Download)
如需APK安装包，请留言留下您的邮箱。如果需要源码，请捐赠100元并留下您的邮箱。
If you want the HowHeapSortWorks.apk, please leave your email address.
If you want the source code, please kindly donate ￥50 and leave your email adress:)
更新(Update)
2015-06-18
增加了'Random array'按钮，用于自动生成15个随机数，方便使用新case。
Added 'Random array' button which generates 15 random numbers as a new test case.
2015-06-21
在下方的数组显示索引。
display index for line nodes.
用表示堆所在层的颜色给下方的数组显示底色。
add background colors for line nodes.