排序算法1|简单插入排序与希尔排序(C#)

最近项目忙了起来,很难集中一整块时间去学习,文章更新的速度也慢了下来。零碎时间打算把算法过一遍,所以开了一个文集记录下学习过程,

谈到算法,很重要。为什么这样讲,面试基本上要问啊!!!但是实际上,对于游戏开发客户端来讲,我们遇到的数据量不会很大,常见的也就是排序或者字符匹配这样的(除非是高级AI系统,可以涉及到复杂的算法),而且现在很多算法都有相应的接口封装好了,我们只管调用使用即可,还有一点就是,懂得算法,完全开阔了我们处理问题的思路,比如使用什么数据结构处理数据更为便捷,以及如果更有效率的处理问题等。

作为开篇,我们从数组处理开始。其中,最老生常谈的就是排序。本篇主要介绍插入排序:简单插入排序以及希尔排序,这两个排序都属于插入排序,实际上简单插入排序就是希尔排序间隔为1分组的情况,两者代码也非常相似。

前文:

我们首先介绍几个概念:
空间复杂度:指程序处理算法需要的额外内存空间。

时间复杂度:指程序处理算法需要的时间。但是这个时间会根据CPU能力,环境温度,计算机配置等影响,所以不太客观。而事实上,我们会用记录算法的关键操作来表示时间复杂度。

算法的复杂度,我们通常会使用大O表示法来表示。

排序算法的稳定性:假设A,B两个数据相等,在原数据列中,A在B之前,经过排序算法,AB数据序列永远不变,即A永远在B之前,这种排序算法为稳定排序;而在排序之后,A有可能排在了B之后,这种算法为非稳定排序。为什么我们要关注稳定性?举个例子,如果你只关心数据本身,那么排序稳定就无关紧要;但是你要用数据去处理其他操作,就要考虑是否需要考虑稳定性,假设游戏里需要显示排行,为了保证每个玩家看到的排行的顺序一致,以及每次玩家打开排行榜,看到的顺序是一致的,这时候就需要排序算法要具有稳定性。

简单插入排序:

思想:将一个数插入到一个有序的数组,那么只用依次比较有序数组的数,直到找到这个数在数组中的位置即可。可以看一下动画演示(动画是用unity制作的):


InsertionSort.gif

接下来着手写代码:

        public static void InsertionSort(int[] arr)
        {
            int length = arr.Length;
            if (length<2)
            {
                return;
            }
            for (int i = 1; i < length; i++)
            {
                int j = i-1;
                int temp = arr[i];              //当前待排序的数字
                while (j>=0&&arr[j]>temp)       //依次向前比较,找到自身位置
                {                    
                    arr[j+1] = arr[j];
                    j--;
                }
                arr[j + 1] = temp;              
            }
        }

时间复杂度:我们主要看两层循环,第一层执行次数为(length-1),第二层最小为0,最大为(length-1),那么复杂度就是从(length-1)+(length-2)+...+1。用大O法,通常我们只关心数量级,而不关心系数,所以其负责度就是:O(n2
空间复杂度:很明显只申请了一个temp的变量,因此为O(1)。
稳定性:如果当前数据跟前一位数据相等,并不会交换两数位置,因此是稳定排序。

希尔排序:

思路:将数组按照一定间隔进行分组,每组组内成员进行简单插入排序。然后间隔变小,再次分组进行简单插入排序。直到间隔为1,并插入排序结束,那么排序结束。演示动画如下:


ShellSort.gif

代码如下:

        public static void ShellSort(int[] arr)
        {
            int length = arr.Length;
            if (length<2)
            {
                return;
            }
            int gap = length / 2;           //分组间隔
            while (gap>0)                   //分组间隔每次缩小2倍
            {
                for (int i = gap; i < length; i++)  
                {
                    //类似插入排序,不过数据已经分组,待排序数组,依次与组内数据比较
                    //以便找到合适位置
                    int j = i - gap;
                    int temp = arr[i];
                    while (j>=0&&arr[j]>temp)
                    {
                        arr[j + gap] = arr[j];
                        j  -= gap;
                    }
                    arr[j + gap] = temp;
                }

                gap /= 2;
            }
        }

可以看出,希尔排序的代码与简单插入排序基本类似,其实简单插入排序就是gap为1的希尔排序。
时间复杂度:希尔排序的时间复杂度分析较为复杂,我自己即便是查阅各种资料,也推不出公式。
空间复杂度:O(1)。

稳定性:由于分组的原因,会导致相同的数据分到不同的组,最终导致相同数据的顺序错乱的情况。如下图序列:
Shell1.png

在第一次分组排序后:
shell2.png

可以看到原本在红色1后面的蓝色1,排序后排在了红色1之前。因此可以看出希尔排序是不稳定排序。
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容