专栏首页菩提树下的杨过数据结构与算法C#版笔记--排序(Sort)-上

数据结构与算法C#版笔记--排序(Sort)-上

这里讨论的仅限于内部排序(即全部数据都在内存中,通过CPU运算处理元素排序),而且仅限顺序表排序(即不讨论链表,树状结构等结构的排序)

注:排序后的结果可以从小到大,或者从大到小,这只是一个相反的处理而已,为方便起见,本文中的方法都是从小到大排序

1、直接插入排序(InsertOrder)

思路:从第二个元素开始向后遍历,检查本身(后面称之为tmp)与前面相邻元素的大小,如果发现前面的元素更大,则依次从近及远(即倒序遍历)检查前面的所有元素,将比自身元素大的元素依次后移,这样最终将得到一个空位,将tmp元素插在这个位置即可.

        /// <summary>
        /// 直接插入排序法
        /// </summary>
        /// <param name="lst"></param>
        static void InsertSort(int[] lst)
        {
            int _circleCount = 0;
            //外循环从第二个元素开始从前向后遍历
            for (int i = 1; i < lst.Length; i++)
            {
                _circleCount++;
                //Console.WriteLine("外循环i=" + i);
                //如果发现某元素比前一个元素小
                if (lst[i] < lst[i - 1])
                {
                    int tmp = lst[i];
                    int j = 0;
                    //则该元素前面的元素,从后到前遍历,依次后移,直接找到应该插入的空档在哪里(这样tmp元素就找到了自己的位置)
                    for (j = i - 1; j >= 0 && tmp < lst[j]; j--)
                    {
                        //如果发现有比tmp小的元素,则将元素后移一位(从而把自身空出来,形成一个空档,以方便如果前面还有更小的元素时,可以继续向后面的空档移动)
                        lst[j + 1] = lst[j];
                        _circleCount++;
                        //Console.WriteLine("内循环i=" + i + ",内循环j=" + j);
                    }
                    //Console.WriteLine("j={0}", j);
                    //运行到这里时,j已经是空档的前一个下标
                    lst[j + 1] = tmp;
                }
            }
            Console.WriteLine("InsertOrder共循环了{0}次", _circleCount);
        }

点评:最好情况下,如果所有元素(N个)已经排好序了,则外循环跑N-1次,内循环一次也进不了,即0次,时间复杂度为O(N);最坏情况下,所有元素反序,外循环N-1次,内循环为i(i从1到N-1),时间复杂度为O(N*N);所以元素越有序列,该方法效率越高,其时间复杂度从O(N)到O(N*N)之间,此外,该方法是一种稳定排序。(注:若数组中有相同值的元素时,经过某方法排序后,这二个相同值的元素先后顺序仍然不变,则称这种排序方法为稳定的,反之为不稳定排序方法)

2、冒泡排序法(BubbleSort)

思路:从最后一个元素开始向前遍历,依次检查本元素与前面相邻元素的大小,如果前面的元素更大,则交换位置,如此反复,直到把自己前移到合适的位置(即 相当于后面的元素,通过这种比较,按照从小到大将不断移动前面来,就象气泡从下面向上冒一样)

        /// <summary>
        /// 冒泡排序法
        /// </summary>
        /// <param name="lst"></param>
        static void BubbleSort(int[] lst)
        {
            int _circleCount = 0;//辅助用,可以去掉

            int tmp;
            for (int i = 0; i < lst.Length; i++)
            {
                for (int j = lst.Length - 2; j >= i; j--)
                {
                    if (lst[j + 1] < lst[j])
                    {
                        tmp = lst[j + 1];
                        lst[j + 1] = lst[j];
                        lst[j] = tmp;
                    }

                    _circleCount++;
                }
            }

            Console.WriteLine("BubbleOrder共循环了{0}次", _circleCount);
        }

点评:与插入排序法类似,最好情况是所有元素已经排好序,这样只跑外循环,内循环因为if判断不成立,直接退出;最坏情况是所有元素反序,外循环和内循环每次都要处理,因此时间复杂度跟插入排序法完全相同,同样这也是一种稳定排序。

3、简单选择排序法 (SimpleSelectOrder)

思路:先扫描整个数组,找出最小的元素,然后跟第一个元素交换(这样,第一个位置的元素就排好了),然后从第二个元素开始继续扫描,找到第二小的元素,跟第二个元素交换(这样,第二个位置的元素也排好了)...如此反复

        /// <summary>
        /// 简单选择排序法
        /// </summary>
        /// <param name="lst"></param>
        static void SimpleSelectSort(int[] lst)
        {
            int _circleCount = 0;//辅助用

            int tmp = 0;
            int t = 0;
            for (int i = 0; i < lst.Length; i++)
            {
                t = i;
                //内循环,找出最小的元素下标
                for (int j = i + 1; j < lst.Length; j++)
                {
                    if (lst[t] > lst[j])
                    {
                        t = j;
                    }
                    _circleCount++;
                }
                //将最小元素[下标为t]与元素i互换
                tmp = lst[i];
                lst[i] = lst[t];
                lst[t] = tmp;
            }
            Console.WriteLine("SimpleSelectSort共循环了{0}次", _circleCount);
        }

点评:跟冒泡法很类似,不过应该注意到,这里的元素交换操作是在内循环外,即不管如何这个交换操作是省不了的,所以其时间复杂度均为O(N*N),同样这也是一个稳定排序。

4、快速排序(QuickOrder)

思路:以数组中间的元素做为分界线(该元素称为支点),扫描其它元素,比支点小的放在左侧,比支点大的放在右侧,这样就把数组分成了二段(即做了一次粗放的大致排序),然后对每一段做同样的处理(即二段变四段,4段变8段...),直到最后每一段只有一个元素为止(没错,该方法是一个递归调用)

        /// <summary>   
        /// 快速排序   
        /// </summary>   
        /// <param name="arr">待排序数组</param>   
        /// <param name="left">数组第一个元素索引Index</param>   
        /// <param name="right">数组最后一个元素索引Index</param>   
        static void QuickSort(int[] arr, int left, int right)
        {
            //左边索引小于右边,则还未排序完成   
            if (left < right)
            {
                //取中间的元素作为比较基准,小于他的往左边移,大于他的往右边移   
                int middle = arr[(left + right) / 2];
                //因为while中要做++与--的操作,所以这里先将i,j各自换外扩张一位
                int i = left - 1;
                int j = right + 1;
                while (true)
                {
                    while (arr[++i] < middle) ;//如果前半部的元素值本身就比支点小,则直接跳过

                    while (arr[--j] > middle) ;//如果后半部的元素值本身就比支点大,则直接跳过

                    //因为前半段是向后遍历,而后半段是向前遍历,所以如果二者碰到了,
                    //则说明所有元素都被扫过了一遍,完成退出
                    if (i >= j) 
                    {
                        break;
                    }

                    //经过前面的处理后,如果发现有放错位置的元素,则将二者对换
                    int tmp = arr[i];
                    arr[j] = arr[i];
                    arr[i] = tmp;

                }

                //经过上面的while循环后,元素已被分成左右二段(左段小于支点,右段大于支点)

                //递归调用,处理左段
                QuickSort(arr, left, i - 1);

                //递归调用,处理右段
                QuickSort(arr, j + 1, right);
            }
        }

点评:每次从中间分成二段,然后再中分为二段,如此反复...这跟二叉树很相似(每次分段,相当于树中的某个节点分成二叉),最好情况下所有元素已经排好序,最终树的左右分支数大致相同(即左右分支长度大致相同),所以分解次数为树的高度log2N,而最坏情况下,所有元素反序,这时分解得到的树相当于一个单右支二叉树(即一个右分支超级长,没有左分支的怪树),即时间复杂度范围为nLog2N 至 N*N。此外,快速排序是一种不稳定的排序(从代码就能看出来,即使是二个相同值的节点,在分段过程中,也有可能被交换顺序)

本来想将堆排序与归并排序一起写在这篇文章里的,今天看了看堆排序,还有点小复杂,完全可以另起一篇详解原理了,下篇将专门学习堆排序及归并排序。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • JBOSS EAP 6.0+ Standalone模式安装成Windows服务

    网上有一些文章介绍用JavaService.exe来实现,但是到EAP 6以上版本,我试过好象没成功,幸好JBoss官方已经推出了专门的工具。 一、先到官网下载...

    菩提树下的杨过
  • 内存数据库到底有多快?

    并发量太高的应用中(比如10分钟内插入300w条记录),数据库往往难堪重负,在没有银子实现服务器集群/负载均衡/分布式存储的情况下,可以尝试一下把数据库做一个临...

    菩提树下的杨过
  • Enterprise Library 4.1学习笔记8----缓存应用程序块之FileDependency

    写入缓存数据时如果使用了FileDependency方式,最终的效果会让缓存是否过期依赖于某一个具体的文件,只要这个文件没有修改,缓存一直 有效,反之如果这个文...

    菩提树下的杨过
  • 如何在 CentOS 7 上安装和配置 Cyberpanel

    CyberPanel 是开源和使用 OpenLiteSpeed 的市场中第一个控制面板。意思就是说,和其他使用传统网站服务器的面板相比,CyberPanel 可...

    雪梦科技
  • 如何在 Ubuntu 18.04 上安装和配置 Cyberpanel

    CyberPanel 是开源和使用 OpenLiteSpeed 的市场中第一个控制面板。意思就是说,和其他使用传统网站服务器的面板相比,CyberPanel 可...

    雪梦科技
  • 成为优秀的技术人员必须做到的几件事情

      找了几天工作,收获颇多。思考得最多的问题可能就是对未来的一个规划。无意中看到下面几条经验,发现和自己想的也差不多,就分享出来。我要求自己做到这些,同时也希望...

    用户1289394
  • 黑帽SEO剖析之手法篇

    此系统文章总共分为四篇,分别是手法篇、工具篇、隐藏篇、总结篇;本篇为黑帽SEO之手法篇,主要介绍黑帽seo的概念以及一些常用的手法。   首先得说黑帽SEO是个...

    FB客服
  • 6.2 gzip压缩工具

    gzip目录概要 gzip 1.txt 压缩1.txt文件 gzip -d 1.txt 或者 uzip 1.txt.gz 解压1...

    运维小白
  • Java中的内部类了解一下

    Java类中不仅可以定义变量和方法,还可以定义类,在类内部定义的类就被称为内部类。根据定义的方式不同,可以将内部类分为四种:

    程序员-代码
  • 04-RabbitMQ常用的六种模型以及在SpringBoot中的应用

    我们并不推荐RPC式的mq调用,这么做完全没有发挥mq异步削峰的作用。如果有使用RPC的需求,请移步SpringCloud或者Dubbo。

    qubianzhong

扫码关注云+社区

领取腾讯云代金券