c#排序算法之堆排序

发布时间：2010年9月14日 / 分类：DOTNET / 8,461 次浏览 / 评论

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

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