365体育官网概括冒泡排序,包涵直接插入排序

在付出的长河中, 平日会赶上集合排序, 那么一般景色下,
大家都是行使list.OrderBy()的不二法门来排序,
也无需关怀到内部算法的贯彻是个什么样样子.
正好这几天准备回看一下数据结构与算法. 

排序:冒泡排序vs飞快排序,冒泡排序vs

在支付的进程中, 平时会遭遇集合排序, 那么一般景观下,
大家都是选择list.OrderBy()的方式来排序,
也无需关心到内部算法的贯彻是个什么样样子.
正好这几天准备回想一下数据结构与算法. 

第一来领悟一下, 排序几乎可以分为哪二种:

  交流排序: 包含冒泡排序,快速排序。

      选取排序: 包含直接接纳排序,堆排序。

      插入排序: 包涵直接插入排序,Hill排序。

      合并排序: 合并排序。

List.OrderBy()采纳的就是神速排序格局. 冒泡排序既然和它是一致种排序形式,
那么我们将他们比较一下看看. 看看哪一类排序更好一点.

 

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

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;
}

那段代码是从参考链接里面拿的, 个人比较懒啊,
而且冒泡排序算法仍然很不难的, 就不自己写了

365体育官网 1

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

见到了神奇之处, 接下来就是长远摸底一下, 算法的考虑和完成.

 

二、思想及贯彻

  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;
}

365体育官网 2

 

率先, 每一回巡回, 我都能确定一个数的任务, 那么须求循环多少次啊?
最终一个数相应不须要再循环相比较了呢, 也没数跟她相比了.
所以循环n-1次就行了.

接着, 那么些中的每四次巡回, 其实就是一个冒泡的历程了.
把初步的数与前面一位数进行相比, 固然大于前面的数, 就向后移一位.
(其实想想, 这几个也挺麻烦的, 为什么比较五回就要活动一次啊?
我不可以找到她的岗位, 才沟通么? 起码缩小了换的操作了)

自家那里的代码与地方示例的稍有不一样, 稍微注意一下.

来看一下那边的时光复杂度, 就算外界只循环了n-1次, 里面也只循环了n-3次,
看似复杂度为(n-1)*(n-3), 不过只要n够大的话, -1或者-3甚至-100,
对最后的结果影响都是很小的. 

按照最坏的情景算的话, 那里的冒泡排序的光阴复杂度,
极限状态是O(n2), 那么他有没有得天独厚状态呢? 好像平昔不啊,
尽管那么些数组已经排好序了, 好像程序仍旧要那样初步走到尾啊,
一点都没有少什么. 所以那边的平分复杂度, 也是 O(n2). 这么看来,
冒泡排序并不是一种卓越的排序方式. 

万一无法提供更好的排序方式的话,
如故老老实实的利用List.OrderBy的格局去排序吧.

 

  1. 快快排序

高效排序算法其实也叫分治法, 其步骤大致可以分为这么几步:

  1. 先从数列中取出一个数作为条件数Num(取得好的话, 是可以减小步骤的)

  2. 分区, 将过量Num的数位居它的左侧, 小于或等于它的数位居它的左侧

  3. 再对左右区间重复前两操作, 直到各样区间唯有一个数停止.

从地点的文字可能仍然不太好掌握这么些历程,
那么自己用一张图纸来形容一下以此进度

365体育官网 3

通过一轮相比过后, 总感觉那里要递归啊. 牵涉到递归,
那么她的上空复杂度可能会比冒泡排序高一点. 

既然如此一轮的进程已经精通了, 那么就先写出一轮的代码好了

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+=1和Right-=1都是有前提条件的, 前提条件为:Left < Right

接下去就相比简单了, 一个递归调用, 这一个递归的沉思是很不难的:

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)

  最优的事态下, 复杂度为: O(nlog2n)

其复杂度的统计和验证, 额, 我是给不出来了, 可是参照里面是有的. 

最差景况下, 快速排序和冒泡排序的时间复杂度是同等的,  不过最优景况下,
冒泡排序是 n * n, 而火速排序的是 n * log2n,

如果n=16,

则冒泡是 16 * 16

立时排序是 16 * 4

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

 

参考:

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

神速排序时间复杂度为O(n×log(n))的求证

http://www.bkjia.com/C\_jc/1203534.htmlwww.bkjia.comtruehttp://www.bkjia.com/C\_jc/1203534.htmlTechArticle排序:冒泡排序vs快速排序,冒泡排序vs
在开发的历程中, 日常会遇上集合排序, 那么一般意况下,
大家都是利用list.OrderBy()的点子来排序, 也无…

率先来询问一下, 排序大致可以分为哪两种:

  互换排序: 包罗冒泡排序,快捷排序。

      选拔排序: 包含直接拔取排序,堆排序。

      插入排序: 包蕴直接插入排序,希尔(希尔(Hill))排序。

      合并排序: 合并排序。

List.OrderBy()选用的就是快捷排序方式. 冒泡排序既然和它是相同种排序方式,
那么大家将她们相比较一下看看. 看看哪一类排序更好一点.

 

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

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;
}

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

365体育官网 4

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

来看了神奇之处, 接下来就是长远摸底一下, 算法的沉思和完毕.

 

二、思想及贯彻

  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;
}

365体育官网 5

 

第一, 每四回巡回, 我都能确定一个数的职分, 那么须求循环多少次啊?
最终一个数相应不须求再循环比较了呢, 也没数跟他相比了.
所以循环n-1次就行了.

随之, 那中间的每两遍巡回, 其实就是一个冒泡的进程了.
把初步的数与背后一位数进行比较, 假如大于前边的数, 就向后移一位.
(其实想想, 这么些也挺麻烦的, 为什么相比较四次就要运动五遍啊?
我不可以找到她的岗位, 才沟通么? 起码裁减了换的操作了)

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

来看一下那边的光阴复杂度, 尽管外界只循环了n-1次, 里面也只循环了n-3次,
看似复杂度为(n-1)*(n-3), 不过若是n够大的话, -1依旧-3居然-100,
对终极的结果影响都是很小的. 

安分守己最坏的状态算的话, 那里的冒泡排序的日子复杂度,
极限状态是O(n2), 那么她有没有精美状态吧? 好像没有呀,
即使这一个数组已经排好序了, 好像程序依然要这么先河走到尾啊,
一点都尚未少什么. 所以那里的平分复杂度, 也是 O(n2). 这么看来,
冒泡排序并不是一种名特新优精的排序格局. 

只要无法提供更好的排序格局的话,
依然安安分分的利用List.OrderBy的不二法门去排序吧.

 

  1. 敏捷排序

很快排序算法其实也叫分治法, 其步骤大概可以分为这么几步:

  1. 先从数列中取出一个数作为规范数Num(取得好的话, 是可以减去步骤的)

  2. 分区, 将超出Num的数位居它的下手, 小于或等于它的数位居它的左边

  3. 再对左右间距重复前两操作, 直到各类区间唯有一个数为止.

从地点的文字可能依旧不太好明白那些历程,
那么自己用一张图片来描写一下以此进度

365体育官网 6

通过一轮相比较过后, 总感觉那里要递归啊. 牵涉到递归,
那么她的空中复杂度可能会比冒泡排序高一点. 

既然一轮的历程已经清楚了, 那么就先写出一轮的代码好了

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+=1和Right-=1都是有前提条件的, 前提条件为:Left < Right

接下去就比较简单了, 一个递归调用, 那些递归的钻探是很粗略的:

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)

  最优的图景下, 复杂度为: O(nlog2n)

其复杂度的预计和表达, 额, 我是给不出去了, 但是参照里面是有的. 

最差景况下, 神速排序和冒泡排序的年月复杂度是一模一样的,  不过最优意况下,
冒泡排序是 n * n, 而火速排序的是 n * log2n,

如果n=16,

则冒泡是 16 * 16

飞快排序是 16 * 4

可知, 只要您不是背到家, 都是比冒泡来的快的.

 

参考:

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

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

相关文章