• 热门专题

Unity Heap sort用Unity动态演示堆排序的过程(How Heap Sort Works)

作者:BIT祝威  发布日期:2015-06-18 00:23:28
Tag标签:过程  动态  
  • How Heap Sort Works

     

    最近做了一个用Unity3D动态演示堆排序过程的程序。

    I've made this app to show how heap sort works recently.

    效果图(Demo)

    一图抵千言。

    A picture paints a thousand words.

    您可以在此查看完整的动态GIF效果图。博客园里放不下这么大的GIF图。

    链接:http://pan.baidu.com/s/1kT051pd 密码:zpy3 

    You can check out the whole gif here. THe blog don't support a big gif like it.

    Link:http://pan.baidu.com/s/1kT051pd password:zpy3 

    堆排序(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.

     1         private static void HeapSortAscending1<T>(this IList<T> arr)
     2             where T : IComparable
     3         {
     4             for (int i = arr.Count / 2 - 1; i >= 0; i--)
     5             {
     6                 arr.HeapAdjustAscending1(i, arr.Count);
     7             }
     8             for (int i = arr.Count - 1; i > 0; i--)
     9             {
    10                 T temp = arr[0];
    11                 arr[0] = arr[i];
    12                 arr[i] = temp;
    13                 arr.HeapAdjustAscending1(0, i);
    14             }
    15         }
    16         private static void HeapAdjustAscending1<T>(this IList<T> arr, int nonLeafNodeToBeAdjusted, int unRangedCount)
    17             where T:IComparable
    18         {
    19             int leftChild = nonLeafNodeToBeAdjusted * 2 + 1;
    20             int rightChild = nonLeafNodeToBeAdjusted * 2 + 2;
    21             int max = nonLeafNodeToBeAdjusted;
    22             if (nonLeafNodeToBeAdjusted < unRangedCount / 2) // 是非叶节点(None leaf node)
    23             {
    24                 if (leftChild < unRangedCount && arr[leftChild].CompareTo(arr[max]) > 0)
    25                 { max = leftChild; }
    26                 if (rightChild < unRangedCount && arr[rightChild].CompareTo(arr[max]) > 0)
    27                 { max = rightChild; }
    28                 if (max!=nonLeafNodeToBeAdjusted)
    29                 {
    30                     T temp = arr[max];
    31                     arr[max] = arr[nonLeafNodeToBeAdjusted];
    32                     arr[nonLeafNodeToBeAdjusted] = temp;
    33                     arr.HeapAdjustAscending1(max, unRangedCount);
    34                 }
    35             }
    36         }
    Heap sort 

    下载(Download)

    您可以在此下载安卓APK。如果需要源码,请捐赠10元并留下您的邮箱。

    You can download the HowHeapSortWorks.apk for android below here.

    链接:http://pan.baidu.com/s/1c0GYIaO 密码:hlvi

    Link:http://pan.baidu.com/s/1c0GYIaO password:hlvi

    If you want the source code, please kindly donate ¥10 and leave your email adress:)

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规