各种排序算法的实现折半插入排序

广州疯狂软件学院拥有三大课程体系包括:java课程,android课程,ios课程,疯狂软件年终钜惠,报名java就业班,免费赠送基础班,名额有限,本月火热报名中,欢迎有志之士电话或者QQ咨询。

  这种算法 比起 直接插入算法的好处是 减少了比较次数,因为你当前插入的前面的列表中肯定是有序的,那么可以通过折半查找来 得来 你应该插入的位置,再把元素集体完后面挪动。

  比如 当前列表是 1, 3 , 9 ,7, 123.当你遍历到7的时候 前面的1,3, 9 实际上已经有序,那么根据折半查找算法可以很容易找到我们应该插入的位置是 9的前面,那么只需要把9 往后面挪动一位,再把7 放到9的位置即可。

  这是我自己写的测试例子。 工作了这么多年了, 现在在家没事温习一下以前的排序,大家可以给出更优的解决办法,或者参与群 C语言/C++/STL/linux/MFC/WTL 77278127 去探讨。

  下一篇继续介绍排序算法。

  template

  int get_pos(int start_pos, int end_pos, T * src, T value)

  {

  if (start_pos == end_pos - 1)

  {

  if (value >= *(src + start_pos))

  {

  return end_pos;

  }

  else

  {

  return start_pos;

  }

  }

  else if (value < *(src + ((start_pos + end_pos) / 2)))

  {

  get_pos(start_pos, (start_pos + end_pos) / 2, src, value);

  }

  else if (value > *(src + ((start_pos + end_pos) / 2)))

  {

  get_pos((start_pos + end_pos) / 2, end_pos, src, value);

  }

  else if (value == *(src + ((start_pos + end_pos) / 2)))

  {

  return ((start_pos + end_pos) / 2);

  }

  }

  template

  void sort(T *temp, int len)

  {

  for (int i = 1; i < len; i++)

  {

  if (*(temp + i) > *(temp + i - 1))

  {

  continue;

  }

  else

  {

  int pos = get_pos(0, i, temp, *(temp + i));

  T t = (*(temp + i) );

  memcpy(temp + pos + 1, temp + pos, sizeof(T) * (i - pos));

  *(temp + pos) = t;

  }

  }

  }

  int main(int argc, char* argv[])

  {

  int src[10] = {1000, 3456, 200, 134, 2342342, 40, 80, -1, 0, 21 };

  sort(src, 10);

  for (int i = 0; i < 10; i++)

  {

  printf("%d ", src[i]);

  }

  system("pause");

  return 0;

  }

  疯狂Java培训专注软件开发培训,提升学员就业能力,重点提升实践动手能力。技术知识沉淀深厚的老师,让你感受Java的魅力,激发你对于编程的热爱,让你在半年的时间内掌握8-10万的代码量,掌握Java核心技术,成为真正的技术高手;通过大量全真企业项目疯狂训练,迅速积累项目经验。让你成为技能型的现代化高端人才,迅速获得高薪就业!时间不等人,赶紧联系我们吧!疯狂java培训中心地址:广州天河区车陂沣宏大厦3楼。

  疯狂Java培训专注软件开发培训,提升学员就业能力,重点提升实践动手能力。疯狂软件开设了java课程,ios课程,android课程,为你提供一个学习java技能的好机会,疯狂软件特大优惠活动,加疯狂软件微信号(疯狂软件),抢优惠,优惠100元+赠送iOS教材一本 详情请看疯狂java培训官网。IT从业着仍是社会所需要的高端人才,广州疯狂软件之力于培养企业所需要的中高端IT人才,让你成为备受企业青睐的人才。

原文地址:https://www.cnblogs.com/gojava/p/3506952.html