您的位置:首页 > 教程 > 开发工具 > sublime > C#实现冒泡排序和插入排序算法

C#实现冒泡排序和插入排序算法

2022-04-15 17:07:56 来源:易采站长站 作者:

C#实现冒泡排序和插入排序算法

1.选择排序(冒泡排序)

升序

用第一个元素跟其他元素比较,如果该元素比其他元素,则交换,保证该元素是最小的。然后再用第二个元素跟后面其他的比较,保证第二个元素是除第一个最小的。依次循环,直到整个数组。

/// <summary>
    /// 选择排序
    /// </summary>
    public class Selection:BaseSort
    {
        public static long usedTimes = 0;
        public Selection()
        {
        }

        public static void Sort(IComparable[] a)
        {
            Stopwatch timer = new Stopwatch();
            timer.Start();


            for (var i = 0; i < a.Length; i++)
            {
                int minIndex = i;
                for (var j = i + 1; j < a.Length; j++)
                {
                    if (Less(a[j], a[minIndex]))
                    {
                        Exch(a, j, minIndex);
                        //minIndex = j;
                    }
                }

            }

            //交换次数更少,内循环只交换索引,最后再交换值
            //for (var i = 0; i < a.Length; i++)
            //{
            //    int minIndex = i;
            //    for (var j = i + 1; j < a.Length; j++)
            //    {
            //        if (Less(a[j], a[minIndex]))
            //            minIndex = j;
            //    }
            //    Exch(a, minIndex, i);
            //}

            
            timer.Stop();
            usedTimes = timer.ElapsedMilliseconds;
        }
    }

该算法的内循环是拿当前元素跟其他元素比较,交换元素的代码写在内循环之外,每次交换都能排定一个元素,因此交换总次数是 N 。所以算法的时间效率取决于比较的次数。

由代码可知,0 到 N-1 之间的任意 i 会进行一次交换和 N-1-i 次比较,所以总共有 N 次交换和(N-1)+ (N-2)+ ...+2+1 = N(N-1)/2 ~ N^2 / 2次比较。

缺点

为了找出最小元素需要扫描一遍数组,但这并没有为下一篇扫描数组提供什么信息。排序一个有序的数组或一个主键全部相同的数组同样需要和排序随机数组一样的时间。

优点

数据移动少。交换次数和数组大小是线性的。

2.插入排序

把一个元素插入一个有序的数组,右边元素需要右移一位。

与选择排序一样,当前索引左边的所有元素都是有序的,但它们的最终位置还不确定,为了给更小的元素腾出空间,它们可能会被移动。当索引达到最右端时,数组排序就完成了。初始时,可以认为第一个元素就是一个有序的数组。

和选择排序不同的是,插入排序所需的时间取决于元素的初始顺序。一个对部分有序的数组会比对随机数组排序要快的多。

public class Insertion : BaseSort
    {
        public static long usedTimes = 0;
        public static void Sort(IComparable[] a)
        {
            Stopwatch timer = new Stopwatch();
            timer.Start();

            /*
             * 将当前位置的值与前一个比较,如果小就互换,
             * 然后用前一个位置的值继续,
             * 直到遇到比它大的值,停止内循环、
             * 相当于拿当前值跟左边有序数组依次比较,如果当前值小就交换,如果遇到比当前值大的元素就跳出内循环,说明已经找到合适的位置了。
             */
            for (var i = 0; i < a.Length; i++)
            {
                for (var j = i; j > 0 && Less(a[j], a[j - 1]); j--)
                {
                    Exch(a, j, j - 1);
                }
            }



            /*
             * temp 存储当前值
             * 然后拿 temp 跟左边的值挨个比较
             * 如果temp小就将比较的值向右移一位,直到遇到比temp大的数或者到头了
             * 就将temp放到当前位置+1的地方
             */
            //int N = a.Length;
            //for (int i = 1; i < N; i++)
            //{
            //    IComparable temp = a[i];
            //    int j;
            //    for (j = i - 1; j >= 0 && Less(temp, a[j]); j--)
            //    {
            //        a[j + 1] = a[j];
            //    }
            //    a[j + 1] = temp;
            //}

            timer.Stop();
            usedTimes = timer.ElapsedMilliseconds;
        }

    }

对于最坏情况下(逆序),插入排序需要 ~ N^2 / 2 次比较和 ~ N^2 / 2 次交换。因为每次循环都需要 i 次比较和交换 (1+2.....+N-1)* N 。

对于最好情况下(全部有序),插入排序需要 N-1 次比较和 0 次交换。因为有序,所以不需要交换,只需要每次循环比较。

对于随机排列的数组,平均情况下插入排序需要 ~ N^2 / 4 次比较和 ~ N^2 / 4 次交换。随机数组在平均情况下每个元素都有可能移动半个数组的长度。

插入排序比较的次数是交换的次数加上一个额外项,该项为 N 减去被插入的元素正好是已知的最小元素的次数。最好情况下(全部有序),每一个元素都是已知的最小元素,所以这一项为 N-1。

插入排序对于非随机数组(部分有序)很有效。例如,有序数组或主键全部相同的数组,它的运行时间是线性的。

现在考虑一般的情况是部分有序的数组。倒置指的是数组中两个顺序颠倒的元素。比如 E X A M P L E 中有 11 对倒置:E-A, X-A, X-M, X-P, X-L, X-E, M-L, M-E, P-L, P-E, L-E 。如果数组中倒置的数量小于数组大小的某个倍数,这个数组就是部分有序的。

下面是典型的部分有序的数组:

数组中每个元素距离它的最终位置都不远;

一个有序的大数组接一个小数组;

数组中只有几个元素的位置不确定;

当倒置的数量很少时,插入排序可能比任何排序算法都快。

插入排序需要的交换次数和数组中倒置的数量相同,每次交换相当于减少一对倒置。需要比较的次数大于等于倒置的数量,小于等于倒置的数量加上数组的大小减一。因为 1 到 N-1 之间的每个 i 都需要一次比较,然后每次交换对应着一次比较,这两种比较之间可能存在交叉,所以是小于等于。

上面的插入排序算法代码,只要遇到比当前元素大的就交换。可以优化这一块,上面注释的代码,可以减少数组访问次数。

插入排序运行时间大概是选择排序的一半。

到此这篇关于C#实现冒泡排序和插入排序算法的文章就介绍到这了。希望对大家的学习有所帮助,也希望大家多多支持易采站长站。

如有侵权,请联系QQ:279390809 电话:15144810328

相关文章

  • sublime php语法错误提示怎么发现

    sublime php语法错误提示怎么发现

    sublime php语法错误提示的发现方法:首先打开sublime软件;然后在sublime中写入php代码;接着按下快捷键“ctrl+B”,即可在执行过程中显示错误提示。昨晚因为php的某个变量代码写错了,sublime又没有提示语法错误。弄了许久,一段段的调试,最后才知道是取到的变量是空的sublime可以提示php语法错误在sublime写完了php代码后,如果写错了不像eclipse即时
    2020-08-15
  • Sublime Text3简体中文汉化包怎么用

    Sublime Text3简体中文汉化包怎么用

    下面由sublime教程栏目给大家介绍Sublime Text3简体中文汉化包的使用方法,希望对需要的朋友有所帮助!汉化包下载地址:https://github.com/Trojain/sublime-package1、由上面的链接得到的 Default.sublime-package 文件。打开sublime text 3 编辑器,打开菜单 => preferences => Browse Pa
    2020-08-20
  • 关于 Sublime Text 中的 Git

    关于 Sublime Text 中的 Git

    下面由sublime教程栏目给大家介绍Sublime Text 中的 Git,希望对需要的朋友有所帮助!Sublime Text 中的 Git从 3.2 版本开始,Sublime Text 在编辑器内集成了 Git。功能如下:侧边栏将会使用图标来指明文件及文件夹的 Git 状态。被你的 .gitignore 文件所指定忽略的文件以及文件夹会在侧边栏褪色显示。在状态栏,你能够查看当前所在分支以及你做
    2020-08-21
  • Sublime Text3+Markdown配置步骤【图文详解】

    Sublime Text3+Markdown配置步骤【图文详解】

    下面由sublime教程栏目给大家介绍Sublime Text3+Markdown配置步骤【图文详解】,希望对需要的朋友有所帮助!Sublime是一款非常优秀的文本编辑器,可以安装大量的插件,使用Sublime + Markdown更是有一番别样体验,在此只写如何正确配置(以Sublime Text 3为例),使用技巧请参阅相关文章。1.安装Package:Markdown Preview和Ma
    2020-08-22
  • 三步搞定sublime text 3配置

    三步搞定sublime text 3配置

    下面由sublime教程栏目给大家介绍sublime text 3的下载和配置,希望对需要的朋友有所帮助!下载sublime text 3在百度中搜索sublime text 3,进入sublime text官网,官网链接是http://www.sublimetext.com/。下载界面如图所示:点击Download for Windows按钮,下载sublime text 3,需要注意的是这里下
    2020-08-24
  • 分享Sublime Text 3 、WebStorm配置护眼主题(浅绿色)

    分享Sublime Text 3 、WebStorm配置护眼主题(浅绿色)

    下面由sublime教程栏目给大家分享Sublime Text 3 、WebStorm配置护眼主题(浅绿色),希望对需要的朋友有所帮助!本文所用软件版本Sublime Text 3(Build 3143)、WebStorm 2017.2.4(Build #WS-172.4155.35),其他版本软件配置过程可能不一样,请知悉!1.Sublime Text 3护眼主题 (1)下载配置文件 链
    2020-08-26
  • Sublime Merge 是什么

    Sublime Merge 是什么

    下面由sublime教程栏目给大家介绍Sublime Merge,希望对需要的朋友有所帮助!Sublime Merge 是由知名文本编辑器 Sublime Text 开发商打造的 Git 客户端,仅适用于 64 位平台。按开发商的说法,Sublime Merge 融合了 Sublime Text 的 UI 引擎和从零开始的 Git* 实现。所以这一工具继承了 Sublime Text 优雅美观的
    2020-08-27
  • Sublime Text 快捷键列表分享

    Sublime Text 快捷键列表分享

    下面由sublime教程栏目给大家介绍Sublime Text 快捷键,希望对需要的朋友有所帮助!Sublime Text 快捷键列表 快捷键按类型分列如下:1、通用 ↑↓← → 上下左右移动光标 Alt 调出菜单 Ctrl + Shift + P 调出命令板(Command Palette) Ctrl + ` 调出控制台2
    2020-08-29