排序算法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（n²）
空间复杂度：很明显只申请了一个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之前。因此可以看出希尔排序是不稳定排序。