阅读 5

堆排序

转载博客

此人写的太好,而且很简单易懂,我只能全部拿过来,下面是链接。

定义

堆排序是一种树形选择排序,在排序过程中可以把元素看成是一颗完全二叉树,每个节点都大(小)于它的两个子节点,当每个节点都大于等于它的两个子节点时,就称为大顶堆,也叫堆有序; 当每个节点都小于等于它的两个子节点时,就称为小顶堆

大顶堆
小顶堆

算法思想

1.将长度为n的待排序的数组进行堆有序化构造成一个大顶堆 2.将根节点与尾节点交换并输出此时的尾节点 3.将剩余的n -1个节点重新进行堆有序化 4.重复步骤2,步骤3直至构造成一个有序序列 假设待排序数组为[20,50,10,30,70,20,80]

构造堆

  • 在构造有序堆时,我们开始只需要扫描一半的元素(n/2-1 ~ 0)即可,为什么? 因为(n/2-1)~0的节点才有子节点,如图1,n=8,(n/2-1) = 3 即3 2 1 0这个四个节点才有子节点
    初始状态
  • 需要将将3 2 1 0这四个节点从下到上,从右到左的与它自己的子节点比较并调整最终形成大顶堆,过程如下: 第一次for循环将节点3和它的子节点7 8的元素进行比较,最大者作为父节点(即元素60作为父节点)红色便是交换后的状态
  • 第二次for循环将节点2和它的子节点5 6的元素进行比较,最大者为父节点(元素80作为父节点)
  • 第三次for循环将节点1和它的子节点3 4的元素进行比较,最大者为父节点(元素70作为父节点)
  • 第四次for循环将节点0和它的子节点1 2的元素进行比较,最大者为父节点(元素80作为父节点)
  • (注意这里,元素20和元素80交换后,20所在的节点还有子节点,所以还要再和它的子节点5 6的元素进行比较,这就是while语句里为什么药index = now 的原因) 至此有序堆已经构造好了!如下图:

调整堆

  • 堆顶元素80和尾40交换后-->调整堆
  • 堆顶元素70和尾30交换后-->调整堆
  • 堆顶元素60尾元素20交换后-->调整堆
  • 其他依次类推,最终已排好序的元素如下:

实现代码

终于到了贴代码,代码借鉴了原博主的思想,然后自己实现了一遍,加深印象。

namespace Algorithm.DataStructure.Sort
{
    class HeapSort:SortData
    {
        public HeapSort():base()
        {
            name = "===================堆排序";
        }

        public override void Sort(int[] array)
        {
            for(int i = array.Length /2 - 1;i>= 0;i--) //先建立堆底,堆上面放生变化可以在调整下面,
            {
                Sort(array, array.Length,i);
            }
            for(int i = array.Length - 1;i>=0;i--)
            {
                int temp = array[i];
                array[i] = array[0];
                array[0] = temp;
                Sort(array, i, 0);//堆顶和堆底交换后,去掉原来的堆顶,重新建立堆
            }
        }

        public void Sort(int []array,int len,int index)
        {
            int left = index * 2 + 1; //左子
            int right = left + 1;//右子
            int now = left; //左右子中比较大的一个,默认左子大
            while(left < len) //索引不能大于长度
            {
                right = left + 1;
                now = left;
                if(right < len && array[now] < array[right])
                {
                    now = right; //更新最大的那个孩子的索引
                }
                if(array[now] > array[index]) //交换孩子和父亲的值
                {
                    int temp = array[index];
                    array[index] = array[now];
                    array[now] = temp;
                }
                else //符合大顶堆,不需要交换
                {
                    break;
                }

                index = now;//堆顶或者堆中间变化,需要查看当前值的孩子是否受影响
                left = index * 2 + 1;
            }
        }
    }
}

复制代码
关注下面的标签,发现更多相似文章
评论