换来排序

在支付的进程中, 平日会境遇集合排序, 那么一般景观下,
大家都以行使list.OrderBy()的方法来排序,
也无需关切到当中算法的落到实处是个什么样样子.
正好这几天准备回看一下数据结构与算法. 

先是来通晓一下, 排序差不离能够分为哪三种:

  交流排序: 包罗冒泡排序,飞速排序。

      选拔排序: 包蕴间接选拔排序,堆排序。

      插入排序: 包蕴间接插入排序,希尔排序。

      合并排序: 合并排序。

List.OrderBy()选用的正是高效排序情势. 冒泡排序既然和它是壹样种排序情势,
那么大家将她们比较一下看看. 看看哪一种排序更加好一点.

 

1、示例(先看结果, 再讲思想)

static void Test()
{
    //五次比较
    for (int i = 1; i <= 5; i++)
    {
        List<int> list = new List<int>();
        //插入2k个随机数到数组中
        for (int j = 0; j < 2000; j++)
        {
            Thread.Sleep(3);
            list.Add(new Random((int)DateTime.Now.Ticks).Next(0, 100000));
        }

        Console.WriteLine("\n第" + i + "次比较:{0}...", string.Join(",", list.Take(10)));

        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 = BubbleSort(list);
        watch.Stop();
        Console.WriteLine("\n冒泡排序耗费时间:" + watch.ElapsedMilliseconds);
        Console.WriteLine("输出前是十个数:" + string.Join(",", result.Take(10).ToList()));
    }
}

//冒泡排序算法
static List<int> BubbleSort(List<int> list)
{
    int temp;
    int count = list.Count;
    //第一层循环: 表明要比较的次数,比如list.count个数,肯定要比较count-1次
    for (int i = 0; i < count - 1; i++)
    {
        //list.count-1:取数据最后一个数下标,
        //j>i: 从后往前的的下标一定大于从前往后的下标,否则就超越了。
        for (int j = count - 1; j > i; j--)
        {
            //如果前面一个数大于后面一个数则交换
            if (list[j - 1] > list[j])
            {
                temp = list[j - 1];
                list[j - 1] = list[j];
                list[j] = temp;
            }
        }
    }
    return list;
}

那段代码是从参考链接里面拿的, 个人相比懒啊,
而且冒泡排序算法照旧很不难的, 就不协调写了

www.27111.com 1

从地点的结果来看, 急忙排序比冒泡排序快的不是一星半点啊. 

见状了神奇之处, 接下来正是深刻摸底一下, 算法的思量和达成.

 

2、思想及落实

  1. 冒泡排序

先是来解释一下冒泡吧, 在水里面, 呼出一口气, 形成三个泡泡,
那个泡泡会在回升的进程中, 逐步变大(水压更小导致的).
最终表露说面破掉了.

沟通着这种思考, 可以想到, 冒泡排序, 应该正是让大的数, 渐渐往上涨,
一向接升学到比它大的数前边, 破掉了.

依据那种思量, 就大致有二个进度在脑海中形成了, 来看一下代码:
(上边包车型地铁还蛮形象的,
就偷过来了)

//冒泡排序算法
static List<int> BubbleSort1(List<int> list)
{
    int temp;
    int count = list.Count;
    for (int i = 0; i < count - 1; i++)
    {
        for (int j = 1; j < count; j++)
        {
            //如果前面一个数大于后面一个数则交换
            if (list[j - 1] > list[j])
            {
                temp = list[j - 1];
                list[j - 1] = list[j];
                list[j] = temp;
            }
        }
    }
    return list;
}

www.27111.com 2

 

首先, 每贰回巡回, 小编都能明确三个数的岗位, 那么须求循环多少次啊?
最终2个数相应不须要再循环相比较了吗, 也没数跟她比较了.
所以循环n-一遍就行了.

继而, 这一个中的每三次巡回, 其实正是3个冒泡的进度了.
把初叶的数与前面一人数举行相比较, 如若大于前面包车型地铁数, 就向后移一位.
(其实想想, 这些也挺麻烦的, 为什么相比较贰回就要活动3遍啊?
作者无法找到她的职位, 才调换么? 起码裁减了换的操作了)

本身那边的代码与地点示例的稍有两样, 稍微注意一下.

来看一下那边的日子复杂度, 即便外界只循环了n-3遍, 里面也只循环了n-二遍,
看似复杂度为(n-一)*(n-三), 不过一旦n够大的话, -一照旧-三竟然-100,
对最后的结果影响都以非常小的. 

鲁人持竿最坏的场所算的话, 这里的冒泡排序的日子复杂度,
极限状态是O(n2), 那么她有未有得天独厚图景吧? 好像从没啊,
即便那些数组已经排好序了, 好像程序照旧要这么开头走到尾啊,
一点都尚未少什么. 所以那里的平均复杂度, 也是 O(n2). 这么看来,
冒泡排序并不是一种美好的排序方式. 

要是无法提供越来越好的排序格局的话,
仍旧安安分分的施用List.OrderBy的不2秘诀去排序吧.

 

  1. 神速排序

高速排序算法其实也叫分治法, 其步骤大约能够分成这么几步:

  一. 先从数列中取出二个数作为基准数Num(取得好的话, 是能够减去步骤的)

  二. 分区, 将过量Num的数位居它的动手, 小于或等于它的数位居它的左手

  三. 再对左右间距重复前两操作, 直到各样区间只有1个数截止.

从上面包车型地铁文字恐怕仍然不太好精晓那些进程,
那么小编用一张图片来描写一下那几个历程

www.27111.com 3

通过一轮相比较过后, 总感到那里要递归啊. 牵涉到递归,
那么他的空中复杂度大概会比冒泡排序高级中学一年级点. 

既是1轮的长河已经知道了, 那么就先写出1轮的代码好了

static int Division(List<int> list, int left, int right)
{
    int baseNum = list[left];

    while (left < right)
    {
        while (left < right && list[right] > baseNum)
        {
            right -= 1;
        }

        list[left] = list[right];
     while (left < right && list[left] <= baseNum)
        {
            left += 1;
        }

        list[right] = list[left];
    }
    list[left] = baseNum;
    return left;
}

此间的Left+=一和Right-=壹都以有前提条件的, 前提条件为:Left < Right

接下去就相比较简单了, 1个递归调用, 这几个递归的研究是很简短的:

static void QuickSort(List<int> list, int left, int right)
{
    if (left < right)
    {
        int i = Division(list, left, right);

        QuickSort(list, left, i - 1);

        QuickSort(list, i + 1, right);
    }
}

 飞速排序的复杂度:

  最不佳的处境下, 复杂度为: O(n2)

www.27111.com,  最优的景况下, 复杂度为: O(nlog2n)

其复杂度的总计和注明, 额, 笔者是给不出来了, 不过参考里面是有的. 

最差景况下, 急迅排序和冒泡排序的岁月复杂度是同样的,  可是最优情形下,
冒泡排序是 n * n, 而快速排序的是 n * log2n,

如果n=16,

则冒泡是 1六 * 16

火速排序是 1六 * 4

足见, 只要您不是背到家, 都以比冒泡来的快的.

 

参考:

算法体系1四日速成——第3天
七大经典排序【上】

高效排序时间复杂度为O(n×log(n))的表明

发表评论

电子邮件地址不会被公开。 必填项已用*标注