算法系列15天速成 第二天 七大经典排序【中】_相关技巧

首先感谢朋友们对第一篇文章的鼎力支持,感动中....... 

 

今天说的是选择排序,包括“直接选择排序”和“堆排序”。

话说上次“冒泡排序”被快排虐了,而且“快排”赢得了内库的重用,众兄弟自然眼红,非要找快排一比高下。

这不今天就来了两兄弟找快排算账。

1.直接选择排序: 

先上图:

说实话,直接选择排序最类似于人的本能思想,比如把大小不一的玩具让三岁小毛孩对大小排个序,

那小孩首先会在这么多玩具中找到最小的放在第一位,然后找到次小的放在第二位,以此类推。。。。。。

,小孩子多聪明啊,这么小就知道了直接选择排序。羡慕中........

对的,小孩子给我们上了一课,

第一步: 我们拿80作为参照物(base),在80后面找到一个最小数20,然后将80跟20交换。

第二步:  第一位数已经是最小数字了,然后我们推进一步在30后面找一位最小数,发现自己最小,不用交换。

第三步:........

最后我们排序完毕。大功告成。

既然是来挑战的,那就5局3胜制。

复制代码 代码如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Diagnostics;

namespace SelectionSort
{
    public class Program
    {
        static void Main(string[] args)
        {
            //5次比较
            for (int i = 1; i <= 5; i++)
            {
                List<int> list = new List<int>();

                //插入2w个随机数到数组中
                for (int j = 0; j < 20000; j++)
                {
                    Thread.Sleep(1);
                    list.Add(new Random((int)DateTime.Now.Ticks).Next(1000, 1000000));
                }

                Console.WriteLine("\n第" + i + "次比较:");

                Stopwatch watch = new Stopwatch();

                watch.Start();
                var result = list.OrderBy(single => single).ToList();
                watch.Stop();

                Console.WriteLine("\n快速排序耗费时间:" + watch.ElapsedMilliseconds);
                Console.WriteLine("输出前十个数:" + string.Join(",", result.Take(10).ToList()));

                watch.Start();
                result = SelectionSort(list);
                watch.Stop();

                Console.WriteLine("\n直接选择排序耗费时间:" + watch.ElapsedMilliseconds);
                Console.WriteLine("输出前十个数:" + string.Join(",", list.Take(10).ToList()));

            }
        }

        //选择排序
        static List<int> SelectionSort(List<int> list)
        {
            //要遍历的次数
            for (int i = 0; i < list.Count - 1; i++)
            {
                //假设tempIndex的下标的值最小
                int tempIndex = i;

                for (int j = i + 1; j < list.Count; j++)
                {
                    //如果tempIndex下标的值大于j下标的值,则记录较小值下标j
                    if (list[tempIndex] > list[j])
                        tempIndex = j;
                }

                //最后将假想最小值跟真的最小值进行交换
                var tempData = list[tempIndex];
                list[tempIndex] = list[i];
                list[i] = tempData;
            }
            return list;
        }
    }
}

比赛结果公布:

堆排序:

要知道堆排序,首先要了解一下二叉树的模型。

下图就是一颗二叉树,具体的情况我后续会分享的。

那么堆排序中有两种情况(看上图理解):

    大根堆:  就是说父节点要比左右孩子都要大。

    小根堆:  就是说父节点要比左右孩子都要小。

 

那么要实现堆排序,必须要做两件事情:

   第一:构建大根堆。

           首先上图:

           

首先这是一个无序的堆,那么我们怎样才能构建大根堆呢?

     第一步: 首先我们发现,这个堆中有2个父节点(2,,3);

     第二步: 比较2这个父节点的两个孩子(4,5),发现5大。

     第三步: 然后将较大的右孩子(5)跟父节点(2)进行交换,至此3的左孩子堆构建完毕,

                 如图:

                         

     第四步: 比较第二个父节点(3)下面的左右孩子(5,1),发现左孩子5大。

     第五步: 然后父节点(3)与左孩子(5)进行交换,注意,交换后,堆可能会遭到破坏,

                 必须按照以上的步骤一,步骤二,步骤三进行重新构造堆。

           

最后构造的堆如下:

                 

 

   第二:输出大根堆。

             至此,我们把大根堆构造出来了,那怎么输出呢?我们做大根堆的目的就是要找出最大值,

         那么我们将堆顶(5)与堆尾(2)进行交换,然后将(5)剔除根堆,由于堆顶现在是(2),

         所以破坏了根堆,必须重新构造,构造完之后又会出现最大值,再次交换和剔除,最后也就是俺们

         要的效果了,

 

 

发现自己兄弟被别人狂殴,,堆排序再也坐不住了,决定要和快排干一场。

同样,快排也不甘示弱,谁怕谁?

复制代码 代码如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Diagnostics;

namespace HeapSort
{
    public class Program
    {
        static void Main(string[] args)
        {
            //5次比较
            for (int j = 1; j <= 5; j++)
            {
                List<int> list = new List<int>();

                //插入2w个数字
                for (int i = 0; i < 20000; i++)
                {
                    Thread.Sleep(1);
                    list.Add(new Random((int)DateTime.Now.Ticks).Next(1000, 100000));
                }

                Console.WriteLine("\n第" + j + "次比较:");

                Stopwatch watch = new Stopwatch();
                watch.Start();
                var result = list.OrderBy(single => single).ToList();
                watch.Stop();
                Console.WriteLine("\n快速排序耗费时间:" + watch.ElapsedMilliseconds);
                Console.WriteLine("输出前十个数" + string.Join(",", result.Take(10).ToList()));

                watch = new Stopwatch();
                watch.Start();
                HeapSort(list);
                watch.Stop();
                Console.WriteLine("\n堆排序耗费时间:" + watch.ElapsedMilliseconds);
                Console.WriteLine("输出前十个数" + string.Join(",", list.Take(10).ToList()));
            }

        }

        ///<summary>
/// 构建堆
///</summary>
///<param name="list">待排序的集合</param>
///<param name="parent">父节点</param>
///<param name="length">输出根堆时剔除最大值使用</param>
        static void HeapAdjust(List<int> list, int parent, int length)
        {
            //temp保存当前父节点
            int temp = list[parent];

            //得到左孩子(这可是二叉树的定义,大家看图也可知道)
            int child = 2 * parent + 1;

            while (child < length)
            {
                //如果parent有右孩子,则要判断左孩子是否小于右孩子
                if (child + 1 < length && list[child] < list[child + 1])
                    child++;

                //父亲节点大于子节点,就不用做交换
                if (temp >= list[child])
                    break;

                //将较大子节点的值赋给父亲节点
                list[parent] = list[child];

                //然后将子节点做为父亲节点,已防止是否破坏根堆时重新构造
                parent = child;

                //找到该父亲节点较小的左孩子节点
                child = 2 * parent + 1;
            }
            //最后将temp值赋给较大的子节点,以形成两值交换
            list[parent] = temp;
        }

        ///<summary>
/// 堆排序
///</summary>
///<param name="list"></param>
        public static void HeapSort(List<int> list)
        {
            //list.Count/2-1:就是堆中父节点的个数
            for (int i = list.Count / 2 - 1; i >= 0; i--)
            {
                HeapAdjust(list, i, list.Count);
            }

            //最后输出堆元素
            for (int i = list.Count - 1; i > 0; i--)
            {
                //堆顶与当前堆的第i个元素进行值对调
                int temp = list[0];
                list[0] = list[i];
                list[i] = temp;

                //因为两值交换,可能破坏根堆,所以必须重新构造
                HeapAdjust(list, 0, i);
            }
        }
    }
}

结果公布:

堆排序此时心里很尴尬,双双被KO,心里想,一定要捞回面子,一定要赢,

于是堆排序提出了求“前K大问题”。(就是在海量数据中找出前几大的数据),

快排一口答应,小意思,没问题。

双方商定,在2w随机数中找出前10大的数:

复制代码 代码如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Diagnostics;

namespace QuickSort
{
    public class Program
    {
        static void Main(string[] args)
        {
            //5此比较
            for (int j = 1; j <= 5; j++)
            {
                List<int> list = new List<int>();

                for (int i = 0; i < 20000; i++)
                {
                    Thread.Sleep(1);
                    list.Add(new Random((int)DateTime.Now.Ticks).Next(1000, 100000));
                }

                Console.WriteLine("\n第" + j + "次比较:");

                Stopwatch watch = new Stopwatch();
                watch.Start();
                var result = list.OrderByDescending(single => single).Take(10).ToList();
                watch.Stop();
                Console.WriteLine("\n快速排序求前K大耗费时间:" + watch.ElapsedMilliseconds);
                Console.WriteLine("输出前十个数:" + string.Join(",", result.Take(10).ToList()));

                watch = new Stopwatch();
                watch.Start();
                result = HeapSort(list, 10);
                watch.Stop();
                Console.WriteLine("\n堆排序求前K大耗费时间:" + watch.ElapsedMilliseconds);
                Console.WriteLine("输出前十个数:" + string.Join(",", list.Take(10).ToList()));
            }

        }

        ///<summary>
/// 构建堆
///</summary>
///<param name="list">待排序的集合</param>
///<param name="parent">父节点</param>
///<param name="length">输出根堆时剔除最大值使用</param>
        static void HeapAdjust(List<int> list, int parent, int length)
        {
            //temp保存当前父节点
            int temp = list[parent];

            //得到左孩子(这可是二叉树的定义哇)
            int child = 2 * parent + 1;

            while (child < length)
            {
                //如果parent有右孩子,则要判断左孩子是否小于右孩子
                if (child + 1 < length && list[child] < list[child + 1])
                    child++;

                //父节点大于子节点,不用做交换
                if (temp >= list[child])
                    break;

                //将较大子节点的值赋给父亲节点
                list[parent] = list[child];

                //然后将子节点做为父亲节点,已防止是否破坏根堆时重新构造
                parent = child;

                //找到该父节点左孩子节点
                child = 2 * parent + 1;
            }
            //最后将temp值赋给较大的子节点,以形成两值交换
            list[parent] = temp;
        }

        ///<summary>
/// 堆排序
///</summary>
///<param name="list">待排序的集合</param>
///<param name="top">前K大</param>
///<returns></returns>
        public static List<int> HeapSort(List<int> list, int top)
        {
            List<int> topNode = new List<int>();

            //list.Count/2-1:就是堆中非叶子节点的个数
            for (int i = list.Count / 2 - 1; i >= 0; i--)
            {
                HeapAdjust(list, i, list.Count);
            }

            //最后输出堆元素(求前K大)
            for (int i = list.Count - 1; i >= list.Count - top; i--)
            {
                //堆顶与当前堆的第i个元素进行值对调
                int temp = list[0];
                list[0] = list[i];
                list[i] = temp;

                //最大值加入集合
                topNode.Add(temp);

                //因为顺序被打乱,必须重新构造堆
                HeapAdjust(list, 0, i);
            }
            return topNode;
        }
    }
}

求前K大的输出结果:

最后堆排序赶紧拉着直接选择排序一路小跑了,因为求前K大问题已经不是他原本来的目的。

ps: 直接选择排序的时间复杂度为:O(n^2)

       堆排序的时间复杂度:O(NlogN)

时间: 2024-12-05 15:40:38

算法系列15天速成 第二天 七大经典排序【中】_相关技巧的相关文章

算法系列15天速成——第二天 七大经典排序【中】

首先感谢朋友们对第一篇文章的鼎力支持,感动中.......    今天说的是选择排序,包括"直接选择排序"和"堆排序".   话说上次"冒泡排序"被快排虐了,而且"快排"赢得了内库的重用,众兄弟自然眼红,非要找快排一比高下. 这不今天就来了两兄弟找快排算账.   1.直接选择排序:  先上图:   说实话,直接选择排序最类似于人的本能思想,比如把大小不一的玩具让三岁小毛孩对大小排个序, 那小孩首先会在这么多玩具中找到最小的放在

算法系列15天速成——第一天 七大经典排序【上】

今天是开篇,得要吹一下算法,算法就好比程序开发中的利剑,所到之处,刀起头落.   针对现实中的排序问题,算法有七把利剑可以助你马道成功.   首先排序分为四种:        交换排序: 包括冒泡排序,快速排序.       选择排序: 包括直接选择排序,堆排序.       插入排序: 包括直接插入排序,希尔排序.       合并排序: 合并排序.   那么今天我们讲的就是交换排序,我们都知道,C#类库提供的排序是快排,为了让今天玩的有意思点, 我们设计算法来跟类库提供的快排较量较量.争取K

算法系列15天速成 第一天 七大经典排序【上】_相关技巧

针对现实中的排序问题,算法有七把利剑可以助你马道成功. 首先排序分为四种:       交换排序: 包括冒泡排序,快速排序.      选择排序: 包括直接选择排序,堆排序.      插入排序: 包括直接插入排序,希尔排序.      合并排序: 合并排序. 那么今天我们讲的就是交换排序,我们都知道,C#类库提供的排序是快排,为了让今天玩的有意思点,我们设计算法来跟类库提供的快排较量较量.争取KO对手. 冒泡排序: 首先我们自己来设计一下"冒泡排序",这种排序很现实的例子就是:我抓一

算法系列15天速成——第十二天 树操作【中】

      先前说了树的基本操作,我们采用的是二叉链表来保存树形结构,当然二叉有二叉的困扰之处,比如我想找到当前结点 的"前驱"和"后继",那么我们就必须要遍历一下树,然后才能定位到该"节点"的"前驱"和"后继",每次定位都是O(n),这 不是我们想看到的,那么有什么办法来解决呢?    (1) 在节点域中增加二个指针域,分别保存"前驱"和"后继",那么就是四叉链表了

算法系列15天速成 第十二天 树操作【中】_相关技巧

先前说了树的基本操作,我们采用的是二叉链表来保存树形结构,当然二叉有二叉的困扰之处,比如我想找到当前结点的"前驱"和"后继",那么我们就必须要遍历一下树,然后才能定位到该"节点"的"前驱"和"后继",每次定位都是O(n),这不是我们想看到的,那么有什么办法来解决呢?    (1) 在节点域中增加二个指针域,分别保存"前驱"和"后继",那么就是四叉链表了,哈哈,还是有点

算法系列15天速成——第七天 线性表【上】

原文:算法系列15天速成--第七天 线性表[上]   人活在社会上不可能孤立,比如跟美女有着千丝万缕的关系,有的是一对一,有的是一对多,有的是多对多. 哈哈,我们的数据也一样,存在这三种基本关系,用术语来说就是: <1>  线性关系. <2>  树形关系. <3>  网状关系.   一: 线性表       1 概念:                  线性表也就是关系户中最简单的一种关系,一对一.                   如:学生学号的集合就是一个线性表.

算法系列15天速成——第三天 七大经典排序【下】

今天跟大家聊聊最后三种排序: 直接插入排序,希尔排序和归并排序.   直接插入排序:        这种排序其实蛮好理解的,很现实的例子就是俺们斗地主,当我们抓到一手乱牌时,我们就要按照大小梳理扑克,30秒后,    扑克梳理完毕,4条3,5条s,哇塞......  回忆一下,俺们当时是怎么梳理的.        最左一张牌是3,第二张牌是5,第三张牌又是3,赶紧插到第一张牌后面去,第四张牌又是3,大喜,赶紧插到第二张后面去,    第五张牌又是3,狂喜,哈哈,一门炮就这样产生了.      

算法系列15天速成 第三天 七大经典排序【下】_相关技巧

直接插入排序:        这种排序其实蛮好理解的,很现实的例子就是俺们斗地主,当我们抓到一手乱牌时,我们就要按照大小梳理扑克,30秒后,    扑克梳理完毕,4条3,5条s,哇塞......  回忆一下,俺们当时是怎么梳理的.        最左一张牌是3,第二张牌是5,第三张牌又是3,赶紧插到第一张牌后面去,第四张牌又是3,大喜,赶紧插到第二张后面去,    第五张牌又是3,狂喜,哈哈,一门炮就这样产生了.      怎么样,生活中处处都是算法,早已经融入我们的生活和血液.       

算法系列15天速成——第六天 五大经典查找【下】

大家是否感觉到,树在数据结构中大行其道,什么领域都要沾一沾,碰一碰. 就拿我们前几天学过的排序就用到了堆和今天讲的"二叉排序树",所以偏激的说,掌握的树你就是牛人了.   今天就聊聊这个"五大经典查找"中的最后一个"二叉排序树".   1. 概念:      <1> 其实很简单,若根节点有左子树,则左子树的所有节点都比根节点小.                              若根节点有右子树,则右子树的所有节点都比根节点大