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

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>待排序的集合</param>
///<param>父节点</param>
///<param>输出根堆时剔除最大值使用</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;

（编辑：焦作站长网）

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