集团旗下网站: 迈领人才网 | 奇酷方舟 | 红砖升本
全国咨询热线:400-807-8991
您现在所在的位置:首页 >学习资源 > Unity游戏/VR/AR入门教材 > VR开发入门教程43:简单算法之希尔排序

VR开发入门教程43:简单算法之希尔排序

来源:奇酷教育 发表于:

VR开发 VR视频 VR培训

  希尔排序

  希尔排序Shell Sort是基于插入排序的一种改进,同样分成两部分,也称缩小增量排序

  步骤分析:

  1、准备待排数组[6 2 4 1 5 9]

  2、首先需要选取关键字,例如关键是3和1(第一步分成三组,第二步分成一组),那么待排数组分成了以下三个虚拟组:[6 1]一组、[2 5]二组、[4 9]三组。注意不是临近的两个数字分组,而是下标为3(分成了三组)的倍数的数字的分成了一组,就是每隔3个数取一个,每隔三个再取一个,这样取出来的数字放到一组,

  3、把它们当成一组,但不实际分组,只是当成一组来看,所以上边的"组"实际上并不存在,只是为了说明分组关系

  4、对以上三组分别进行插入排序变成下边这样

  [1 6] [2 5] [4 9]

  具体过程:

  [6 1]6和1交换变成[1 6]

  [2 5]2与5不动还是[2 5]

  [4 9]4与9不动还是[4 9]

  第一趟排序状态演示:

  待排数组:[6 2 4 1 5 9]

  排后数组:[1 2 4 6 5 9]

  第二趟关键字取的是1,即每隔一个取一个组成新数组,实际上就是只有一组啦,隔一取一就全部取出来了

  此时待排数组为:[1 2 4 6 5 9]

  直接对它进行插入排序

  还记得插入排序怎么排不?复习一下

  [1 2 4]都不用动,过程省略,到5的时候,将5取出,在前边的有序数组里找到适合它的位置插入,就是4后边,6前边

  后边的也不用改,所以排序完毕

  顺序输出结果:[1 2 4 5 6 9]

  如何选取关键字

  希尔排序的关键是如何取关键字,因为其它内容与插入排序一样

  那么如何选取关键字呢?就是分成三组,一组,这个分组的依据是什么呢?为什么不是二组,六组或者其它组?

  好的增量序列的共同特征:

  ① 最后一个增量必须为1

  ② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况

  就是说,这个关键的选择是没有规定的,怎么选都可以,仅一条,关键字要越来越小,直到1为止

  增量的取值规则:为第一次取总长度的一半,第二次取一半的一半,依次类推直到1为止

  总的说来希尔对插入排序进行了改造

  原理:为了在插入排序前达到整个序列基本有序的状态 提高插入排序的效率

  static void ShellSort(int[] unsorted, int len)

  {

  int group, i, j, temp;

  for (group = len / 2; group > 0; group /= 2)

  {

  for (i = group; i < len; i++)

  {

  for (j = i - group; j >= 0; j -= group)

  {

  if (unsorted[j] > unsorted[j + group])

  {

  temp = unsorted[j];

  unsorted[j] = unsorted[j + group];

  unsorted[j + group] = temp;

  }

  }

  }

  }

  }