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

//最后将假想最小值跟真的最小值进行交换
                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()));

（编辑：焦作站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!