c# 插入排序,希尔排序

插入排序:

假设待排序集合是桌上的牌,每次抽一张,

手里的牌是有序的,将抽到的牌,插入手中合适的位置,

保证手中的牌一直是有序的..

具体的是两层循环:

　　外层循环每次抽一张牌

　　内层循环是将抽到的牌,从后往前与手中的牌(已排序部分)比较,如果手中的牌大,

则将已经手中的牌后移,反之,就将抽到的牌插入它的后边.进入下一轮外循环.

 1 public static void Insertion_Sort(int[] source)
 2         {
 3             int length = source.Count();
 4             for (int p = 1; p < length; p++)
 5             {
 6                 var temp = source[p];
 7                 int realIndex = 0;
 8                 for (int i = p-1; i >=0; i--)
 9                 {
10                     if (source[i] > temp)//往后移动一位
11                     {
12                         source[i + 1] = source[i];
13                         realIndex = i;
14                     }
15                     else
16                     {
17                         realIndex = i + 1;
18                         break;
19                     }                   
20                 }
21                 source[realIndex] = temp;
22             }
23         }

希尔排序

是插入排序的优化

首先需要定义一组增量序列,保证起始值为1,结束值小于数组元素个数,比如

用2^k-1这个公式去生成(Hibbard)

        public static List<int> HibbardList(int length)
        {
            List<int> range = new List<int>();
            for (int i = 1; Math.Pow(2,i)-1 < length; i++)
            {
                range.Add((int)Math.Pow(2, i) - 1);
            }
            return range;
        }

整体排序需要三层循环,最外层循环是对上述互质序列循环,执行完一轮保证间隔互质序列中的一个数字,是有序的;

就像是,抽一轮牌,保证手中的牌是间隔某个数有序的,然后再把牌放到桌上(不要洗牌!!!),再抽一次,保证一个更小的间隔有序,直至这个间隔是1;

为什么间隔数序列最好两两互质.

下两层循环逻辑和插入排序一样.

 1  public static void Shell_Sort(int[] source,List<int> range)
 2         {
 3             for (int d =range.Count-1 ; d >=0; d--)
 4             {
 5                 //间隔dd进行插入排序
 6                 int dd = range[d];
 7                 for (int p = dd; p < source.Length; p++)//注意p的增量是1,而不是dd
 8                 {
 9                     var temp = source[p];
10                     int realIndex = 0;
11                     for (int i = p - dd; i >= 0; i-=dd)
12                     {
13                         if (source[i] > temp)
14                         {
15                             source[i + dd] = source[i];
16                             realIndex = i;
17                         }
18                         else
19                         {
20                             realIndex = i + dd;
21                             break;
22                         }
23                     }
24                     source[realIndex] = temp;                   
25                 }
26             }
27         }
28  public static void ShellHibbard_Sort(int[] nums)
29         {
30             Shell_Sort(nums, HibbardList(nums.Length));
31         }

核心思想来自B站:<浙江大学数据结构>(c语言),何老师,陈老师逻辑清晰,语言简洁.我这种非计算机专业的也听起来也感觉很棒!

因为我的学习目标是用c#做建筑软件二次开发,主要是不会c语言:(,故将思想用c#实践.程序测试没问题.