堆排序

作者：追风剑情发布于：2014-11-9 16:49 分类：Algorithms

堆是一棵顺序存储的完全二叉树，其中每个结点的关键字都不小于其孩子结点的关键字（称为大根堆，如果是进行从大到小的排序，则堆中每个结点的关键字都不大于其孩子结点的关键字，称为小根椎）。

在堆排序过程中，关键字的比较次数等于初始建堆所需的比较次数与每次调整新堆所需的比较次数之和，堆排序在最坏情况下所需的比较次数不超过,显然，元素的移动次数也不超过，堆排序是不稳定的。

开发工具：Visual Studio 2010

开发语言：C#

using System;
 
namespace HeapSortTest
{
    class Program
    {
        static void Main(string[] args)
        {
            //有效数据从R[1]开始
            int[] R = new int[] {0, 75, 87, 68, 92, 88, 61, 77, 96, 80, 72 };
            int n = R.Length - 1;
            int i;
 
            Console.WriteLine("排序前:");
            for (i = 1; i <= n; i++)
                Console.Write(R[i]+" ");
            Console.WriteLine();
 
            HeapSort(R, n);
            Console.WriteLine("排序后：");
            for (i = 1; i <= n; i++)
                Console.Write(R[i] + " ");
 
            Console.Read();
        }
 
        // 筛选函数
        static void Sift(int[] R, int low, int high)
        {
            int i = low, j = 2 * i;//R[j]是R[i]的左孩子
            int tmp = R[i];
            while(j<=high){
                //若右孩子较大，把j指向右孩子
                if(j<high && R[j] < R[j+1]){
                    j++;//j变为2i+1,指向右孩子结点
                }
                if (tmp < R[j])
                {
                    R[i] = R[j];//将R[j]调整到双亲结点位置上
                    i = j;//修改i和j的值，以便继续向下筛选
                    j = 2 * i;
                } else {
                    break;//筛选结束
                }
            }
            R[i] = tmp;//被筛选结点的值放入最终位置
        }
 
        /**
         * 堆排序
         * 初始建堆工作可以通过反复筛选来完成：从完全二叉树的最后一个分支结点R[i]
         * (其中i=n/2)开始，通过调用算法Sift(R,j,n)(其中j=i,i-1,...,1),依次将以
         * R[i],R[i-1],...,R[1]为根的子树调整为堆。
         */
        static void HeapSort(int[] R, int n)
        {
            int i;
            int tmp;
            //循环建立初始堆
            for (i = n / 2; i >= 1; i--)
                Sift(R,i,n);
            //进行n-1次循环，完成堆排序
            for (i = n; i >= 2; i--)
            {
                tmp = R[1];
                R[1] = R[i];
                R[i] = tmp;
                //筛选R[1]结点，得到i-1个结点的堆
                Sift(R,1,i-1);
            }
        }
    }
}