波斯马BOSSMA Information Technology

c#排序算法之堆排序

发布时间:2010年9月14日 / 分类:DOTNET / 7,802 次浏览 / 评论

堆排序(HeapSort)是一树形选择排序。堆排序的特点是:在排序过程中,将R[l..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系,在当前无序区中选择关键字最大(或最小)的记录。堆排序的时间,主要由建立初始]堆和反复重建堆这两部分的时间开销构成。

        static void HeapSort(int[] intArr)
        {
            int numberOfLoop = 0;
            int numberOfSwap = 0;

            //第一次创建大堆   
            for (int i = intArr.Length / 2 - 1; i >= 0; i--)
            {
                numberOfLoop++;
                HeapAdjust(intArr, i, intArr.Length, ref numberOfLoop, ref numberOfSwap);
            }

            //元素位置调换,无序区通过调整为有序区,获得最大的值   
            for (int i = intArr.Length - 1; i > 0; i--)
            {
                numberOfLoop++;
                numberOfSwap++;

                //堆顶(最大值)与当前堆的最后一个堆元素交换位置   
                int tmp = intArr[0];
                intArr[0] = intArr[i];
                intArr[i] = tmp;

                //将剩下的无序堆部分重新建堆处理,因为只是将最大值转移,因此只需要一轮排序,获取最大值  
                HeapAdjust(intArr, 0, i, ref numberOfLoop, ref numberOfSwap);
            }

            DisplaySortResult(numberOfLoop, numberOfSwap, intArr);
        }

static void HeapAdjust(int[] intArr, int i, int length, ref int numberOfLoop, ref int numberOfSwap)
        {
            int temp = intArr[i];
            int child = 2 * i + 1;

            while (child < length)
            {
                //如果存在右节点,且大于左节点,child++
                if (child < length - 1 && intArr[child] < intArr[child + 1])
                {
                    numberOfLoop++;
                    child++;
                }

                //父节点大于左右子节点,跳出循环
                if (temp >= intArr[child]) break;

                numberOfSwap++;

                //否则设置父节点为最大的子节点值
                intArr[i] = intArr[child];

                i = child;
                child = 2 * i + 1;
            }

            numberOfSwap++;
            intArr[i] = temp;
        }

和快速排序相比,速度差不多。

本博客所有文章如无特别注明均为原创。
复制或转载请以超链接形式注明转自波斯马,原文地址《c#排序算法之堆排序

关键字:

建议订阅本站,及时阅读最新文章!
【上一篇】 【下一篇】

发表评论