数据结构与算法C#版笔记--排序(Sort)-下

5、堆排序(HeapSort)

在接触“堆排序”前,先回顾一下数据结构C#版笔记--树与二叉树 ,其中提到了“完全二叉树”有一些重要的数学特性:

上图就是一颗完全二叉树,如果每个节点按从上到下,从左至右标上序号,则可以用数组来实现顺性存储,同时其序号:

1、如果i>1,则序号为i的父结节序号为i/2(这里/指整除) 言外之意:整个数组前一半都是父节点,后一半则是叶节点

2、如果2*i<=n(这里n为整颗树的节点总数),则序号为i的左子节点序号为2*i

3、如果2*i +1 <=n,则序号为i的右子节点序号为2*i + 1

好了,再来看看"堆(Heap)"是个神马玩意儿?

其实,堆就是一颗完全二叉树,由上面的知识点回顾可以知道,任意给定一个数组,我们就能将它构造成一颗完全二叉树,也就是创建一个“堆”--ps:还好业内标准称它为一堆,而不是一坨 :)

其中,堆又可以分为最大堆与最小堆,下图就是一个最大堆:

简言之:每个(父)节点的值,都比其子节点值大,这样的堆就称为最大堆;反过来类推,如果每个(父)节点的值,都比其子节点小,就叫最小堆。

下面该"堆排序"(HeapSort)登场了,其思路为:

1、先将给定待排序的数组通过一定处理,形成一个“最大堆”

2、然后将根节点(root)与最后一个序号的节点(lastNode)对换,这样值最大的根节点,就“沉”到所有节点最后了(也就是垫底了),下轮处理就不用理会它了.

3、因为第2步的操作,剩下的这些节点肯定已经不满足最大堆的定义了(因为把小值的末节点换成根节点了,它的子节点中肯定会有值比它大的),然后再类似第1步的处理,把这些剩下的节点重新排成“最大堆”

4、重复第2步的操作,将“新最大堆的根节点”与“新最大堆的末结点”(其实就是整个数组的倒数第二个节点,因为在第一轮处理中,最大值的节点已经沉到最后了,所以新最大堆的最末节点就是整个数组的倒数第二个节点)对换,这样第二大的元素也沉到适当的位置了,以后就不用理它了,然后继续把剩下的节点,重组成最大堆

5、反复以上过程,直到最后剩下的节点只剩一个为止(即没办法再继续重组成最大堆),这时排序结束,最后剩下的节点,肯定就是值最小的

假设给定数组new int[] {1,3,5,6,4,2},要求用“堆排序算法”从小到大排序,上面的算法描述图解为:

理解以上思路后,堆排序就拆分成了二个问题:

A、如何将数组指定范围的N个元素创建一个"最大堆"?

B、如何用一定的算法,反复调用A中的"最大堆创建"方法,以处理剩下的节点,直到最终只剩一个元素为止

创建最大堆的算法,完全依赖于完全二叉树的数学特性,代码如下:

        /// <summary>
        /// 创建最大堆
        /// </summary>
        /// <param name="arr">待处理的数组</param>
        /// <param name="low">指定连续待处理元素范围的下标下限</param>
        /// <param name="high">指定连续待处理元素范围的下标上限</param>
        static void CreateMaxHeap(int[] arr, int low, int high)
        {
            if ((low < high) && (high <= arr.Length - 1))
            {
                int j = 0, k = 0, t = 0;

                //根据完全二叉树特性,前一半元素都是父节点,所以只需要遍历前一半即可
                for (int i = high / 2; i >= low; --i)
                {
                    k = i;
                    t = arr[i];//暂存当前节点值
                    j = 2 * i + 1;//计算左节点下标(注意:数组下标是从0开始的,而完全二叉树的序号是从1开始的,所以这里的2*i+1是左子节点,而非右子节点!)                    
                    while (j <= high) //如果左节点存在
                    {
                        //如果右节点也存在,且右节点更大
                        if ((j < high) && (j + 1 <= high) && (arr[j] < arr[j + 1]))
                        {
                            ++j;//将j值调整到右节点的序号,即经过该if判断后,j对应的元素就是i元素的左、右子节点中值最大的
                        }

                        //如果本身节点比子节点小
                        if (t < arr[j])
                        {
                            arr[k] = arr[j];//将自己节点的值,更新为左右子节点中最大的值

                            //然后保存左右子节点中最大元素的下标(因为实际上要做的是将最大子节点与自身进行值交换,
                            //上一步只完成了交换值的一部分,后面还会继续处理才能完成整个交换)
                            k = j;
                            j = 2 * k + 1;//交换后,j元素就是父节点了,然后重新以j元素为父节点,继续考量其"左子节点",准备进入新一轮while循环
                        }
                        else //如果本身已经是最大值了,则说明元素i所对应的子树,已经是最大堆,则直接跳出循环
                        {
                            break;
                        }
                    }
                    //接上面的交换值操作,将最大子节点的元素值替换为t(因为最近的一次if语句中,k=j 了,
                    //所以这里的arr[k]其实就是arr[j]=t,即完成了值交换的最后一步,
                    //当然如果最近一次的if语句为false,根本没进入,则这时的k仍然是i,维持原值而已)
                    arr[k] = t;
                }
            }
        }

反复调用该算法排序的代码:

        /// <summary>
        /// 堆排序
        /// </summary>
        /// <param name="arr"></param>
        static void HeapSort(int[] arr)
        {
            int tmp = 0;
            //初始时,将整个数组排列成"初始最大堆"
            CreateMaxHeap(arr, 0, arr.Length - 1);
            for (int i = arr.Length - 1; i > 0; --i)
            {
                //将根节点与最末结点对换
                tmp = arr[0];
                arr[0] = arr[i];
                arr[i] = tmp;
                //去掉沉底的元素,剩下的元素重新排列成“最大堆”
                CreateMaxHeap(arr, 0, i - 1);
            }
        }

点评:这是一种思维方式很独特的排序方式,时间复杂度跟快速排序类似,也是跟二叉树有关,为O(Nlog2N),同样它也是一种不稳定的排序。

6、归并排序算法(MergeSort)

思路:将数组中的每个元素看作一个小序列,然后二二合并成一个有序的新序列(这样序列个数从N变成了N/2,但是每个小序列的长度从1变成2),然后继续将这些新序列二二合并,得到N/4个序列(每个序列的长度从2变成4),如此反复,最终得到一个全部排列好的完整序列。这也是算法中"分治法"的经典案例之一,即分而治之。

这里反复要用到将二个序列合并为新序列的处理,封装成以下方法 :

        /// <summary>
        /// 归并处理
        /// </summary>
        /// <param name="arr">需要归并处理的数组</param>
        /// <param name="len">每段小序列的长度</param>
        static void Merge(int[] arr, int len)
        {
            int m = 0; //临时顺序表的起始位置
            int low1 = 0; //第1个有序表的起始位置
            int high1; //第1个有序表的结束位置
            int low2; //第2个有序表的起始位置
            int high2; //第2个有序表的结束位置
            int i = 0;
            int j = 0;
            //临时表,用于临时将两个有序表合并为一个有序表
            int[] tmp = new int[arr.Length];

            //归并处理
            while ((low1 + len) < arr.Length)
            {
                low2 = low1 + len; //第2个有序表的起始位置
                high1 = low2 - 1; //第1个有序表的结束位置

                //第2个有序表的结束位置
                high2 = ( (low2 + len - 1) < arr.Length) ? low2 + len - 1 : arr.Length - 1;
                                
                i = low1;
                j = low2;

                //如果二个有序表都还没整完
                while ((i <= high1) && (j <= high2))
                {

                    if (arr[i] <= arr[j])//如果 第1个有序表的元素小于第2个有序表的对应元素,则直接复制第1个有序表的元素到临时表
                    {
                        tmp[m++] = arr[i++];
                    }
                    else//否则,复制第2个有序表的元素到临时表
                    {
                        tmp[m++] = arr[j++];
                    }
                }

                //经过上面的处理后,如果第1个有序表还有元素
                while (i <= high1)
                {
                    tmp[m++] = arr[i++];
                }

                //经过上面的处理后,如果第2个有序表还有元素
                while (j <= high2)
                {
                    tmp[m++] = arr[j++];
                }

                low1 = high2 + 1;//将low1"指针"指到“处理完的2个有序表”之后,以方便下面将剩余未处理完的元素复制到临时表
            }

            i = low1;

            //将尚未处理到的元素复制到临时表
            while (i < arr.Length)
            {
                tmp[m++] = arr[i++];
            }

            //将临时表的元素复制到原数组
            for (i = 0; i < arr.Length; ++i)
            {
                arr[i] = tmp[i];
            }
        }

排序处理:

        /// <summary>
        /// 归并排序
        /// </summary>
        /// <param name="arr"></param>
        static void MergeSort(int[] arr)
        {
            int k = 1; //归并增量
            while (k < arr.Length)
            {
                Merge(arr, k);
                k *= 2;
            }
        }
    }

点评:俩俩合并,又是跟2有关的,哈哈,计算机领域真的很2啊!所以其时间复杂度又是O(Nlog2N),但是该算法需要很多的临时数组,所以其空间复杂度较其它算法都要大一些为O(N),此外它是稳定的排序方法。

排序方法小结:(原书的小结还算不错,就懒得自己再写了,直接从原电子书上copy过来记录下)

     排序在计算机程序设计中非常重要,上面介绍的各种排序方法各有优缺点,适用的场合也各不相同。

    在选择排序方法时应考虑的因素有:

   (1)待排序记录的数目 n 的大小;

   (2)记录本身除关键码外的其它信息量的大小;

   (3)关键码(即元素值)的情况;

   (4)对排序稳定性的要求;

   (5)语言工具的条件,辅助空间的大小等。

   综合考虑以上因素,可以得出如下结论:

   (1)若排序记录的数目 n 较小(如 n≤50)时,可采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多,因而当记录本身信息量较大时,用简单选择排序比较好。

   (2)若记录的初始状态已经按关键码基本有序,可采用直接插入排序或冒泡排序。

   (3)若排序记录的数目n较大,则可采用时间复杂度为O(nlog2n)的排序方法(如快速排序、堆排序或归并排序等)。

快速排序的平均性能最好,在待排序序列已经按关键码随机分布时,快速排序最适合。快速排序在最坏情况下的时间复杂度是O(n2),而堆排序在最坏情况下的时间复杂度不会发生变化,并且所需的辅助空间少于快速排序。但这两种排序方法都是不稳定的排序,若需要稳定的排序方法,则可采用归并排序。

   (4)前面讨论的排序算法,都是采用顺序存储结构。在待排序的记录非常多时,为避免花大量的时间进行记录的移动,可以采用链式存储结构。直接插入排序和归并排序都可以非常容易地在链表上实现,但快速排序和堆排序却很难在链表上实现。此时,可以提取关键码建立索引表,然后对索引表进行排序。也可以引入一个整形数组 t[n]作为辅助表,排序前令t[i]=i,1≤i≤n。若排序算法中要求交换记录 R[i]和 R[j],则只须交换 t[i]和 t[j]即可。排序结束后,数组 t[n]就存放了记录之间的顺序关系

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python数据科学

十大经典排序算法(Python代码实现)

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见...

2641
来自专栏向治洪

算法笔记之排序

最近在看《算法笔记》,如果单从算法来说,这本书真正做到了短小精悍,首先以排序入题,那么我们今天也来说说排序。 排序 将一堆杂乱无章的元素按照某种规则有序排列的过...

22710
来自专栏Jack-Cui

150.Evaluate Reverse Polish Notation(Stack-Medium)

Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid...

20010
来自专栏java一日一条

八大排序算法

(1)基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一...

711
来自专栏owent

C/C++语言常用排序算法

资料由互联网收集整理,供新手参考学习 这里又生动点的演示:http://www.cnblogs.com/wangfupeng1988/archive/2011...

1151
来自专栏恰童鞋骚年

数据结构基础温故-7.排序

排序(Sorting)是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为按关键字“有序”的记录序列。如何进行排序,特别是高效率地进行排序时计算...

1021
来自专栏我是攻城师

一个优雅的反转数组的算法

` 比较简单粗暴的方法是,遍历原始数组从最后一项向前遍历,然后把输出结果保存在一个新的数组里面,这样就完成了所谓的反转。

921
来自专栏Java技术分享圈

杨老师课堂_Java教程第四篇之数组运用

今天主要是讲解以下知识点: 1、流程控制语句switch 2、数组 3、王者荣耀英雄随机出战案例

914
来自专栏desperate633

深入理解python中的排序

进行一个简单的升序排列直接调用sorted()函数,函数将会返回一个排序后的列表:

851
来自专栏Jack的Android之旅

疯狂java笔记之常用的内部排序

在计算机程序开发过程中,经常需要一组数据元素(或记录)按某个关键字进行排序,排序完成的序列可用于快速查找相关记录。

671

扫码关注云+社区

领取腾讯云代金券